모항이코딩한다

풀이방법 사용된 것: 이분 탐색 좌표압축 2022.06.08 간단한 코드로 풀리는 문제이지만, 좌표압축의 대표적인 예제이므로 좌표압축과 관련된 기본적인 내용까지 포함하여 자세하게 적었다. 단, 이분 탐색에 대한 설명은 적지 않았다. 이분 탐색에 대한 설명 및 좌표압축에 대한 매우 기본적인 이야기는 아래의 ICPC 강의 정리글에 있다. 관련된 신촌 ICPC 강의 정리글 초급 7회차 이분탐색 & 분할정복 이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임. 쪼갠다는 것은 무엇인가 문제의 크기가 크면 어렵다. 문제를 작은 부분 문제들로 나누어 풀면 쉬워진다. 문제를 쪼개고, 부분 문제들 blowupmomo.tistory.com 오답노트 #2370 : 시장 선거 포스터 풀이방법 및 문제점 2022.06.08..

풀이방법 사용된 것: 분할정복 재귀 2022.06.04 재귀적으로 정의된 분할정복 함수 solve를 사용하였다. solve는 한 변의 길이가 $2^n$인 정사각형 모양의 특정 영역을 맡아서, 자신이 맡은 영역의 한 변의 길이가 2라면, 그 영역에 들어있는 4개의 수 중 두 번째로 큰 값을 리턴한다. 반대로 자신이 맡은 영역의 한 변의 길이가 2보다 크다면, 영역을 동일한 4개 구역으로 쪼개어 그 4개 구역에 대한 재귀를 수행하여 결과값 4개를 받아온다. 그 후 그 결과값 4개 중 두 번째로 큰 값을 리턴한다. 코드 Java(2022.06.04) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

풀이방법 사용된 것: 브루트포스 알고리즘 사칙연산 2022.06.01 머리 쓰거나 똑똑하게 푸려고 하면 오히려 어렵다. 주먹구구식으로 하니 쉽게 풀렸다. 빈칸의 위치가 어디인지 찾아둔다. 빈칸을 제외한 모든 수에 대하여, 1 또는 3의 알맞은 가중치를 곱하여 모조리 더한다. 마지막 자리의 체크기호도 같이 더한다. 이렇게 싹 더해준 값을 sum이라 하겠다. (아래 코드에서는 빈칸 위치 찾기와 덧셈을 동시에 했다) 빈칸이 가중치 1의 위치라면 다음과 같이 풀면 된다. 0부터 9까지의 정수 i에 대하여 반복문을 돌리며, ( sum+i ) % 10 == 0 을 만족하는 수가 발견되면 그 수를 정답으로 취한다. 반대로 빈칸이 가중치 3의 위치라면 다음과 같이 풀면 된다. 0부터 9까지의 정수 i에 대하여 반복문을..

풀이방법 사용된 것: 깊이우선탐색(DFS) 너비우선탐색(BFS) 스택(Stack) 큐(Queue) 2022.06.01 기본적인 DFS와 BFS를 둘 다 사용해보는 스탠다드 문제이다. 스택을 이용해 DFS를 해주고, 큐를 이용해 BFS를 해주었다. 단, 방문할 수 있는 노드가 여러 개 있을 때엔 노드의 번호의 크기가 작은 것부터 방문한다는 점에 주의해야 한다. 이 때문에 스택에는 자식노드들을 내림차순으로 넣어주고, 큐에는 오름차순으로 넣어주었다. 인접 리스트의 내용물의 정렬은 TreeSet의 자동 오름차순 정렬과 desceningSet 기능을 이용하여 해결했다. 코드 Java(2022.06.01) import java.io.BufferedReader; import java.io.IOException; im..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.30 첫 칸부터 마지막 칸까지 훑으면서, 아직 방문하지 않은 칸에 대하여 그 칸을 시작점으로 그 칸과 같은 편인 칸에 대하여 dfs를 돈다. 그러면서 몇 칸을 방문했는지 센다. 해당 dfs가 끝나면 몇 칸 방문했는지 센 수를 제곱하여 정답에 더한다. 코드 Java(2022.05.30) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[][] map;//전쟁터 지도 static boolean[][] visited;..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.29 지도의 모든 칸에 대하여, 해당 칸에 집이 존재하고, 아직 방문한 적이 없는 칸이라면 그 칸을 시작점으로 삼아 dfs를 수행한다. dfs가 한 번 수행 될 때마다 이때 방문한 칸 수를 저장한다. 이 칸 수가 해당 단지의 집 개수이다. 개수들을 ArrayList에 차곡차곡 저장해준 뒤, (단지의 개수를 미리 알 수 없으므로 길이변경이 자유롭고 중복값을 허용하는 ArrayList를 사용하였다.) 모든 칸의 점검이 끝나면 이 개수들을 int[]에 옮겨 Arrays.sort로 오름차순 정렬한다. 이 값들을 화면에 출력해준다. 코드 Java(2022.05.29) import java.io.BufferedReader; import java.io.IOEx..

풀이방법 사용된 것: 누적합 2022.05.29 N+1 길이의 정수 배열을 선언한 뒤, 0번 인덱스에는 0의 값을 저장하고 그 후로 n번 인덱스에 n번째 수까지의 누적 합을 저장하는 방식으로 배열을 채운다. 셋째 줄부터 주어지는 숫자 i와 j에 대하여 (i번 인덱스에 저장된 수) - (j-1번 인덱스에 저장된 수) 가 정답이다. 코드 Java(2022.05.29) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws ..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.28 백준 2630번 색종이 만들기 문제와 매우 유사하다. 색이 2가지에서 3가지로 증가하였다는 점, 그리고 분할하는 영역의 개수가 4개에서 9개로 증가하였다는 점 이렇게 딱 두 가지만 달라졌다. #2630 : 색종이 만들기 풀이방법 사용된 것: 분할 정복 재귀 2022.05.18 분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다. 사용한 전역변수는 다음과 같이 3개이다. boolean[][] paper : 종이 정보. 파란색인 부분은 true, blowupmomo.tistory.com 코드 언어(2000.05.04) import java.io.BufferedReader; import java.io.IOException; import java.io..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.28 정답을 저장할 int형 변수 answer를 선언하고 0으로 초기화한다. 1번부터 N번까지의 모든 노드에 대하여, 아직 방문한 적 없는 노드일 경우 answer를 1 증가시키고 해당 노드를 시작점으로 삼아 dfs를 돈다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static ArrayList[] arr;//간선 정보 저장용 배열 static ..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.28 섬의 개수를 저장할 int형 변수 answer을 선언하고 0으로 초기화한다. 지도의 모든 칸에 대하여, 아직 방문한 적이 없는 섬 땅 부분이 발견될 때마다 answer를 1 증가시키고, 그 땅 좌표를 시작으로 dfs를 돌린다. dfs를 돌리면서 거쳐가는 모든 땅은 방문했다고 표시해준다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[][] map;//지도정보 stati..