Social Developer

어제보다 한 걸음 더

Algorithms

이 문제는 문제가 dp 적용 가능함을 파악한 뒤, 점화식을 찾아내는 것이 중요하다. N의 크기가 증가할수록 오른쪽으로 전체 직사각형이 길어지고, 이전 크기(N-1, N-2)와의 연관성을 지니고 있다. 이 때문에, 특정 2xN 크기의 타일링 방법의 수를 구할 때 재귀적으로 이전 크기의 값들을 통해 구할 수 있으며(Divide & Conquer), 한 번 계산한 값들을 저장해놓고 재사용해 연산의 숫자를 줄여줄 수 있다(Memoization). 여기까지 알아도, 구체적으로 어떤 연관성, 규칙을 가지고 있는지를 파악해야 문제를 풀 수 있다. 각 N의 크기별로 경우의 수를 나열했다. N일 때의 경우의 수는 아래 두 가지 유형의 경우의 수들의 합으로 구해진다. 1. N-1일 때 경우의 수에서 오른쪽에 2 X 1 크..

2021. 3. 9.

Algorithms

블로그에 같은 문제를 2번씩 올리는 사람이 나말고 또 있을까..? 분명 풀어서 풀이 업로드까지 해놓았는데, 거의 정확히 1년이 된 오늘 다시 푸는데 엄청 애를 먹었다. 단순한 문제 풀이가 아니라, DP를 활용함에 있어 중요한 부분인듯 싶어 고민했던 부분을 다시 기록하려 한다. 문제를 보자마자 처음 든 생각은 1이 될 때까지 입력값을 if 문으로 1번 연산(3으로 나눔) 먼저, 다음은 2번 연산(2로 나눔), 두 연산 모두 안되는 경우 3번 연산(-1)으로 처리하면서 과정을 count하면 될 거라고 생각했다. 역시 이렇게 간단할 리가 없다. 예제 입력 2처럼 10 -> 9 -> 3 -> 1 로 먼저 3번 연산을 하는 경우가 최솟값을 반환하는 경우가 있기 때문이다. 여기까지 보고 나서 바로 든 해결 방법은 ..

2021. 3. 7.

Algorithms

이전 1753번 최단경로 문제와 같이 최단경로 유형의 문제다. 다만 이번에는 버스 노선이 edge인데 음수 범위를 포함하기 때문에, 벨만 포드 알고리즘을 사용해 최단경로를 구해주어야 한다. 이번 문제에서 유의해야 할 점은 최단 경로를 나타내는 dist 배열을 int가 아닌 long으로 설정해줘야 한다는 점이다. 이 점을 캐치하지 못하고 출력초과 결과를 받아 오래 헤맸다. (이 문제에서 출력초과는 사실상 음수사이클 판정을 하지 못한 것) 간선 weight의 범위가 -10,000 < C < 10,000이고, 노드의 수가 최대 500임에도 dist 배열을 long으로 설정해줘야 하는 이유는 경로의 weight를 계산하는 과정에서 음의 사이클이 존재하는 경우 알고리즘 내부 반복문을 한 번 돌 때마다 최악의 경우..

2021. 3. 4.