전체 글

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연산하면 부분집합을 구해낼 수 있다.

1. 분류다이나믹 프로그래밍 2. 풀이 첫 몇 항을 제외한 나머지 모두가 규칙에 맞춰 증가하는 형태를 이루고 있다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 3이 쓰여진 삼각형의 한쪽 변에 1, 2 삼각형, 4가 쓰여진 삼각형의 한쪽 변에 1, 3 삼각형, 5가 쓰여진 삼각형의 한쪽 변에 1, 4 삼각형, ... D[N] = D[N-1] + D[N-5]의 규칙에 맞춰서 증가한다. 첫 몇 항만 초기화해주고 나머지는 저대로 구하면 답을 쉽게 찾아낼 수 있다.

1. 분류다이나믹 프로그래밍 2. 풀이 파스칼의 삼각형이 이항계수를 나타낸다는 것을 알고 있었다면 쉽게 풀리는 문제이다. 최상단 1을 초기화하고 이후부터 좌측, 우측 끝단을 1로 만든 후 가운데 숫자를 만들어내면 끝이다. 2차원 배열 d[y][x]가 이항계수에 들어갈 숫자들을 저장한다. 가장 윗 줄부터 하나씩 채워넣으며 N, K를 구하면 된다.

1. 분류다이나믹 프로그래밍 2. 풀이 규칙만 찾으면 금방 풀리는 문제이다. 나는 이런 류의 문제에서 규칙성이 있겠다 판단되면 엑셀을 켜고 하나하나 대입하여 확인한다. 대부분의 경우에 규칙이 적용되면 금방 구할 수 있기 때문이다. N, K에 숫자를 0, 0부터 대입하여 몇 개 구하면 바로 알 수 있다.

1. 분류이분탐색 2. 풀이 먼저 N개의 숫자를 입력받은 뒤 이어서 입력받는 M개의 숫자가 먼저 받은 N개 숫자들 중 있는지를 찾는 문제. N, M 둘다 최대 10만 개까지 입력이 가능하기 때문에 O(N^2) 이상은 무조건 시간 초과가 난다. 입력받은 숫자를 오름차순으로 정리한 뒤 이분탐색으로 찾는다면? N개 입력 : O(N)정렬 : sort 함수 이용 - O(NlogN)탐색 : O(MlogN) 이 정도면 제한시간 내에 무리없이 찾아낼 수 있을 것이다.