algorithm
-
[Programmers] 스티커 모으기(2)Algorithm/Programmers 2021. 10. 24. 14:45
출처: https://programmers.co.kr/learn/courses/30/lessons/12971 분류: dp 접근 배열의 길이도 100,000 으로 크고 이 스티커를 뗄지 안 뗄지, 앞에껄 땠는지 안 땠는지 등등의 경우를 고려해줘야 하니 DP로 문제로 접근을 했어요. 그냥 배열의 첫 번째를 기준으로 잡으면, 이 스티커를 땔 경우 DP vs 떼지 않을 경우 DP 두 번의 DP를 구해서 최대를 구하면 되는 문제였네요 처음에 저도 이렇게 접근은 했는데 첫 번째 인덱스부터 DP, 마지막 인덱스부터 거꾸로 DP 라는 엉뚱한 풀이로 해서.. 꽤나 삽질을 했습니다 😰 풀이 일단 각 케이스의 0, 1번 기저 사례를 구해주고 2번 인덱스부터 점화식으로 적용해주면 됩니다. (사실 n이 3일 때는 하나밖에 땔 ..
-
백준 1261 알고스팟Algorithm/BOJ 2021. 6. 14. 15:41
출처: https://www.acmicpc.net/problem/1261 분류: BFS, 다익스트라 접근방식 0은 그냥 통과, 1이 있는 칸은 벽을 부수면서 목적지까지 갈 때 최소한 몇 개의 벽을 부숴야하는지 찾는 문제였습니다. dist 배열을 두고 최소 비용을 갱신해주면서 BFS 탐색을 해주는 방식으로 해결했습니다. 해결방법 let mn = readLine()!.split(separator: " ").map { Int(String($0))! } let (m, n) = (mn[0], mn[1]) let delta = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() for _ in 0..= 0, nr = 0, nc < m else { con..
-
백준 1941 소문난 칠공주Algorithm/BOJ 2021. 6. 6. 16:50
출처: https://www.acmicpc.net/problem/1941 분류: brute force 접근방식 처음엔 그냥 bfs, dfs로 풀 수 있겠거니 했으나.... 점점 어라? 어라..? 어라....????!! 하며 쉽지 않았던 문제였습니다. 중복을 어떻게 줄여줘야할지 도통 감이 오질 않더라구요.. 결국은 다음와 같은 과정으로 해결했습니다. 1. 각 칸을 0~24로 두고, 0~24 중 7개를 선택하는 조합을 구한다. (약 48만개) 2. 조합에서 S가 4명 이상인지 확인한다 3. 조합이 모두 인접해있는지 확인한다. 1, 2번까지는 어렵지 않게 구할 수 있을 거 같은데 3번이 살짝 까다롭네요. 3번은 만든 조합의 0번부터 시작해 인접한 수가 조합안에 있는지 확인하고 queue에 담아주면서 탐색하는 ..
-
백준 2668 숫자고르기Algorithm/BOJ 2021. 6. 4. 23:05
출처: https://www.acmicpc.net/problem/2668 분류: 그래프, dfs 접근방식 1~n 까지에 각각 숫자가 매겨져 있을 때, 매겨진 숫자와 자신의 숫자의 집합이 같아지도록 최대한 많이 뽑아내는 문제입니다. 1~n을 노드 자신의 인덱스로, 매겨진 숫자를 다음 노드를 가리키는 그래프로 생각해보면, 결국 자기 자신으로 돌아오는 사이클이 아니면 절대 같은 집합이 될 수 없다는 걸 알 수 있습니다. 이렇게 각 사이클들을 더해주면 끝입니다 :) 전체 defaultVisit과 방문하면서 체크할 visit 배열을 만들어두고 탐색해서 사이클이 생겼다면 해당 visit을 defaultVisit으로 업데이트 시켜주는 방식으로 구현했습니다. for i in 0.. 0 { defaultVisit = v..
-
백준 13335 트럭Algorithm/BOJ 2021. 6. 4. 15:29
출처: https://www.acmicpc.net/problem/13335 분류: 구현, 시뮬레이션 접근방식 어떻게 하면 똑똑하게 풀 수 있을지 고민이 되었던 문제네요.. 결국 시간을 1초씩 늘리면서 매 시간 진입, 나갈 수 있는 트럭을 체크해주면서 해결했습니다. 매 시간 늘리지 않고 의미있는 시간 단위로 체크하면서 처리하고 싶었는데... 잘 모르겠네요 😢 말씀드렸다시피 매 시간 체크를 해주기 위해 현재 시간, 다음 진입해야 할 트럭, 현재 다리 위에 달리고 있는 트럭, 다리의 무게, 각 트럭의 끝나는 시간을 기록한 배열 등을 정의했습니다. 풀이는 간단합니다. 더이상 기다리고 있는 트럭이 없을 때까지 반복하는데요, 현재 시간에 끝나는 트럭이 있는지 먼저 확인해서 빼주고 다음 트럭이 진입할 수 있는지 체크..
-
백준 2250 트리의 높이와 너비Algorithm/BOJ 2021. 6. 4. 14:26
출처: https://www.acmicpc.net/problem/2250 분류: 트리, 중위순회 접근방식 너비가 가장 큰 높이를 구해야하는 문제였습니다. 문제의 그림이 힌트를 주고 있는데요, 가장 왼쪽 노드부터 x가 하나씩 증가하고 있습니다. 중위 순회를 하면 "왼쪽 -> 루트 -> 오른쪽" 순서로 방문하기 때문에 이 순서가 곧 x가 1인 노드부터 차례대로 방문하는 순서입니다. 이 부분까지 이해가 됐다면 구현만 해주면 되는데요! 저는 그냥 중위순회에서 다 처리해버렸습니다. 전역적으로 사용하는 x값을 가지고 다니면서 노드에 넣었으면 1 증가시키는 방식으로 x를 처리했구요 해당 레벨의 최대, 최소 x값을 넣는 배열을 전역적으로 만들어 놓고 최대 최소를 업데이트 시켜줬습니다. func markWhileInOr..
-
백준 1094 막대기 (비트 개수 세기)Algorithm/BOJ 2021. 6. 3. 15:31
출처: https://www.acmicpc.net/problem/1094 분류: 비트마스킹 접근방식 주어진 문제의 조건을 맹목적으로 따라서 풀 수도 있지만, 조건을 해보면 결국은 주어진 x를 몇 개의 2의 배수를 사용해 만들 수 있느냐 하는 문제입니다. 다시 생각해보면 "x를 이진수로 만들었을 때 1이 몇 개냐" 라는 말과 같은 말이라는 걸 알 수 있습니다 :) 따라서 이진수에서 1이 몇 개인지 세는 방법을 알아보겠습니다. 2로 나누기 우선 비트 연산을 하지 않는다면 주어진 수를 x로 나눠가면서 셀 수가 있겠네요. 중학생(?)때 배우는 10진수를 2진수로 바꿀 때 나눠가면서 나머지를 세는 바로 그 방식입니다. while x > 0 { bitCount += x % 2 x /= 2 } >> 1 2로 나누는 ..
-
백준 2056 작업Algorithm/BOJ 2021. 6. 3. 13:32
출처: https://www.acmicpc.net/problem/2056 분류: 위상정렬 접근방식 나보다 먼저 수행되어야 할 작업이 필요한 위상정렬에 관한 문제였습니다 :) 각 작업을 Node로 정의해서 나보다 먼저 수행되어야 할 작업들을 진입차수, inDegree 내가 끝나길 기다리고 있는 작업들을 nextTasks로 가지고 있도록 만들었습니다. 내가 수행하는 데 걸리는 시간을 workingTime 그리고 자신이 끝나는 시간 endTime을 가지고 있도록 했습니다. (우선 초기값은 workingTime이고 내가 기다리던 작업이 끝날 때마다 업데이트 시킵니다.) inDegree가 0인 작업들은 바로 시작이 가능하므로 큐에 담아서 실행시키고, 작업이 끝나면 기다리던 노드로 가서 inDegree를 줄이고 n..