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

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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이과정 간단한 BFS문제지만, 주의해야 할 점은 현재 칸과 다음 칸이 이어져있는지 확인해야 한다는 점이다. 처음엔 터널만 있으면 간다 생각하고 풀었다가 문제를 다시 읽고 수정했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Qu..

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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이 과정 테두리에 있지 않는 각 프로세서마다 4방향 or 선택X 경우 합쳐 5가지 경우의 수가 있다. 기본적인 부분집합인 선택O or 선택X에서 선택지가 5개로 늘어났다고 볼 수 있는 것이다. 이 문제의 핵심은 부분집합과, 재귀에서의 복구하는 과정이다. 아래 코드에서는 연결한 부분을 2로 표시한 후, 재귀가 끝나고 다시 0으로 되돌려주고 다음 case를 진행하도록 했다. impor..

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) 최대값 구하기 - 처음 값을 입력받을 때..