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

1. 문제 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net 2. 풀이 과정 병합 정렬 + 이진 탐색 문제이다. 여기서 시간 단축을 위해 누적합 개념을 추가적으로 사용했다. 예를 들어, 입력이 아래와 같이 주어진다면 4 1 5 10 15 2 3 8 9 병합 정렬하면서 한식, 양식 수를 세서 누적합을 구해놓고 이진탐색할 때 이용한다. 1 2 3 5 8 9 10 15 한식 1 1 1 2 2 2 3 4..

1. 문제 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 풀이과정 풀이방법은 2가지가 있다. 위상 정렬 문제를 많이 접해보지 않아서 헤맸던 문제다. 1. 위상정렬 선행 요소를 입력 받을 때, 선행요소에 '나'를 추가하는 방식으로 한다. 즉, 모든 노드들의 후행요소로 저장해주는 것이다. 0번째 작업부터 차례대로 돌면서, 자신의 뒤에 실행할 곳에 수행 시간을 더해준다.이때, 선행 요소가 여러 개 있는 작업은 수행 시간이 가장 긴 선..

1. 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 2. 풀이 과정 한 장소에서 여러 곳으로 뻗어나갈 수 있기 때문에, 단순 dfs나 bfs로는 풀리지 않는다. 한 장소에 방문하면, 지금까지 방문한 장소를 모두 고려해 갈 수 있는 장소를 탐색한다. 방문한 장소를 찾아서 4방위 탐색해서 dfs로 들어가면 된다. +) 중복 방지를 위해 visited 배열을 사용한다. 비트마스킹으로 경로 방문 체크를 한다. import java.io.*; pub..

1. 문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이과정 1) 시작점 = 출발점이므로, 출발점은 어디든 결과는 같다. 따라서 시작점은 0으로 고정했다. 2) 순서에 따라 결과가 달라지는 순열 문제이다. 그리고 마지막에 도착지 => 출발지까지 값도 고려해주는 걸 잊지말자. import java.io.*; import java.util.*; public class Boj10971 { st..

1. 문제 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 2. 풀이과정 경우의 수 문제에 대각선의 특징을 이용하는 아이디어가 필요한 문제다. 우선, 모든 경우의 수를 고려하면 시간 복잡도는 O(2^(N*N))이고, 최대 2^100이므로 시간 초과가 난다. x+y가 짝수인 집단과 홀수인 집단을 나눈다. 이들은 서로 절대 같은 대각선 상에 있을 수 없기 때문에, 독립적으로 계산한 후 결과들을 더해주면 되는 것이다. 나눠보면, 체크보드처럼 그려지는 것을 확..

1. 문제 https://www.acmicpc.net/problem/3954 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 2. 풀이과정 문제도 문제지만, 이해가 어려웠던 문제였다.. 헷갈렸던 부분을 정리해보면, 1) - : -1이 되는 순간 255로! 즉 숫자는 0~255까지만 취급한다. 2) 명령 실행 횟수가 50_000_000초과하면, 현재 상태는 무한 루프를 돌고 있는 것이다. 정상 종료는 그 전에 끝나는 경우다. 해결 방법 : 무한 루프 외엔 일반 계산이다. 무한..

1. 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 풀이 과정 필요한 데이터를 만들어서 푸는 MST문제이다. MST 문제 해결 방법은 Kruskal과 Prim이 있는데 정점 기준으로 데이터를 기록했기 때문에, Prim을 사용했다. 1. 섬마다 번호 붙이기 2. 섬과 섬까지 거리 구하기 가로, 세로 각각 for문 돌면서 최솟값 갱신시켜나감 3. MST 구하기 *cycle없이 다 이어진, cost가 최소인 그래프 ..

1. 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 2. 풀이 과정 소수 구하기는 에라토스테네스의 체를 사용했고, 연속된 수의 합은 dp를 활용했다. 2부터 N까지 보면서, 소수가 보이면 values배열에 더한 값을 저장한다. 예시로 N=15일 때를 생각해보면, i=2 values = [2] i=3 values = [5, 3] i=4 values = [9, 7, 4] i=5 values = [14, 12, 9, 5] i=6 values = [20, 18, 15, 11, 6] => result++; ... 15보다 큰 값은 N(15)가 될 가능성이 없으므로,..

1. 문제 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 2. 풀이 과정 가장 많은 팀이 되는 경우 = 친구는 무조건 같은 팀이어야 하므로, 친구끼리만 같은 팀이고 나머지는 다 다른 팀 따라서, 친구만 찾아서 연결지어주면 된다. 친구인 경우 1) 친구의 친구는 친구 2) 원수의 원수는 친구 조건 1에서는 dfs로 친구의 친구의 친구 ... 까지 다 찾아야 한다. 하지만, 원수의 경우 자신의 원수의 원수만 친구이다. 즉, 나-친구-원수-원수는 친구의 친구지만, 내 친구가 될 수 없다. 실행 과정은 2번 조건인 원수의 ..

1. 문제 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 풀이 과정 - h = Math.ceil(log2(N)) - tree_size = 2^(h+1) *h가 0부터 시작하기 때문에, h+1승 해준다. 1. 세그먼트 트리 생성(초기화) public static long init(int node, int start, int end) { if(start==end) { tree[n..