알고리즘
-
백준 17136 색종이 붙이기Algorithm/BOJ 2021. 3. 28. 19:14
출처: www.acmicpc.net/problem/17136 분류: 완전탐색 접근방식 가능한 색종이를 열심히 붙이면 되는 문제였습니다. 처음엔 크기가 5x5인 색종이부터 먼저 붙여나가는 방식으로 접근했는데 이렇게 되면 틀리더라구요.. 반례가 있나봅니다. 따라서 백트래킹으로 모든 경우를 찾아주는 방식으로 접근해야 합니다!! 그리고 이것도 단순히 크기가 1인 색종이부터 확인해나가면 모두 1인 칸일 경우에는 엄청난 연산이 필요하게됩니다. 크기 5부터 접근해서 찾고, 이미 찾은 최소 케이스보다 많이 사용하게되면 그 이상은 무의미하니 거기서 중단해주면 시간을 단축시킬 수 있습니다. 나머지는 단순 구현이라 코드를 보시면 어렵지않게 이해가 되실 것 같습니다 :) 해결방법 func solution() { typeali..
-
백준 1038 감소하는 수Algorithm/BOJ 2021. 3. 28. 16:47
출처: www.acmicpc.net/problem/1038 분류: 완전탐색 접근방식 n번째 감소하는 수를 찾는 문제였습니다. 한 자리 수는 모두 감소하는 수이며, 작은 수부터 찾아줘야 합니다. 감소하는 수는 이런 식으로 진행됩니다. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, 50, ... ] 규칙을 생각해보면 마지막 수는 마지막 앞자리 수보다 작아야 하니 앞자리 수가 4라면 마지막에 올 수 있는 수는 0, 1, 2, 3 이 됩니다. 그리고 마지막 자리를 제외한 수도 무조건 감소하는 수가 되어야 합니다. 감소하는 수 54 다음에 540, 541, 542, 543 이 올 수 있지만 44는 감소하는 수가 아니기 때문에 440,..
-
백준 2263 트리의 순회Algorithm/BOJ 2021. 3. 26. 16:19
출처: www.acmicpc.net/problem/2263 분류: 트리 접근방식 트리 순회 방법의 특성을 잘 이용해 해결했어야 하는 문제였습니다. 기억해야 할 특징은 다음과 같습니다. 1. post-order는 왼쪽 - 오른쪽 - 루트 순으로 탐색하므로 배열의 마지막은 루트노드가 됩니다. 2. in-order 는 root를 기준으로 왼쪽은 left, 오른쪽은 right 서브트리로 분리됩니다. post-order를 통해 root 노드를 찾았다면, in-order의 시작부터 root 까지가 왼쪽, 오른쪽으로 분리되고, 이를 통해 왼쪽, 오른쪽에 몇 개의 노드가 존재하는지 알 수 있습니다. 다시 in-order는 왼쪽 - 오른쪽 - 루트가 순서대로 배치되어 있기 때문에 개수를 통해 in-order에서 어디까지..
-
백준 5639 이진 검색 트리Algorithm/BOJ 2021. 3. 26. 14:19
출처: www.acmicpc.net/problem/5639 분류: 트리 접근방식 pre-order 결과가 들어오면 이 트리의 post-order 검색의 결과를 출력하는 문제였습니다. pre-order의 결과를 놓고 보면 첫 번째가 root, root+1 부터 처음으로 root보다 큰 값이 나오는 위치까지가 Left 그 다음이 Right 트리가 됩니다. 우리가 원하는 결과인 post-order는 왼쪽부터 탐색하기 때문에 루트를 타겟으로 이분탐색으로 UpperBounds를 찾아서 왼쪽 -> 오른쪽 -> 루트 를 반복적으로 돌려주면 원하는 결과를 얻을 수 있습니다. 처음엔 입력 받을 때마다 루트부터 위치를 찾아 트리를 만들어 나가는 방식으로 접근했었는데 이렇게 하니까 시간초과가 났습니다. c++로는 이런 식으..
-
백준 1068 트리Algorithm/BOJ 2021. 3. 25. 16:49
출처: www.acmicpc.net/problem/1068 분류: 트리 접근방식 전형적인 트리 문제였습니다. 주어진 대로 부모자식을 쭉 연결한 다음 dfs나 bfs 방식으로 탐색하다가 삭제해야 할 노드를 만나면 건너뛰는 방식으로 하면 해당 요구조건에 맞게 빠르게 해결할 수도 있으나 (많은 분들이 그렇게 푸신 것 같습니다.) 저는 실제 트리에 가깝게 해결해보고 싶어서 실제로 해당 노드와 그 자식 노드들을 제거해주는 방식으로 해결해봤습니다. 처음에는 Node, Tree 클래스를 각각 만들어서 처리해서 풀었다가 별도의 Tree 클래스 없이 루트노드만 가지고 해결하도록 개선해봤는데요, n만큼 임시 배열에 노드를 만들어두고 -1을 만나면 treeNode의 변수로 저장해두고 연결과 제거를 모두 끝내고 나면 임시 배..
-
백준 10819 차이를 최대로Algorithm/BOJ 2021. 3. 16. 13:20
출처: www.acmicpc.net/problem/10819 분류: 완전탐색, 순열 접근방식 n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다. 주어진 예제에서는 [8, 15, 1, 20, 4, 10] 경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ 순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고... 굉장히 비효율적으로 풀었었네요 ㅠㅠ 덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다. 앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로 바꿀 자리의 인덱스..
-
백준 16236 아기상어Algorithm/BOJ 2021. 3. 10. 18:08
출처: www.acmicpc.net/problem/16236 분류: BFS 접근방식 상어가 먹이를 찾을 수 없을 때가지 최단거리의 먹이를 찾아 bfs를 돌려주면 되는 문제였습니다. 기술적으로 크게 어려운 것은 없었으나... 익숙하지 않다면 구현에서 좀 애를 먹을 수 있을 것 같네요..! (후 힘들었습니다..) 같은 거리의 먹이들이 여러 개라면 요구사항대로 정렬을 해줘야 합니다! row 우선, 그다음 col로 ..! feeds.sorted(by: { $0.r == $1.r ? $0.c < $1.c : $0.r < $1.r}) 큐에서 DoubleStackQueue를 사용했는데 그냥 배열로 해서 removeFirst해도 통과가 가능한 것 같습니다. 해결방법 struct DoubleStackQueue { pri..
-
백준 12100 2408(easy)Algorithm/BOJ 2021. 3. 8. 15:03
출처: www.acmicpc.net/problem/12100 분류: 시뮬레이션 접근방식 바킹독님의 유튜브 강의를 참고했습니다. 최고 🥰 2048.. 하는 건 좋아했는데 막상 만들라고 하니 꽤 어려웠습니다. 하지만 항상 지나고 생각해보면 그리 어렵지 않습니다 💪 한 행만 잘 합칠 수 있다면 이걸 반복하고, 회전시켜서 간단하게 해결했습니다. 한 행 기울이기 먼저 한 행을 왼쪽으로 기울여서 합치는 걸 생각해보겠습니다. 저는 합쳐진 새로운 행을 만들어 나간다고 생각을 했는데요, 왼쪽으로 기울일거니까 합칠 배열의 인덱스를 0으로 두고 기존의 행을 돌면서 새로운 배열을 만들어 나갔습니다. 새로 만들어질 배열을 mixed, mixed의 현재 인덱스를 movingPoint 라고 해볼게요. mixed 를 기존 행의 크기..