전체 글

윈도우즈 10 환경에서 VS code, Python3을 활용하여 크롤링을 공부해보기로 하였다. 설치하고 연동하는 방법은 다른 블로그에도 많으니 넘어가기로 하고... 처음 코드를 작성하다 보면 pylint를 찾을 수 없다는 에러가 발생한다 (Linter pylint is not installed) VS code는 참 친절하다. 직접 콘솔 창에서 설치해야 할 것을 버튼 하나로 해결해준다. 에러가 발생하자마자 pylint를 설치하는 버튼을 눌러 보았으나... 설치가 안 된다. 에러 로그를 들여다보면 __init__.py 파일에 문제가 생겼댄다. 들어가서 문제의 75번 줄을 확인해 보았다. 자세히 보면 무언가 이상함을 알 수 있다. except UnicodeDecodeError 아래의 s.decode('utf_..

https://www.acmicpc.net/problem/7576 1. 분류 BFS 2. 풀이 모든 토마토를 익힐 때까지 며칠이나 걸릴지를 구하는 문제. 익은 토마토는 주변 상하좌우의 토마토를 익혀버린다. 좀비도 아니고...; 큐에 넣은 인접 토마토들이 다 빠져나온 순간을 하루가 지난 것으로 설정하였다. 3. 소스코드 #include #include using namespace std; int map[1000][1000]; const int dy[4] = { -1, 0, 1, 0 }; const int dx[4] = { 0, 1, 0, -1 }; int main() { int m, n, day = 0; bool isPossible = false, isFull = true; queue q; scanf("%..

1. 분류Prefix 2. 풀이 두 점 (x1, y1), (x2, y2)으로 그릴 수 있는 직사각형의 범위 내에 있는 모든 수의 합을 구하는 문제이다. 가장 간단하게 풀 수 있는 방법은 역시나 이중 반복문으로 수를 일일이 더하는 방법일 것이다. 아쉽게도 그 방법은 사용하지 못한다. 합을 구해야 하는 갯수 M개, 행과 열의 개수 N개이므로 최악의 경우를 생각해본다면 시간복잡도는 O(M * N^2) => 100,000 * 1,024 * 1,024 = 1,048,576,000 무조건 시간초과를 유발할 것이다. 조금 다르게 생각해보자. 예제 입력에서 첫 번째 출력은 (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)를 더하는 것이다. 입력을 받는 동시에 미리 더해본다면? 표의 각..

1. 소개 프로그래밍 문제에 가장 자주 출현하는 디자인 패러다임이다. 메모리를 희생하여 속도를 얻는 가장 대표적인 방식이기도 하다. 이름이 굉장히 거창하지만 사실 의미는 없고 단순히 멋있어서 지은 것이라고... 종만북(프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략)에서는 DP의 특성 상 동적 프로그래밍보다는 동적 계획법이 더 알맞은 번역이라고 소개하고 있다. 2. 풀이법 분할 정복과 접근방식이 유사하다. 주어진 문제를 더 작은 문제들로 나누고 각 조각들의 답을 도출해내기 때문이다. 단, DP에서는 단 한 번만 계산하고 그 결과를 다시 재활용하여 속도를 향상시킨다는 점에서 다르다. 가장 쉽게 생각해볼 수 있는 사례로 이항계수가 있다. BOJ 이항 계수 2 링크위키백과(파스칼의 삼각형) 위키백과의 공식..

1. 분류다이나믹 프로그래밍 2. 풀이 이런 식의 문제들은 체육대회의 달리기 시합이라고 생각하면 쉽게 구할 수 있다. 다 같이 출발하여 가장 먼저 도착한 사람이 이기듯이 다 같이 출발하여 맨 아래에 도달했을 때 가장 큰 값을 가진 시작점이 이기는 것이다. 어짜피 문제의 조건 상 바로 아래 땅으로 내려갈 때 같은 열을 제외하고 항상 최대값을 선택해야 하기 때문에 코드도 어렵지 않게 짤 수 있다.

1. 분류다이나믹 프로그래밍 2. 풀이 숫자를 여러 개 주고 연속된 숫자들의 합 중 가장 큰 값을 도출해내는 문제이다. 다이나믹 프로그래밍으로 해결했다. 첫 숫자부터 끝 숫자까지 순회면서 (dp+현재 값)과 현재값 중 큰 값을 남긴다. 그리고 다시 처음부터 최고값을 찾는다.

https://www.acmicpc.net/problem/1697 1. 분류 BFS 2. 풀이 수빈이의 최소 이동 시간을 계산하는 문제이다. 입력으로는 시작점 좌표와 도착점 좌표를 받는다. 문제의 조건에서 수빈이는 3가지의 행동을 할 수 있다. 1. 현재 있는 위치에서 +1 2. 현재 있는 위치에서 -1 3. 현재 있는 위치의 x2로 순간이동 문제에서 주어진 예제는 5, 17이다. 5 → 4 → 8 → 16 → 17 5 → 10 → 9 → 18 → 17 위의 2가지 방법 정도가 4번만에 도착할 수 있는 최단 거리이다. 나올 수 있는 경우의 수들을 그림으로 그려보았다. 왼쪽 화살표는 -1, 중앙은 +1, 오른쪽은 x2를 한 것이다. 그림을 보면 DFS로 풀 수 없는 문제임을 알 수 있다(5 → 4 → 5 ..

1. 분류다이나믹 프로그래밍 2. 풀이 시작점을 몰라 꽤 오랫동안 헤멘 문제였다. 첫 항부터 시작하면 마지막 항 스티커를 어떻게 해야하는지를 깊게 고민했기 때문이다. 여러 번의 시행착오 끝에 괜찮은 방법이 생각나서 잊지 않기 위해 포스트를 작성하게 되었다. 1항부터 N항까지, 각 항마다 스티커에 할 수 있는 행위는 단 두 가지이다. 1. 스티커를 떼지 않는다.2. 스티커를 뗀다. 1번 행동을 할 때는 바로 전 항에서 무엇을 하던 상관 없으나 스티커를 한번 떼면 양 옆에 붙은 스티커를 건들 수 없다는 조건이 있기 때문에 2번 행동의 경우엔 바로 전 항에서 스티커를 떼지 않은 경우에만 가능하다. 점화식으로 표현하면 다음과 같다. 스티커를 건드리지 않을 땐 이전 항 중 최대값을 취하고 스티커를 뗄 땐 이전 항..