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

1. 문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 2. 풀이과정 1. 출발지부터 시작, 출발지는 방문 체크 2. 편의점, 도착지 전체를 보면서, 갈 수 있는 곳 확인한다. - x좌표의 차이 + y좌표의 차이

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://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..