알고리즘 (18) 썸네일형 리스트형 백준 9663 백 트래킹 코틀린 백트래킹을 간단히 설명하자면 dfs 탐색에서 조건을 만족하는 부분만(깊이) 탐색한다고 생각하면 된다. 부모 노드의 자식 노드중 조건에 해당하지 않는 자식 노드가 있다면 그의 자식 노드들 또한 탐색하지 않는다. 가장 대표적인 문제가 n-queen문제이다. n x n의 체스판에 n개의 퀸이 서로를 공격하지 못하게 하는 문제이다. x o x x x x x o o x x x x x o x 위와 같이 퀸(o)이 서로 공격 못하는 경우의 수를 구하는 문제이다. 만약 퀸이(0.1)일 경우 다음 행에서는 같은 열과 대각선에 퀸을 놓을 수 없으므로 해당 부분을 자식으로 하는 경우를 제외한(백트래킹) 방법으로 탐색을 이어 나가면 된다. ex) 0 0,1 / / \ \ 1 1,0(x)1,1(x) 1,2(x) 1,3(o) /.. 백준 5582번 공통 부분 문자열 코틀린 lcs를 이용한 dp 문제이다. 두 문자의 길이에 따라 각각 i행과 j열로 이루어진 표를 만들고 i행의 문자와 j열의 문자가 같으면 값을 표시하면 된다. 현재 값이 같고(i, j) 대각선 위의(i-1, j-1) 값이 같은 경우면 문자가 연속 된 경우임으로 해당값(i-1, j-1)에 +1을 해주면 된다. (표를 그려보면 알 수 있다.) 코틀린으로 풀때 자꾸 메모리 초과가 나와서 실패 했는데.. Array(row) {Array{column} {0}} 으로 초기화 할 경우 0으로 초기화 하는 과정에서 메모리 문제로 실패하게 된다ㅠ fun main() { val word1 = readLine()!! val word2 = readLine()!! val row = word1.length + 1 val column .. 백준 1915 코틀린 일반적인 dp 문제와 다르게 점화식을 세워 푸는 풀이보다는 메모 라이징 특성을 이용하여 푸는 문제이다. 현재 좌표에 값이 1일 때 좌표의 왼쪽, 왼쪽 위, 위에 값이의 최솟값이 1이라면 2x2의 정사각형을 만들 수 있고 1의 값을 2로 대체해 주면(메모 라이징) 해당 좌표의 왼쪽, 왼쪽 위, 위에 값이 1이라는 사실을 알 수 있다. 이런 식으로 왼쪽, 왼쪽 위, 위에 값이의 최솟값이 2이라면 3x3의 정사각형을 만들 수 있다. ex) 0111 0122 0123 ex) 0011 0112 0122 따라서, 현재 좌표의 값이 1일 때 왼쪽, 왼쪽 위, 위에 값의 최솟값에 1을 더한 값이 현재 좌표에서 만들 수 있는 최대 크기의 정사각형이므로 좌표들의 값들 중 최댓값을 출력하면 정답이 된다. import kot.. 백준 2579 계단 오르기 코틀린 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net fun main() { val n = readLine()!!.toInt() val arr = IntArray(n+1) { 0 } val dp = Array(n+1) { IntArray(3) { 0 } } for (i in 1 until n+1) { arr[i] = readLine()!!.toInt() } dp[1][1] = arr[1] for (i in 2 until n + 1) { dp[i][1] = max.. 백준 1005 코틀린 위상정렬이라는 개념을 몰라 시간 초과로 실패한 문제다. 위상정렬은 단반향에(개수는 상관x) 순서가 정해진 문제에 사용된다. 보통 선행 정점을 가지지 않는 정점들을 q에 넣어 해당 정점이 가르키는 정점들을 순서로 진행 하는 알고리즘이다. fun main() { val t = readLine()!!.toInt() for (i in 0 until t) { val input = readLine()!!.split(" ") val n = input[0].toInt() val rules = Array(n + 1) { ArrayList() } val priceInput = readLine()!!.split(" ").map { it.toInt() } val degree = Array(n + 1) { 0 } for (j .. 백준 1202 코틀린 처음에 떠오른 방법은 정렬 후 그리디로 풀려고 했지만 시간초과가 나왔다. 시간초과 없이 해결하기 위해서는 트리 구조와 같은 우선순위 큐나 객체 참조 해쉬등을 이용하여 풀어야 되는 걸 알았지만 왜 그런지 오기가 생겨 처음 방법으로 계속 풀다가 계속 실패하고 결국 우선순위 큐를 이용하였다 ㅠ https://www.acmicpc.net/problem/1202 보석과 가방을 무게순으로 정렬한 다음 각 가방의 무게보다 같거나 작은 배낭을 value값 기준의 우선순위 큐에 넣어주고 이중 가장 값어치가 높은 보석을 꺼내 sum에 더해 준다.(가방에는 한개의 보석만 가능함으로) 그리고 우선순위 큐에 남아있는 보석들은 (가방을 무게순으로 정렬했기 때문에 다음 가방에 넣을 수 있는) 다음 추가되는 보석들과 같이 우선순위큐.. 백준 1043 코틀린 완전 탐색과 유니온 파인드 두가지 이상의 방식으로 풀이 가능한 문제이다. 제일 먼저 떠오른게 완전 탐색인데 dfs로 풀려면 각 참석자가 참가한 파티나 같이 파티를 참석한 사람들의 정보가 필요하여 그냥 while문과 set contains(big O (1))를 이용하여 완전 탐색 하여 구연하였다. fun main() { val first = readLine()!!.split(" ") val m = first[1].toInt() val second = readLine()!!.split(" ") val set = HashSet() var count = 0 val parties = ArrayList() val visited = arrayOfNulls(m) for (i in 1 until second.size) .. 백준 1068 코틀린 문제를 잘 못 읽어서 애를 먹었다. 하나의 노드에 여러개의 자식노드가 존재 가능하고(이진으로 착각ㅠ) 부모노드의 자식이 하나인데 삭제 되었을 경우 부모 노드 또한 카운트에 속하는 경우를 체크해야 한다. remove 이후로는 탐색을 안하기 위해서 작성한 건데 급박한 시험의 경우 그냥 삭제를 해버리고 노드를 재탐색 하는게 좋을 것 같다. var count = 0 val list = ArrayList() fun main(args: Array) { val n = readLine()!!.toInt() val arr = readLine()!!.split(" ") val remove = readLine()!!.toInt() var root = 0 for (i in 0 until n) { list.add(Node(i .. 이전 1 2 3 다음