네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 풀이과정 처음엔 단순하게, 아래 코드처럼 상대방과 상대방과 연결된 노드들에 연결된 노드를 추가시켜주려고 했다. 하지만, 하나의 네크워크의 연결된 정보를 그에 속한 모든 노드들이 중복해서 갖다보니 메모리 초과가 났다.. public static void connect(String p1, String p2) { Set s1 = personNo.get(p1); Set s2 =..

1. 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 2. 풀이과정 '관계 = 나보다 뒤에 있다'라고 정의하고 보았다. i => k 이고 k =>j이면 i=>j인 것을 모든 수에 대해 적용시키면 된다. 여기서 i==j일 때는 시작지와 도착지가 같으면 의미가 없으므로 넘긴다. 또, j를 들어가기 전 i=>k부터 성립이 안 되면 앞에서 걸러주면 시간이 단축된다. import java.io.*; import java.util.*; pub..

1. 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 2. 풀이과정 입력이 아래와 같이 주어진다고 하면, 6 2 3 1 5 5 2 1 앞에서부터 증가하는 수열을 찾으면서, 그 때마다 마지막에 위치한 수도 같이 저장한다. 감소하는 수열은 뒤에서부터 증가하는 수열과 같은 의미로, 앞의 과정을 인덱스 N-1에서부터 똑같이 해주면 된다. 그리고나서, 두 부분으로 잘라서 앞부분의 제일 긴 증가하는 수열 길이 + 뒷부분의 제일 긴 감소하는 수열의 길이를 더한 값의 최대..

1. 문제 https://www.acmicpc.net/problem/5577 5577번: RBY팡! 세로로 N개의 공이 붙어있으며, 각 공의 색은 R(빨강), B(파랑), Y(노랑) 중 하나이다. 플레이어는 한 공의 색을 다른 색으로 바꿀 수 있다. 이러한 변환을 거쳐 동일한 색의 공이 4개 이상 연속되면 www.acmicpc.net 2. 풀이과정 1. 입력을 받으면서 같은 수 끼리 이어진 개수를 2차원 배열 (값, 개수)로 기록한다. ex) 1113221 => {{1, 3}, {3, 1}, {2, 2}, {1, 1}} 2. 개수를 센 배열을 순차적으로 접근하면서 simulation을 한다. 최소로 하기 위해서는 같은 색이 이어진 곳 중간을 굳이 다른 색으로 바꿀 필요가 없다. 따라서, 지금 접근한 공의..

1. 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 2. 풀이과정 [실행 과정] 1. Main에서 (0, 0)의 물고기를 잡아먹고 시작한다. 2. 물고기가 이동한다. 3. 상어가 다음으로 이동할 위치를 고른다. 간단하게 보면, 상어의 위치에 따른 dfs 알고리즘이다. 여기서 map을 변경한 것을 재귀가 끝난 후, 복구하는 과정 때문에 길어졌다. 시간을 줄이기 위해서, 물고기의 번호와 map의 위치를 매핑시켜 저장한 fi..

1. 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 2. 풀이과정 1. 팀 나누기(조합) 조합의 특성을 이용하자면, 아래 문제에서 nC1과 nC(n-1)은 같은 경우라고 볼 수 있다. 따라서 n/2개까지만 뽑는 조합을 작성하여 simulation을 돌린다. 왜 같은 경우인지 설명하자면, 두 팀으로 나누어 두 팀의 값 차이를 결과로 내기 때문에, 각 팀이 빨간팀인지 파란팀인지는 상관없다. 빨간팀의 값이 1이고 파란팀이 3일 때와 빨간팀의 값이 3이고 파란팀이 ..

1. 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2. 풀이과정 작은 수부터 순열 생성하면서 simulation한다. [simulation 단계] 1. 해당 칸에 번호 i를 놓을 수 있는지 확인 => 못 놓으면 다음 i보고, 놓을 수 있으면 다음 단계로 2. 해당 칸에 번호를 놓고, 방문 체크 3. 다음 칸을 보자 4. 다음 칸들을 다 본 후엔, 2번 과정을 복구 import java.io.BufferedReader; import..

1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이과정 BFS를 사용한 이유 처음엔, dfs로 풀고 시간 초과가 났다. 생각해보니 이 문제는 가다가 해당 노드에 더 작은 비용으로 갈 수 있는 경우, 굳이 더 갈 필요가 없어서 버리기 때문에 bfs가 유리하다. dfs를 사용할 경우, 초반에 전체 탐색을 하기 때문에 시간 초과가 나는 것 같다. Priority Queue를 사용한 이유 bfs임에도 priority..

1. 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2. 풀이과정 채운다 = 빈칸없게! 1) n이 0이나 홀수면, 0을 출력 2) 짝수면 아래의 규칙을 따름 p[n] = (p[n-2]*3) + (p[n-4]*2) + (p[n-6]*2) + ... = (p[n-2]*3) + (p[n-4] + p[n-6] + ... )*2 2칸일 때, 가능한 건 3가지, 4칸일 때만 가능한 건 2가지, 6칸일 때만 가능한 건 2가지, ... , 그 뒤로 모두 2가지씩 있다. 여기서 6칸일 때만 가능하다는 말은 n=2, n=4일 때처럼 6보다 작은 타일에서 블럭을 어떻..

1. 문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2. 풀이 과정 처음엔 쉬운 풀이 방법이 있을까 생각하다가, 안 떠올라서 그냥 모든 경우의 수를 다 돌려보고 생각해봐야겠다 하고 구현했는데, 통과가 되었다. 위로, 아래로, 왼쪽으로, 오른쪽으로 각각 0, 1, 2, 3으로 생각하고 5개를 뽑는 중복 순열을 만들었다. 선택한 차례대로 함수를 실행시켜 결과를 냈다. 1) 최대값 구하기 - 처음 값을 입력받을 때..