파이썬

[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 풀이 이 문제는 그리디 알고리즘과 우선순위 큐를 이용해서 해결할 수 있습니다. 2022.07.18 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의..

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생각을 해봤는데 알고 보니까 이름하고는 별 상관이 없더라구요..ㅋㅋㅋㅋㅋ 동적 계획법은 어떤 문제를 여러개의 작은 문제로 나눠 해결하고 그 결과를 저장을 했다가 큰 문제를 풀 때 사용하는 문제 풀이 기법입니다! 즉, 한 번 푼 문제는 다시 풀지 않게 되는 것이죠. 분할 정복 알고리즘과 비슷하다고 생각하실 수도 있는데 해결한 문제를 반복적으로 해결하는 분할 정복과는 달리 동적 계획법은 이미 푼 문제는 기억하여 다시 풀지 않기 때문에 부분 문제가 중복된다면 더욱 효율적이라고 볼..

[파이썬으로 배우는 알고리즘] 분할정복(Divide & Conquer)과 병합/퀵정렬

분할정복(Divide & Conquer) 알고리즘이란? 문제 해결에 있어서 어떤 문제를 더이상 쪼갤 수 없을 때까지 분할한 후 (Divide) 하위 문제들을 해결하고 (Conquer) 합치면서(Combine) 문제의 답을 도출하는 알고리즘을 분할정복(Divide & Conquer) 알고리즘이라고 합니다. 설명만으로는 잘 이해가 안 갈 수도 있으니 대표적인 분할정복 문제인 병합정렬(Merge Sort)과 퀵정렬(Quick Sort)을 예시로 직접 풀어보면서 설명하도록 하겠습니다! 병합정렬(Merge Sort) 병합정렬 개념 1) 정렬할 리스트를 더 이상 나눌 수 없을 때까지 2개의 부분 리스트로 분할(Divide) 2) 더이상 나눌 수 없는 부분 리스트를 다시 합치면서 정렬 수행(Conquer, Combi..

[백준(BOJ)] #2263- 트리의 순회 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 풀이 이 문제를 풀 때 생각보다 방법이 쉽게 생각나서 빨리 풀겠다 생각했는데 구현에서 애먹어서 성공까지 가는데 오래 걸렸네요..ㅋㅋㅋㅋㅋㅋ 방법 자체는 트리 순회의 특징과 재귀 호출에 대해 어느 정도 알고 있으면 그렇게 어렵지는 않습니다! 트리 --> 2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tree) [파이썬으로 배우는 자료구조] 트리(Tree) 1. 트리(Tree)란? ..

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIFO 구조라는 것을 배웠습니다. 큐 배우기 --> 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) 1. 스택(Stack) 1.1. 스택이란? 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 들어볼까요? 우리가 보통 접시를 선반에 차곡차곡 쌓아올린 후 쌓여있는 c4u-rdav.tistory.com 그렇다면 우선순위 큐는 무엇을 의미할까요?? 먼저 들어온 데이터를 무작정 먼저 처리하는 구조가 아니라 데이터에 우선순위에 따라 우선순위가 높은..

[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의 가장 좋아 보이는 것만 선택하기 때문에 나중에 미칠 영향은 고려하지 않아 지역적으로는 최적이지만 최종적(전역적)인 답에 도달했다고 해서 그것이 최적해라는 보장은 없습니다. 만약 그리디 알고리즘을 적용하여 위와 같은 트리에서 거쳐 가는 노드 값의 합을 최대로 만든다고 하면 순간의 선택만 고려하기 때문에 3 -> 7 -> 9라는 경로로 해는 19가 됩니다. 하지만 실제 최적해는 21(3 -> 5 -> 13)로 이는 그리디 알고리즘이 최적의 해를 보장할 수 없음을 보여줍니다. 따라서 그리디 알고리즘을 적용하려면 지역적으..

[백준(BOJ)] #1285- 동전 뒤집기 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 풀이 저는 이 문제를 해결하기 위해 먼저 행 또는 열을 기준으로 선택하여 뒤집는 모든 경우의 수를 구했습니다. 이때 행을 뒤집는 연산을 할 때 비트마스킹을 적용하여 행을 뒤집는 경우의 수를 구했습니다. 2022.07.15 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 비트마스크(BitMask) [파이썬으로 배우는 알고리즘] 비트마스크(BitMask) 1. 비트마스크(BitM..

[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

비트마스크(BitMask)란? 컴퓨터는 내부적으로 모든 데이터를 이진수로 표현을 합니다. 예전에 c언어로 비트 체계와 비트 연산자를 간단히 다룬 적이 있는데 비트에 대해서 궁금하신 분들은 참고하시면 될 것 같아요. 2020.07.17 - [프로그래밍언어/c언어] - C언어 독학 #7. 비트 체계와 비트 연산자 C언어 독학 #7. 비트 체계와 비트 연산자 인삿말 안녕하세요 알다브입니다. 저번 시간에 연산자에 대해서 알아봤습니다. 사실 저번 시간에 비트 연산자까지 다 끝내려했는데 비트 연산자까지 다루면 너무 길어질까봐 이번 글에서 따로 c4u-rdav.tistory.com 비트의 특성을 이용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 하며 엄밀히 말하면 알고리즘이라기보다는 일종의 테크닉이라고 볼..

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인접한 노드부터 탐색하는 알고리즘입니다. 스택 자료구조를 활용하는 DFS와 달리 BFS에서는 일반적으로 큐 자료구조를 이용합니다. DFS 배우기 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) 1. DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 탐색 알고리즘입니 c4u-rdav.tistory.c..

[백준(BOJ)] #19236- 청소년 상어 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제 풀이 이 문제는 구현 문제로 DFS 알고리즘을 적용하여 풀었습니다. DFS 알고리즘 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) 1. DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로..