모항이코딩한다

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.28 방문한 적 없는 배추가 발견될 때마다 필요한 지렁이 수를 1 증가시키고, 그 배추를 시작으로 인접한 배추들을 모두 방문해주면 된다. 다시 말하자면 정답을 저장할 int형 변수 answer을 선언한 뒤 0으로 초기화한다. 그 후 밭의 모든 칸에 대하여, (이번 칸이 배추임) AND (이번 칸을 방문한 적 없음) 이 true일 경우 answer을 1 증가시키고, 이번 칸에 대하여 dfs를 돌아준다. 코드 Java(2022.05.28) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringToke..

풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.07 오답노트 #24479 : 알고리즘 수업 - 깊이 우선 탐색 1 풀이방법 및 문제점 2022.05.27 지금까지 몇 개의 노드를 방문해왔는지 저장하는 변수 num을 전역변수로 설정하지 않고 재귀 시마다 넘겨주는 변수로 선언하였더니 틀린 답이 도출되었다. 이 점을 blowupmomo.tistory.com 그냥 시작 노드에 대하여 깊이우선탐색을 해주면 된다. 단! 한 정점에 여러 노드가 연결되어있을 경우 그 노드들을 오름차순으로 방문한다. 따라서 인접 리스트의 요소들이 오름차순으로 정렬되어있어야 한다. 이 점 때문에 나는 요소들을 자동으로 오름차순 정렬시켜주는 TreeSet를 사용했다. 코드 Java(2022.05.27) import java.io..

풀이방법 사용된 것: 깊이우선탐색 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가 작다면 이번 버섯의 값을 더..