알고리즘

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번 행동의 경우엔 바로 전 항에서 스티커를 떼지 않은 경우에만 가능하다. 점화식으로 표현하면 다음과 같다. 스티커를 건드리지 않을 땐 이전 항 중 최대값을 취하고 스티커를 뗄 땐 이전 항..

1. 분류다이나믹 프로그래밍 2. 풀이 전형적인 DP 문제 중 하나이다. 스티커의 조건을 잘 생각하고, 1열부터 5열까지 순차탐색으로 진행하면서 값을 찾을 방법을 생각해보았다. 한 스티커의 열 단위에서 행할 수 있는 동작은 3가지가 있다. 1. 아무 스티커도 건드리지 않는다.2. 윗 줄의 스티커를 떼어낸다.3. 아랫 줄의 스티커를 떼어낸다. 이 세 가지 동작을 세세하게 나눠보자면, 1. 아무 스티커도 건드리지 않을 때는 이전 단계에서 무엇을 하던간에 상관 없이 수행할 수 있다.2. 이전 단계에서 윗 줄의 스티커를 떼어내지 않은 경우에만 가능하다.3. 이전 단계에서 아랫 줄의 스티커를 떼어내지 않은 경우에만 가능하다. 이렇게만 알고 있으면 점화식을 작성할 수 있다. 1. 이번 단계에서 아무 스티커도 건드리..

1. 분류다이나믹 프로그래밍 2. 풀이 0과 1로 이루어진 배열이 주어지고, 그 중 1로만 이루어진 가장 큰 정사각형의 넓이는 구하는 문제이다. 1051번 문제와 유사하나, 전부 1이어야 정사각형으로 인정한다는 점에서 다르다. 행열의 최대 크기는 1000x1000이고 하나하나 찾아가자면 O(N^3) 이상의 시간이 소요될 것으로 보이는데, 1000의 세제곱은 10억이므로 완전탐색은 불가능하다. 그렇다면 행열 요소를 하나하나 찾아가면서 정사각형의 크기를 바로 기록하는 방법은 없을까? 문제에서 주어진 정사각형의 내부는 모두 1이라는 성질을 생각해보니 DP로 이용할 점화식을 구할 수 있었다. 큰 정사각형은 내부에 작은 정사각형을 가지고 있다는 것을 생각해보자. 먼저 정사각형의 크기가 담길 부분의 기준을 정해야한..

1. 분류브루트 포스 2. 풀이 직사각형의 너비와 높이를 받아 내부의 정사각형 중 가장 큰 것을 구하는 문제이다. 네 모서리의 수가 같아야 정사각형으로 인정된다. 너비와 높이값이 최대 50이므로 O(n^4)이어도 풀 수가 있으므로 넉넉히 생각했다. 내부 정사각형을 하나하나 찾아가며 최대값을 뽑아내었다. 길이가 2인 정사각형부터 너비와 높이 중 작은 값(min)까지 검사했다. 내부에 for문이 2개 더 있는데 배열의 왼쪽 상단부터 우측 하단까지 일일이 방문하는 간단한 소스코드이다. 로직은 맞는데 계속 틀려서 곰곰히 생각을 해보니, 정사각형의 최소값을 0으로 주었기 때문이었다. 이런 실수는 특히나 조심해야겠다.

1. 분류브루트 포스, 비트마스크 2. 풀이 N개의 원소를 갖는 집합에서 합이 S인 부분집합의 개수를 세는 문제. 부분집합은 2^N개만큼 존재한다. 부분집합을 구하는 방법은 여러 가지가 있겠지만 나는 비트연산을 이용했다. A, B, C를 갖는 집합의 부분집합을 표로 그려보면 다음과 같다. 정수 이진수 부분집합 0 000 1 001 A 2 010 B 3 011 A B 4 100 C 5 101 A C 6 110 B C 7 111 A B C 위 사실만 알면 부분집합을 구하는 건 다 한 것이다. 정수 0부터 2^N - 1까지 반복문, 그 안에 원소의 개수(N)개만큼 도는 반복문. 그리고 반복문 두 개의 인덱스를 AND연산하면 부분집합을 구해낼 수 있다.