Swift
-
백준 7453 합이 0인 네 정수Algorithm/BOJ 2021. 3. 4. 14:53
출처: www.acmicpc.net/problem/7453 분류: 투 포인터, 이분 탐색 접근방식 4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다. 이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다. a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab, c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd 를 만들고 둘 모두 오름차순으로 정렬해줍니다. 다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다. ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다. sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다..
-
백준 2110 공유기 설치Algorithm/BOJ 2021. 3. 3. 20:52
출처: www.acmicpc.net/problem/2110 분류: 이분 탐색 접근방식 이분 탐색 문제인 걸 알고 접근했는데도 접근이 어려웠던 문제였습니다. ㅠㅠ 이녀석 쉬워지질 않네요... 공유기들의 위치가 주어지기 때문에 이걸 가지고 어떻게 이분탐색을 해야하나 싶지만, 저희는 공유기 사이의 거리가 가장 큰 경우를 찾아야 합니다. 따라서 공유기 사이의 거리를 가지고 이분 탐색을 돌려야 합니다. 따라서 저희는 최소 설치 거리를 low 최대 설치 거리를 high 정해서 이분탐색을 해야합니다. 다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :( 자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요? 바로 옆집에 공유기를 ..
-
백준 15810 풍선 공장Algorithm/BOJ 2021. 3. 3. 00:17
출처: www.acmicpc.net/problem/15810 분류: 이분탐색 접근방식 스태프 한 명이 만들 수 있는 풍선의 개수는 시간 / 걸리는 시간 으로 구해줄 수가 있고 특정 시간에 만들어진 풍선의 개수는 해당 시간에 각 스태프가 만들 수 있는 풍선의 개수를 모두 더해 구할 수 있습니다. 이제 최대 걸리는 시간을 특정할 수 있다면 각 시간에 원하는 풍선 개수를 넘거나 같은 시간을 찾아 이분 탐색으로 반씩 잘라가며 찾을 수 있습니다. 처음으로 풍선의 개수를 넘거나 같은 시간을 찾아야 하기 때문에 이분탐색 lower bounded 로 풀어줬습니다. 마지막으로 최대 걸리는 시간(High)을 정해줘야 합니다. 처음에는 staff의 최대 범위가 1000000이여서 적당히 원하는 풍선의 개수 * 1000000..
-
Programmers Lv2) [2021 카카오블라인드] 신규 아이디 추천Algorithm/Programmers 2021. 2. 22. 13:38
출처: programmers.co.kr/learn/courses/30/lessons/72410 분류: 문자열 접근방식 친절하게 단계별로 요구사항을 제시해주고 있기 때문에 주어진 대로 열심히 구현하면 되는 문제였습니다! 문자열을 다루는 문제이니 만큼 굉장히 다양한 풀이들이 있더라구요. 문자열을 연습하기 아주 좋은 문제였던 것 같아요. 각 단계별로 가능한 다양한 풀이를 생각해보면서 정리해보고자 합니다. 우선 다른 분들의 풀이를 보면 그냥 solution 함수에 다 때려박아(?)서 구현하신 분도 있고 함수를 나누신 분도 계시고 extension 으로 처리해서 더 깔끔하게 푸신 분들도 계시던 것 같아요. 편한대로 풀면 되겠지만 실전이라면 여기서 너무 시간을 오래 끌지 않도록 익숙하고 빠르게 풀 수 있는 방법으로..
-
백준 1149 RGB 거리Algorithm/BOJ 2021. 2. 19. 15:32
출처: https://www.acmicpc.net/problem/1149 분류: DP 접근방식 dp 문제임은 알았지만 결국 풀지 못하고 다른 분들의 풀이를 참고했습니다 ㅠㅠ 처음에는 r, g, b에서 시작한 dp 3개를 다 채우면 되지않을까 생각을 했는데 이렇게 하면 두 색의 비용이 같거나 하는 등의 여러 예외들을 처리해줄 수가 없게됩니다 ㅠㅠ 기존에서 사고를 좀 더 열어 생각해보면 각 집이 모두 r, g, b로 칠해질 수 있는 경우를 생각해보면 쉽게 접근할 수 있습니다 :) 일반적인 1차원 배열이 아니라 [집의 개수][3] 크기의 2차원 배열을 채워나가는 방식으로 접근하면 쉽게 해결할 수 있었습니다. 해결방법 let numberOfHouse = Int(readLine()!)! var colorSet =..
-
백준 2961 도영이가 만든 맛있는 음식Algorithm/BOJ 2021. 2. 19. 14:04
출처: https://www.acmicpc.net/problem/2961 분류: 재귀 접근방식 N이 1 ~ 10 으로 아주 작아서 백트래킹으로 모든 조합을 다 계산해서 풀 수 있었습니다. 처음에는 뭐에 홀렸는지 단순히 이중 포문으로 모든 경우를 다 체크할 수 있지 않나? 라고 생각했었네요... 단순히 이렇게 하면 중간을 건너뛴 1, 3 같은 조합은 체크할 수가 없겠죠 ㅠㅠ s는 곱이고 b는 합이기 때문에 초기값으로 1, 0을 넣고 시작해줬습니다. 처음을 안 넣었을 경우는 계산하면 안 되기 때문에 각 케이스에서 재료를 넣어서 새롭게 만든 조합의 차만 생각을 해줬습니다. 해결방법 let n = Int(readLine()!)! var flavors = [[Int]]() for _ in 0.. abs(newS-..
-
백준 1074 ZAlgorithm/BOJ 2021. 2. 18. 12:28
출처: https://www.acmicpc.net/problem/1074 분류: 재귀 접근방식 백준 1992 쿼드트리 와 비슷한 문제였습니다. 대신 쿼드트리처럼 전부 방문하면 시간 제한에 걸리게 되기 때문에 어느 사분면에 포함되는지 체크해서 해당 분면만 재귀적으로 호출해줘야 합니다. 방문의 순서는 알고 있기 때문에 해당 사분면에 가능한 방문의 범위도 알 수가 있습니다. 4x4 배열이라면 각각 0~3, 4~7, 8~11, 12~15 사이의 값이 오겠죠? 이를 이용해서 방문 가능한 카운트 범위도 같이 넘겨주면서 해결했습니다. 해결방법 import Foundation extension Int { func pow(_ n: Int) -> Int { var powered = 1 (0..
-
백준 1992 쿼드트리Algorithm/BOJ 2021. 2. 18. 11:20
출처: https://www.acmicpc.net/problem/1992 분류: 재귀 접근방식 사각형의 영역을 1, 2, 3, 4분면씩 쪼개서 재귀로 풀 수 있는 문제였습니다. 고민하다가 잘 모르겠어서 다른 분들 풀이를 참고해서 풀었네요 ㅠ-ㅠ 처음엔 포문을 먼저 돌려서 모두 1인지 0인지 체크하는 방식으로 풀었는데, 다른 분들의 풀이를 보니 어차피 재귀로 돌릴거라면 먼저 체크하지 않아도 결과를 가지고 확인해서 풀 수도 있네요! 해결방법 처음 풀이 포문으로 전부 0인지 1인지 체크, 아니라면 compression func compress(size: Int, at point: Point) -> String { guard size != 1 else { return String(map[point.r][poin..