모항이코딩한다

풀이방법 사용된 것: 깊이우선탐색 2022.05.25 모든 정점에 1 혹은 2 중에 하나의 번호를 부여해야 한다고 하자. 인접한 두 정점이 같은 번호를 부여받는 일 없이 모든 정점에 1 혹은 2를 부여할 수 있다면 그 그래프는 이분 그래프이다. 더보기 여러 칸으로 나누어진 그림을 2가지 색으로만 색칠하되, 인접한 칸끼리는 색이 겹치지 않도록 하는 색칠 수수께끼와 비슷하다고 보면 된다. 이 원리를 이용하여 이 문제를 풀 수 있다. 그 방법은 다음과 같다. 정점들을 깊이우선탐색 또는 너비우선탐색하면서, 다음 정점으로 넘어갈 때마다 이전에 방문했던 정점과 다른 번호를 부여한다. 그 후 정점들을 검사해보았을 때, 인접한 두 정점이 같은 번호를 부여받은 경우가 하나도 없다면 이 그래프는 이분 그래프이다. 코드 J..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.25 그래프 탐색을 통해 각 영역에 속한 칸들을 탐색하고 양과 늑대의 마릿수를 세는 문제이다. 나는 깊이우선탐색을 사용하였다. 알고리즘은 다음과 같다. 마당의 특정 한 칸을 시작으로 깊이우선탐색을 하면, 그 칸과 같은 영역에 속하는 모든 칸을 한 번씩 방문할 수 있다. 이 과정에서 그 영역의 양과 늑대의 마릿수를 세어주면 된다. 이러한 과정을 마당의 모든 칸에 대하여 수행하면 문제가 해결된다. 다음은 코드 설명이다. 사용된 전역변수는 다음과 같다. static int r, c;//마당의 크기(r은 행, c는 열 개수) static char[][] map;//마당 지도 static boolean[][] visited;//방문여부 판별 static i..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.19 전체가 '-'로만 채워진 문자열을 먼저 만들고, 함수 f가 특정 부분을 지우는 식으로 해결한다. 재귀적으로 정의된 함수 f는 다음과 같이 동작한다. 주어진 문자열을 세 부분으로 동등하게 쪼갠다. 주어진 문자열의 가운데는 지운다. 주어진 문자열의 왼쪽과 오른쪽에 대하여는 재귀를 한다. 따라서 갈수록 더 짧은 부분에 대하여 재귀를 해나가게 된다. 주어진 문자열의 길이가 1이 되었을 때가 base case이다. 이때 재귀를 종료한다. 코드 Java(2022.05.19) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java..

풀이방법 사용된 것: ArrayList 2022.05.20 출력해야 하는 점의 x좌표와 y좌표는 세 번의 입력 중 단 한 번만 나온다. 두 번 나오는 값은 무시하고 딱 한 번 나온 x좌표와 딱 한 번 나온 y좌표를 출력하면 된다. ArrayList를 x좌표를 위한 것 하나, y좌표를 위한 것 하나를 만든다. 3개의 좌표값을 읽어오면서 처음 나온 값은 ArrayList에 저장을 하고 두 번째 나온 값은 ArrayList에서 지운다. 그럼 세 좌표값을 모두 읽은 후에는 각각의 ArrayList에 값이 하나씩만 남는다. 그 값들이 정답이다. 코드 Java(2022.05.20) import java.io.BufferedReader; import java.io.IOException; import java.io.I..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.18 분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다. 사용된 전역변수는 char[][] print : 출력할 별 그림 이렇게 하나이다. 사용된 함수 star()의 구조를 간단히 설명하자면 다음과 같다. 함수 star() 개요 star()은 특정 영역에 대하여, 영역의 한 변의 길이가 3이라면 해당 영역에 3x3짜리 별 그림을 직접 찍고, 영역의 한 변의 길이가 3보다 크다면 재귀를 수행하는 함수이다. 매개변수 int row : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 열 좌표 int col : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 행 좌표 int len : star()에서 다룰 영역의 한 변의 길이 작..

풀이방법 사용된 것: 분할 정복 재귀 2022.05.18 분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다. 사용한 전역변수는 다음과 같이 3개이다. boolean[][] paper : 종이 정보. 파란색인 부분은 true, 하얀색인 부분은 false로 저장한다. int answer_w : 첫 줄에 출력될 정답. 완성된 하얀 색종이의 개수를 저장한다. int answer_b : 둘째 줄에 출력될 정답. 완성된 파란 색종이의 개수를 저장한다. 먼저 종이 정보를 읽어오고, answer_w와 answer_b를 0으로 초기화시키고, 함수 cut()을 수행하고, answer_w와 answer_b를 출력하면 된다. cut()의 구성은 다음과 같다. 함수 cut() 개요 cut()은 주어진 영역의 색이 통일되어..

풀이방법 사용된 것: HashSet 2022.05.16 해시셋을 사용하였다. 집합 A의 원소들을 읽어와 해시셋에 저장한다. 집합 B의 원소들에 대하여, 해시셋에 이미 들어있는 수라면 해시셋에서 해당 수를 제거한다. 해시셋에 없는 수라면 해시셋에 새로 추가한다. 위의 과정이 끝난 후, 해시셋의 크기를 화면에 출력한다. 코드 Java(2022.05.16) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { public static void main(Str..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.12 버섯을 앞에서부터 먹어가며 계산한다. 이번 버섯을 먹었을 때의 총합이 100보다 작은 경우에는 무조건 먹는 것이 이득이므로 먹고 넘어간다. 이번 버섯을 먹었을 때의 총합이 100 이상인 경우가 처음 등장했을 때 답을 출력해야 한다. 다음과 같은 과정을 통해 답을 결정한다. 이번 버섯을 먹었을 때 총합이 100보다 얼마나 큰지 그 차를 변수 A에 저장한다. 이번 버섯을 먹지 않을 때 총합이 100보다 얼마나 작은지 그 차를 변수 B에 저장한다. 그리고 A와 B를 비교한다. A보다 B가 작다면 이번 버섯의 값을 더하지 않은 총합 (이번 버섯을 먹지 않았을 경우의 총합)을 화면에 출력하고 프로그램을 종료한다. B보다 A가 작다면 이번 버섯의 값을 더..

풀이방법 사용된 것: 백트래킹 2022.05.10 백트래킹 문제이다. 아래의 정답 코드는 가지치기 없이 모든 경우의 수를 다 검사하도록 하였고 이렇게 해도 시간초과가 나지 않기 때문에 브루트포스 알고리즘 문제라고도 할 수 있다. 가능한 모든 순열을 만들면서, 새 순열이 만들어질 때마다 하나씩 세어준다. 세다가 그 숫자가 문제에서 주어진 번호(N)에 도달하면 그 번호의 순열을 출력 문자열에 추가하면 된다. 주어지는 글자들이 사전순으로 주어지므로, 입력 문자열의 앞에 있는 글자부터 하나씩 순서대로 순열에 추가하는 식으로 순열을 만들면 된다. 그럼 결과물인 순열들도 자연스럽게 사전순으로 앞에 있는 것부터 순서대로 도출된다. "No permutation"을 출력해야 하는 유일한 경우는 바로 문제에서 주어진 번호..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.10 다 비교하면 된다. 알고리즘은 다음과 같다. 일단 그림 정보를 읽어온다. 그림의 색이 두 가지 뿐이므로 boolean 배열로 저장했다. 그 다음 비교를 한다. 필요한 변수는 min, a, b이다. int형 변수 min을 선언하고, 35보다 큰 수로 초기화한다. 정답에 해당하는 두 그림의 번호를 저장할 int형 변수 a와 b를 선언하고, 음수로 초기화한다. 그리고 가능한 모든 쌍에 대하여 다음의 과정을 반복한다. 두 그림을 선택한다. 두 그림을 비교하여, 서로 다른 칸의 개수를 센다. 서로 다른 칸의 개수를 담은 변수를 temp라 하겠다. min과 temp를 비교한다. min보다 temp가 작다면 min의 값을 temp로 업데이트하고, 방금 센 ..