https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 부분문자열을 구하는 문제로 처음에는 for문을 중첩해서 구하는 방법을 생각했다. 하지만 시간초과가 났다. 입력되는 문자열의 길이가 최대 1,000,000(백만)이다. for문을 중첩해서 돌린다면 O(n^2) 약 1,000,000(백만) * 1,000,000(백만) = 억 단위가 넘어가서 1초 안에 풀지 못한다... 실패 import java.io.BufferedReader;..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이전에 한 번 푼 적이 있어서 풀이법을 떠올리는 건 쉬웠다. 1.정렬 : 우선 끝나는 시간을 기준으로 오름차순 정렬을 하고, 끝나는 시간이 같은 경우에는 시작 시간을 기준으로 오름차순 정렬을 한다. 2. 모든 시간에 대해서 끝나는 시간을 기준으로 하여 가능한 다음 회의 시작 시간을 찾는다. 2차원 배열을 정렬하는데, Arrays.sort와 Comparator 사용이 아직 미숙하다. 코드 import java.io.BufferedReader; import java.io.IOException; import java...

https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 처음에는 좌표를 가지고 사칙연산을 통해 넓이를 구하려고 했다. 하지만 넓이를 2차원 배열로 생각하고 색종이를 붙일 때마다 덮게 되는 부분에 1을 넣어주고, 최종적으로 넓이를 구할 때 1인 부분을 카운딩해주면 된다. 이렇게 생각하면 간단한 문제! 복잡하게 생각하지 말자. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.I..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 같은 태그인 다익스트라 문제를 풀고 다익스트라 복습겸 풀었다. 한 도착 지점의 최소비용만 구하면 되는거라 더 간단했다. 손으로 직접 다 치면서 알고리즘이 머릿속에 들어가고 손에 익게 했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제의 제목에서 알 수 있듯이 플로이드-와샬 알고리즘을 쓰는 문제이다. 골드4라는데 다른 골드 문제에 비하면 덜 까다로운 편이였다. 플로이드-와샬 알고리즘을 잘 알고 문제의 조건만 잘 처리를 하면 되기 때문에 같은 그래프 탐색의 DFS&BFS 문제보다 상대적으로 쉽게 느껴진다. 문제의 조건들을 꼼꼼히 읽어야 한다. "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다", "만약, i에서..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복&재귀 문제이다. 지금까지 풀었던 분할정복 문제 중에서는 쉬운 축에 속하는 것 같다. 재귀에 약해서 쫄았는데 생각보다 금방 풀렸다. 종이의 시작점의 행 번호, 열 번호, 종이의 크기를 매개변수로 보내 종이가 같은 수로 이루어져 있는지 확인한다. 종이가 같은 수로 이루어져 있으면, 해당 수의 카운터를 올리고 종료한다. 같은 수로 이루어져 있지 않으면, 재귀를 통해 크기를 1/3로 ..