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

1. 문제 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 2. 풀이 과정 처음엔 앞에서부터 빈칸을 해당 개수만큼 비워두고 해당 값을 적는 형태로 작성했다. 하지만, 자기보다 큰 수의 개수를 가지고 있기 때문에, 반대로 큰 수부터 보면서 배열의 arr[i]번째에 넣어주는 방식으로도 구현할 수 있었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 2. 풀이 과정 최대한 원래 줄을 안 건드리고 새로 줄 세우는 방법이 가장 빠르다. 따라서 원래 줄 중에서 가장 긴 부분 수열(LIS, Longest Increasing Subsequence)을 찾으면 된다. 결괏값은 전체 아이들의 수인 N - 가장 긴 부분 수열의 길이가 된다. import java.io.BufferedReader; import java.io.InputStreamReader;..

문제 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 과정 MST문제로 풀이 방법은 Prim과 Kruskal 두 가지가 있는데, 간선의 개수가 많으므로 Prim을 선택하여 풀었다. 하지만, 아래의 메서드를 보면 거리 계산하는 함수에서 Math.pow를 쓰지 않고 곱셈을 쓰면 기본이 int형으로 계산되기 때문에 값이 정확히 측정되지 않아 통과하지 못한다. public static double getDistance(..

문제 https://www.acmicpc.net/problem/10472 10472번: 십자뒤집기 당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색 www.acmicpc.net 풀이 과정 데이터는 3x3으로 총 9개의 수가 주어지므로, int하나로 비트마스킹을 사용했다. 특정 상태까지의 최단 시간을 구하는 문제이므로 BFS를 사용했고 검은색은 1, 흰색은 0으로 비트마스킹해서 전체 값이 0이면 모두 흰색이므로 종료하도록 했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 2. 풀이과정 [방법 1] DFS + 새로운 배열 선언 방식 새로운 배열을 만들어서 DFS를 구현했다. 메모리는 많이 사용하지만, 메서드가 종료될 때 배열을 원상태로 되돌리지 않아도 돼서 빠르다. 마지막에 요소가 2개 남았을 때, 최대값을 업데이트해주고 종료한다. import java.io.BufferedReader; import java.io.InputStreamReader; i..

1. 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 2. 풀이과정 문제대로 구현하면 되는 문제이고, 톱니바퀴를 회전할 때는 배열의 모든 값을 오른쪽 혹은 왼쪽으로 움직이지 않고 시작 포인트만 변경해서 얼만큼 회전했는지 표현했다. 그리고 가장 왼쪽, 오른쪽의 값은 나머지 연산을 통해 시작에서 각각 2번째, 6번째에 떨어진 값을 반환하도록 했다. import java.io.BufferedReader; import java.io.Inpu..

1. 문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 풀이 과정 처음에는 간단하게 (해당 데이터에서 최대 길이) = (해당 데이터보다 작고 앞에 있는 것 중 가장 큰 값) + 1을 해서 이중for문으로 구현했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public stat..

1. 문제 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 2. 풀이 과정 처음에는 오는 방향에 따라 들어온 방향과 같으면 거울 수를 추가하지 않고, 들어온 방향과 다르면 거울 수를 추가해서 처리했다. PriorityQueue를 사용해서 사용한 거울 수가 작은 경로부터 처리해서 도착지가 나오면 종료했다. 코드는 아래에 [더보기]를 클릭하면 볼 수 있다. 더보기 import java.io.BufferedReader; import java..

1. 문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 2. 풀이 과정 [방법1] LinkedList + Iterator 처음에는 LinkedList를 사용해서 풀었다. LinkedList를 선택한 이유는 리스트 중간에 값을 삽입하고 삭제하는 과정이 빠르기 때문이다. 하지만 시간초과가 났다. 기존 코드에서는 커서가 있는 값을 index를 써서 해당 위치에 있는 값을 찾았기 때문에, LinkedList는 맨 처음 요소부터 index번째에 있는 ..

1. 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 과정 [방법1] PriorityQueue를 이용한 BFS 도착 지점이 출발 지점보다 작은 경우, 빼기만 해서 가는 것이 가장 빠르므로 N-K를 출력한다. 아닌 경우는 PriorityQueue를 써서, 현재 최소 경로인 값에 +1, -1, *2 를 해본다. 더보기 import java.io.BufferedReader; import java.io..