전체 글
-
백준 2252 줄 세우기Algorithm/BOJ 2021. 1. 27. 22:16
출처: https://www.acmicpc.net/problem/2252 분류: 위상정렬 접근방식 위상정렬로 해결할 수 있는 문제였습니다 :) 특정 순서를 지켜야 하고 방향성 있는 그래프 일 때는 위상정렬!! 을 다시 한번 기억해야겠습니다. 해결방법 큐를 구현하긴 귀찮고 removeFirst도 사용하기 싫어서 큐 인덱스를 가리키는 변수를 하나 만들어서 FIFO를 구현해봤습니다 :) protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()!..
-
백준 13904 과제Algorithm/BOJ 2021. 1. 27. 13:56
출처: https://www.acmicpc.net/problem/13904 분류: 그리디 접근방식 그리디하게 점수가 높은 과제부터 배정해주는 방식으로 해결했습니다. 점수가 높은 과제를 마감일에 처리해주되 해당 날이 이미 배정되어 있다면 비어 있는 날을 찾아 그 전날에 배정해주는 방식으로 해결했습니다. 만약 1 30 2 40 2 50 주어졌다면, 점수가 가장 높은 2 50을 먼저 배정해주고 그 다음 높은 2 40을 배정해주려 하는데, 2일차는 이미 차서 그 전날인 1일차에 배정해주는 방식입니다. 이미 점수가 높은 순서대로 배정시키기 때문에 다 차있어서 배정할 수 없다면 그게 최선일거라고 판단했습니다. 해결방법 protocol Readable { func readSingleValue() -> String f..
-
백준 1300 K번째 수Algorithm/BOJ 2021. 1. 26. 14:53
출처: https://www.acmicpc.net/problem/1300 분류: 이분탐색 접근방식 풀이 자체는 그냥 이진탐색을 이용하면 돼서 그렇게 어렵지 않지만, 이진탐색으로 접근하기가 어려웠던 문제였습니다. 가장 첫 번쨰 접근은 오름차순으로 정렬했을 때 k번째 수라는 건, B[k] 의 원소보다 작거나 같은 수가 k-1개만큼은 있다는 의미가 됩니다. 그럼 B[k]의 원소가 될 어떤 수를 정하고 이 어떤 수보다 작은 수가 k-1개가 있는지 확인하면 됩니다. 문제는 어떤 수보다 작은 수가 몇 개인지 확인하는 방법입니다. 이 방법만 찾으면 이진탐색으로 어떤 수보다 작은 수의 개수가 k보다 작은지 비교해가며 찾아줄 수 있습니다. 어떤 수를 m이라고 했을 때 이 m보다 작은 수가 몇 개가 있는지는 어떻게 확인할..
-
Intrinsic Content Size, Content Hugging, Content Compression ResistanceiOS 2021. 1. 24. 14:44
개인적으로 공부하며 정리하는 블로그 입니다. 오류나 부족한 부분이 있을 수 있으니 감안하여 봐주시고 아낌없는 조언 감사드립니다 :D Intrinsic Content Size Intrinsic Content Size란 View의 콘텐츠(내용물)를 고려한 자연스러운 크기를 의미합니다. 하지만 모든 뷰가 Intrinsic Content Size를 갖고 있는 건 아닙니다. 그냥 UIView 같은 경우엔 기본적으로 내용이 없는 빈 뷰이기 때문에 intrinsic content size를 갖지 않습니다. 반면, UIButton 같은 경우 title을 포함해 약간의 패딩까지 가지고 있습니다. 표로 간단히 정리해보죠. View Intrinsic Content Size UIView, NSView Intrinsic Con..
-
백준 1339 단어 수학Algorithm/BOJ 2021. 1. 22. 14:43
출처: https://www.acmicpc.net/problem/1339 분류: 그리디 접근방식 기본적으로 글자를 체크하고 수를 만드는 방식은 글자를 키로하고 글자의 자리 수 배열(해당 문제에서 최대 8자리)을 만들어서 이 글자가 해당 자리수에 몇 번이 사용되었는지 체크했습니다. 그리고 이걸 가지고 수를 만드는 방식으로 접근했습니다. 이제 문제는 어떤 글자에 어떤 숫자를 할당할지 결정해야 합니다. 아마도 가장 일반적인 생각이자 실수하기 딱 좋은 가정은 가장 큰 자리 수의 숫자가 많은 글자에 가장 큰 수를 매칭시키는 것으로 생각할 수 있습니다. 아래 예를 생각해볼까요? AA BC " 가장 큰 자리에 A 와 B가 1개씩 있어서 동률이고, 그 다음에 A가 한 번 더 있으니 A에 가장 큰 수인 9를 할당하면 되..
-
백준 1806 부분합Algorithm/BOJ 2021. 1. 22. 11:43
출처: https://www.acmicpc.net/problem/1806 분류: 투포인터 접근방식 앞선 투포인터 문제와 거의 비슷했습니다. 이 문제도 전형적인 투포인터 방식으로 풀었습니다 :) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleValue() -> Int { return Int(readLine()!)! } func readArray(with separator: Character..
-
백준 2003 수들의 합2카테고리 없음 2021. 1. 22. 10:53
출처: https://www.acmicpc.net/problem/2003 분류: 두 포인터 접근방식 수열의 특정 구간의 합이 특정한 수가 되는 경우의 수를 구하는, 대표적인 투 포인터 문제입니다. 2개의 포인터를 둬서 하나는 합이 원하는 수보다 크거나 같으면, 다른 하나는 합이 원하는 수보다 작으면 움직여주면서 합을 계산해주면 됩니다:) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleVa..
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..