항상 DP 문제를 접하고 풀 때마다 느끼는거지만 '재귀'를 이용해 문제를 풀고자 하면 항상 어디에서 막히거나 시간 초과에 걸린다. 메모이제이션을 제대로 못해서인지 아니면 내가 점화식을 제대로 못짜서인지는 모르겠지만, 다른 사람의 풀이를 보면 죄다 거의 반복문으로 풀어낸다. 나도 반복문으로 풀고 싶지 않은 것은 아니다. 매번 DP 문제를 풀 때마다 재귀를 통해 문제를 풀어왔기 때문에, 반복문을 통한 접근 방식에 익숙치 않아서 어떻게 접근해야 할지도 모르겠고, 사실 아직까지 Top-down과 Bottom-up 방식을 구분하여 점화식을 세우는 방법 조차 내겐 너무 벅찬 일이다. 언제쯤 DP 문제가 익숙해져서 술술 풀어낼 수 있을지는 모르겠다. 매일 최소 한 문제씩 DP 문제를 풀고 있긴 한데, 감이 잡히는 것..
문제를 읽고 이해하기 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. 입력에서 0이 주어진..
문제 인식 C++ STL의 vector는 push_back()을 통해 배열의 원소를 계속 늘릴 수 있다. 그러나, vector가 처음 선언될 때 예약되어 있던 '용량'을 초과해버리면, 그보다 더 '큰' (2배 정도) 용량의 메모리를 할당한 후 기존의 원소를 모두 복사하고, 기존의 메모리는 해제하는 작업을 거친다. 즉, 이 작업에는 할당 -> 복사 -> 해제의 비용이 들어간다. 이 작업의 시간 복잡도는 O(1)로 알려져있으나 이는 엄연히 Amotized Analysis 즉, 분할 상환 분석법을 통해 구해진 시간 복잡도일 뿐이며, 최악의 경우 O(N)까지 시간 복잡도가 커질 수 있다. 한 마디로, 재할당이 많이 일어나면 일어날 수록 성능이 매우 떨어진다는 의미이다. 실제로 BOJ 문제에서 이로 인해 시간 초..
문제를 읽고 이해하기 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 ..
문제를 읽고 이해하기 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법..
분할 정복이란? 분할 정복(Divide and Conquer)이란 알고리즘 디자인 패러다임 중 하나로, 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 각 문제에 대한 답을 재귀를 통해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 알고리즘입니다. 일반적인 재귀와 다른 점 분할 정복은 일반적인 재귀와 다르게 부분 문제를 나눌 때 '거의 같은 크기의 부분 문제'로 나눈다는 점입니다. 반면에 일반적인 재귀는 하나의 조각과 나머지 전체로 나눕니다. 분할 정복의 구성 요소 - 문제를 더 작은 문제로 분할하는 자연스러운 방법 - 각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 효율적인 방법 + 더이상 분할하지 않고 바로 풀 수 있는 매우 작은 문제
배경 SW마에스트로 11기 코딩테스트를 봤는데, 생각보다 내가 알고리즘을 굉장히 못한다는걸 느꼈다. (개발만 하고 살았으니 그럴만도..) 그래서 체계적으로 알고리즘을 공부할 수 있는 방법을 찾아보다가, 알고리즘계의 바이블이라고 알려진 종만북을 구매하게 되었다! 공부 계획 내가 제일 약한 동적 계획법(DP)와 탐욕법(Greedy) 그리고 분할 정복을 위주로 책과 함께 문제를 풀어 나갈 것이며, 다른 유형에 대해서는 BOJ 또는 Programmers를 이용하여 하루에 한 문제 이상 학습한다. 3월 16일 2. 문제 해결 개관 ~ 3. 코딩과 디버깅에 관하여, 8. 동적 계획법 - 도입, 와일드카드 + BOJ DP 1문제 풀기 (완료) 3월 17일 p145 ~ p155 무식하게 풀기, p175 ~ p182 분..