https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 난이도 : 골드4 태그 : 자료구조, 그래프 이론, 그래프 탐색, 분리 집합 설명 파티에 진실을 아는 사람이 포함되어 있으면, 그 파티에 참여한 사람들은 모두 진실을 알고 있다고 간주하고, 진실을 알고 있는 사람들이 하나도 포함되어 있지 않는 파티를 카운트하는 문제입니다. 문제 태그에도 명시되어 있듯이 그래프 탐색(DFS/BFS)를 통해서도 풀 수 있지만, 분리 집합 (Union - Find 알고리즘 이용)..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 태그 : 그래프 이론, 위상정렬 설명 누가 누구보다 더 앞선 우선순위를 갖고 있다는 사실만으로 정렬을 하는 위상정렬 문제입니다. 예를 들어 A, B, C, D, E. 5명의 사람을 키 순서대로 정렬하려 할때, 170cm, 180cm, 190cm, 160cm, 150cm 등으로 각 사람의 키가 주어지면 손쉽게 정렬 할 수 있겠지만, A는 B보다 작다. D, E는..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 백트래킹 설명 유명한 보드게임인 스도쿠를 기반으로 한 코테 문제입니다. 빈칸에 들어갈 수 있는 경우의 수를 하나씩 찾아 대입해보고, 최종적으로 결과값을 도출해내는 백트래킹 문제입니다. DFS를 사용하여 풀이하였습니다. 소스코드 입력값 세팅 import java.io.BufferedReader import java.io.InputStreamReader imp..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 백트래킹, 깊이 우선 탐색 설명 DFS를 사용한 백트래킹을 사용하여 풀 수 있는 문제 입니다. 아이디어 자체는 빨리 떠올랐는데, 시간초과 때문에 꽤 애먹었던 문제였습니다. 처음엔 방문한 좌표와 사용한 알파벳을 각각 체크하였는데, 생각해보니 사용한 알파벳만 체크해도 되더군요. 사용한 알파벳 역시 ArrayList로 했더니 시간초과가 나..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프이론, 플로이드 - 워셜 설명 문제의 제목처럼 플로이드 - 워셜 알고리즘을 이용해 해결할 수 있는 문제입니다. 플로이드 - 워셜 알고리즘의 기본격인 문제이니, 해당 알고리즘을 알고 계신다면 어렵지 않게 풀 수 있습니다. 저는 잘 몰라서 플로이드 - 워셜 알고리즘이 뭔지 찾아보고서야 풀었네요...ㅎㅎ 소스코드 값 입력과 테이블 준비 val br = BufferedR..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 비트마스킹 문제풀이 처음 문제를 봤을땐, 아 집합문제니 HashSet을 사용해 풀면 되겠구나! 라는 생각이 들어 별 문제 없이 코딩을 시작했습니다. import java.io.BufferedReader import java.io.InputStreamReader fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) val n = ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 난이도 : 실버1 태그 : 그리디, 정렬 설명 가장 많은 회의를 배정할 수 있도록 하는 문제입니다. 처음엔 회의 시간이 가장 짧은 것 부터 그리디 알고리즘을 이용하여 풀이하였는데, 생각해보니 (1,10) (9,11) (10, 20)의 경우 (1,10) (10,20)을 냅두고 (9,11)을 선택하게 되더군요. 그래서 끝나는 시간이 가장 짧은 순으로 그리디 알고리즘을 적용하였습니다. 소스코드 인풋값 저장 val n = readLine()!!.toInt() val arr = Array(n) { Array(2) { 0 ..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 난이도 : 골드5 태그 : 그래프탐색, 너비우선탐색, 그래프이론 설명 이전의 포스팅했던 백준 7576번 토마토는 한 층인 평면(x, y축)으로만 이루어졌던과 달리, 7569번 토마토는 복수의 층으로 입체(x,y,z)로 이루어져 있는게 차이점입니다. 이전 포스팅의 코드를 베이스로 약간 변형을 주어 3차원 BFS로 풀이할 수 있으며, 이전 포스팅의 내용이 궁금하신 분은 아래 링..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍 설명 정수 4를 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 으로 나타내는... 프로그램을 짜고 있었는데 뭔가 이상했습니다. 이 문제, 뭔가 실버3 같지가 않았습니다. 뭔가 쌔한 느낌을 받은 저는, 어... 이거 생각해보니 굳이 1, 2, 3으로 나타낼 필요까진 없네? 라는 것을 뒤늦게야 깨달았고, 아 이거 점화식이구나! 라는 생각이 마침내 떠올랐습니다. 그 즉시 각 항들을 구해보며 규칙성을 찾기 시작했습니다. a[1] = ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 좌표 상 각 블록(단지)의 개수가 몇개인지 판단하는 전형적인 그래프 탐색 (DFS / BFS) 문제입니다. 모든 점에 대해 DFS / BFS를 진행하며, DFS / BFS가 진행된 횟수를 카운트하면 됩니다. DFS 및 BFS 중 어느것을 사용해 풀이해도 무방하나, 이전 코테 포스팅에서 DFS는 많이 풀이..