하다보니

이번 단원은 개념도 그렇게 어렵지 않고 구현 난이도도 낮아서 많이 수월하다. 다이나믹 프로그래밍을 알파벳 앞 글자만 따서 DP라고 부르기도 한다. DP는 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘. 즉, 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘. -> DP는 작정하고 어렵게 하고자 한다면 한도 끝도 없이 어려워지지만 코딩 테스트에 나올 수준의 DP문제는 일단 점화식만 찾고 나면 그 뒤는 초기값을 채워 넣은 후에 반복문을 돌면서 배열을 채우면 끝이어서 구현이 굉장히 쉽다. 하지만 점화식을 이끌어내는 과정이 그렇게 쉽지 않고, 무엇보다도 초보 단계에서는 주어진 문제가 DP로 푸는 문제라는 ..

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 즉, 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법. 백트래킹은 상당한 구현력을 필요로 하고 실수하기도 쉽다. 또한 재귀의 특성상 틀리더라도 실수한 부분을 찾기가 정말 힘들어서 많은 시간을 할애해 개념을 익히고 연습을 해야하고, 그렇지 않으면 풀이는 대충 알겠는데 그 풀이를 코드로 옮겨내지 못해서 문제를 틀릴 확률이 크다. 그래도 한편으로는 그렇게 응용을 할 수 있는 건덕지가 많지는 않기 때문에 예제들을 꼼꼼하게 풀고 BFS를 배울 때와 비슷하게 기본적인 코드의 형태를 익혀두면 할만할것이다. 백준 15649번-N과 M 비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력하는 방식으로 구현할 수 ..

재귀란 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것. 우리가 지금까지 당연하게 생각하던 절차 지향적인 사고를 탈피해야 한다. 1번 도미노가 쓰러지고 이후에 2번 도미노 쓰러지고... 이렇게 연쇄적으로 진행되어 모든 도미노가 쓰러진다는 절차 말고 q번 도미노가 쓰러진다. k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다 까지만 생각한 후 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 한다. 올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 이러한 입력을 base condition 내지는 base case라고 한다. 그리고 모든 입력은 base conditio..

DFS는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. BFS 과정 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 n개일 때 O(n)이다. 위의 과정은 BFS의 과정과 다른 것은 다 똑같고 큐만 스택으로 바뀐 것이다. 큐를 쓰면 BFS이고 스택을 쓰면 DFS가 된다. #include using namespace std..

그림판의 페인트 기능을 이용하면 물고기의 색을 바꿀 수 있다. 페인트의 기능은 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 것이고 이런걸 flood fill이라고 한다. 이 기능을 어떻게 구현할 수 있을까. 일단 클릭한 칸의 상하좌우를 보며 색이 같은지를 확인하고 같은 칸에 대해서 또 상하좌우로 확인하고,,,좀 막연하다. 이 기능을 BFS 알고리즘으로 해결할 수 있게 된다. BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 원래 bfs는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 여기서 말하는 그래프는 정점과 간선으로 이루어진 자료구조이다. BFS 과정 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 원소를 꺼내어 그 칸에 상하..

스택의 대표적인 활용 사례로 수식의 괄호 쌍이랑 전위/중위/후위 표기법, DFS, Flood Fill 등이 있다. 이 중에서 전위/중위/후위 표기법은 코딩테스트 대비용으로는 너무 지엽적이라 제외한다. 나머지는 다 강의에 포함되어 있고 이번 시간에는 수식의 괄호쌍을 공부해보겠다. 수식의 괄호쌍이란 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다. 문제 해결 방법 여는 괄호가 나오면 스택에 추가 닫는 괄호가 나왔을 경우, 스택이 비어있으면 올바르지 않은 괄호 쌍 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 스택의 top이 짝이 맞는 괄호일..

덱은 Restricted Structure의 끝판왕 같은 느낌의 자료구조이다. 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 참고로 자료구조의 덱은 deque이고 Double Ended Queue라는 뜻을 가지고 있다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 좋다. 덱의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤의 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL stack, queue에서 불가능했던 것을 생각하면 꽤 독특한 일이다. 덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는..

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. FIFO(First in First out) 구조이다. 큐의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤의 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각함. 큐에서는 추가되는 곳을 rear, 즉 뒤 쪽이라고 하고 제거되는 쪽을 front, 즉 앞 쪽이라고 한다. 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만 배열을 가지고 만들 땐 해당 기능이 가능하도록 구현할 수 있다. 하지만 STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없다. 큐를 ..

스택이란 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. LIFO(Last in First out) 자료구조라고 부른다. 참고로 큐나 덱도 스택처럼 특정 워치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려 있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 원소의 추가 O(1) 원소의 제거 O(1) 제일 상단의 원소 확인이 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 - 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 스택 구현 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있다. 둘 중에서 배열을 이용하는게 구현이 더 쉽다. 원소를 ..

연결 리스트란 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 이곳저곳에 흩어져있다. 연결 리스트의 성질 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함 - 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않아서 원소를 순서대로 탐색해야 한다. 2. 임의의 위치에 원소를 추가/제거는 O(1) - 이 성질이 배열과 비교했을 때 큰 차이가있는 성질이고, 연결 리스트의 큰 장점이다. 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 1. 단일 연결 리스트 - 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트이다. 2. 이중 연결 리스트 각 원소가 자신의 이전 원소와 다음..