전체 글
-
2020년 회고일상/끄적끄적 2021. 6. 24. 23:51
지금은 해가 바뀌고도 절반이 지난 2021년 6월 말이지만 내 길었던 한 해를 이제야 보내줄 수 있을 것 같아서 뒤늦은 회고를 해보려 한다. 나의 2020 제1 목표는 취업이었고 사실 취준이 전부였다. 말이 회고지 사실 험난한 취준기... 목표점검 19년도를 회고하면서 야심차게 세웠던 목표를 돌아봐야지 취업 아직은 인턴이지만 일단은..! 블로그 포스팅 100개 19년 회고 글부터 하면 약 230개 정도되는 것 같다. 앱 출시 개인앱 하나와 동아리에서 2개의 앱을 출시했다. RxSwift 시작하기 아직 초보지만 프로젝트 하나를 Rx로 했으니 일단 시작은 했다. TDD 도전 제대로 된 TDD까지는 아니지만 테스트를 경험했다. 책 10권 읽기 독서 스터디를 하면서 그래도 꾸준히 읽을 수 있었다. 22권 정도 ..
-
백준 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..