[문제] 13144번: List of Unique Numbers (acmicpc.net) 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net [문제 풀이] 우선 문제를 풀기 전에 문제 조건을 보면 주의해야 할 요소들이 보인다. 메모리 제한이 고작 32MB에다가 수열의 한계가 100,000이다. 즉, 평범한 방식으로는 시간 초과가 날테니 어떻게 풀어야 할지 고민해보자. 고민을 하다가 두 포인터 알고리즘을 이용하기로 하였다. 두 포인터 알고리즘을 사용해서 새로운 값이 이미 기존에 있는 값이라면 앞에서부터 시작대로 줄여나가기로..

[문제] 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [문제 풀이] 문자열에 대해서 배울 수 있는 좋은 문제이다. 나는 빈 string을 하나 더 만들고 해당 문자열에 스택을 사용하듯이 계속 쌓아뒀다. 그러다가 만일 해당 문자열이 bomb와 같다면 해당 문자열 만큼을 새로 만든 문자열에서 지우는 형식으로 진행하였다. * find를 쓸려다가 문자열의 길이가 1,000,000 라서 시간 복잡도에 걸린다고 생각하여서 쓰지 않았다. * string ..

[문제] 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [문제 풀이] 처음에는 굉장히 어렵게 접근을 하였었다. 백 트래킹을 활용해서 1의 조합들을 모두 구하고 해당 조합이 나올때마다 BFS를 활용해서 거리를 구해서 모든 거리에서의 최소값을 answer로 제출을 하였다. 하지만, 당연히 백 트래킹 + BFS로 가니 시간은 초과가 날 수밖에 없었다. 코드는 복잡해지는데 시간 복잡도도 올라가니 안 좋은 접근 방식이었다. 두번째로 생각을 바꿔보았..

[문제] 9251번: LCS (acmicpc.net) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [문제 풀이] 문제를 풀기 전에 문제의 제목인 LCS 알고리즘에 대해서 배워보도록 하자. 두개의 스트링을 이용해서 기본값이 0인 2차원 배열을 만들어보자. A C A Y K P C 0 0 0 0 0 0 A 0 0 0 0 0 0 P 0 0 0 0 0 0 C 0 0 0 0 0 0 A 0 0 0 0 0 0 K 0 0 0 0 0 0 해당 배열을 이용해서 우리들은 두개의 s..

[문제] https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net [문제 풀이] 문제 조건 제한이 까다로워 실수가 많았던 문제. BFS 에 익숙하지 않다 보니 초반에 코드가 더러워서 보기가 힘들었던 부분이 많았다. BFS나 DFS등을 쓸 때는 변수명을 잘 지으면서 최대한 코드를 보기 편하게 만들자. 먼저 불꽃이 가는 곳을 모두 만들고 다음으로 지훈이를 옮기자. * 팁 : 불꽃이 가는 곳은 기본 미로가 아닌 다른 불꽃 미로를 만들어두자. 안..

[문제] https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net [문제 풀이] 분할정복을 이용해서 풀자. 별 찍기 - 10 과 비슷하게 풀 수가 있으나 처음 위치를 x좌표를 n-1로 두어야 하는 것에 유의하자. 만일 사이즈(높이)가 3보다 크다면(10) 위치를 3곳으로 나누어 주자. 첫번째 위치는 현재 위치 그대로(11) 두번째 위치는 x를 현재 크기의 1/2를 뺀 지점, y를 현재 크기의 1/2를 더한 지점으로 (12) 세번째 위치는 x를 현재 크기의 1/2를 더하고 y를 현재 크기의 1/2를 더한 지..