개발 일기 개발 일기

https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 처음으로 풀어본 구현 유형의 문제였다. 단순히 이차원배열을 생각하고 하나 하나 노드를 이동하면서 풀이를 생각했다. 문제는 통과했지만 다른 사람들의 풀이를 보고 구현 유형의 문제는 나처럼 푸는게 아니구나 느꼈다. 규칙성을 찾고 그걸 코드로 구현하는게 중요해 보인다. 내가 짠 코드는 아래와 같다. package baekjoon import java.io.BufferedReader import java.io.InputStreamReader fun main() = with(BufferedReader(InputStreamReader(Sy..

https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net dfs를 이용하여 모든 카드 경우의 수를 구했다. import java.io.BufferedReader import java.io.InputStreamReader var graph = mutableListOf() var visited = booleanArrayOf() val resultList = arrayListOf() var n = 0 var k = 0 fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { n = read..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 목표가 정해져있지 않는 최단거리 문제이다. 모든 지점마다 bfs를 돌리고 최대값을 return 하는 방식으로 접근했다. bfs를 돌 때마다 visited 배열을 false로 초기화한다. import java.io.BufferedReader import java.io.InputStreamReader import java.util.LinkedList import java.util.Queue import ..

https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 평범한 bfs 문제이다. Queue를 이용한 bfs에서는 Queue에 넣는 순간 방문처리를 해야 시간초과를 피할 수 있다. import java.io.BufferedReader import java.io.InputStreamReader import java.util.LinkedList import java.util.Queue var graph: Arra..

https://www.acmicpc.net/problem/21937 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 역방향으로 시작해 방문한 노드의 갯수만 세어주면 된다. dfs를 돌때마다 방문 처리를 하고 count를 return 한다. 처음 방문도 count를 세므로 출력전 -1을 해준다. import java.io.BufferedReader import java.io.InputStreamReader var graph: Array = arrayOf() var visited = boolea..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 처음에는 그래프를 이용한 dfs로 풀어야 하나 생각했으나 단순 반복문으로도 풀이가 가능해 보여서 간단하게 풀었다. 단순하게 for문을 돌려 모든 경우의 수를 구했다. 각 사람의 친구를 먼저 탐색하고 친구의 친구도 탐색해서 visited 배열에 저장한다. 자기 자신은 친구로 인정되지 않기 때문에 마지막에 자신을 false 처리하고 count 값을 구한다. import java.io.BufferedRea..