모항이코딩한다

풀이방법 사용된 것: 깊이우선탐색 2022.06.09 3184번 문제와 완전히 똑같은 문제이다. 양이 'o'가 아닌 'k'로 표시된다는 것만 다르다. #3184 : 양 풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.25 그래프 탐색을 통해 각 영역에 속한 칸들을 탐색하고 양과 늑대의 마릿수를 세는 문제이다. 나는 깊이우선탐색을 사용하였다. 알고리즘은 다음과 blowupmomo.tistory.com 코드 Java(2022.06.09) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { s..

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

풀이방법 및 문제점 2022.06.08 (1) 이분탐색을 쓰지 않고 그냥 좌표압축을 시도해보았다. 해시맵을 사용하였다. 역시 시간초과가 발생한다. 답의 값 자체는 맞게 도출되는 것 같다. 2022.06.08 (2) 이분탐색을 이용하여 좌표압축을 하니 해결되었다. 정답 게시글 바로가기 코드 Java(2022.06.08(1)) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thro..

풀이방법 사용된 것: 분할정복 재귀 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 DFS는 본래 스택의 성질을 이용한 탐색법이다. 나는 재귀로 구현해왔지만, 사실 이것도 스택의 원리와 똑같다. 재귀라는 것은 시스템 상에 스택이 쌓이고 빠지면서 실행되기 때문이다. 스택을 사용하여 DFS를 하는 방법은 다음과 같다. 일단 시작 정점의 번호를 스택에 넣는다. 그리고 스택의 top에 있는 정점에 대하여 다음을 반복한다. 스택 top에 있는 정점이 이미 방문한 정점이라면 그냥 빼내서 버리고, 아직 방문하지 않은 정점이라면 빼냄과 동시에 그 정점의 자식들을 스택에 차곡차곡 쌓는다. 이 과정을 반복하다 보면 스택이 완전히 비는 시점이 온다. 그때는 모..

풀이방법 사용된 것: 깊이우선탐색(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 ..