전체 글
-
백준 1939 중량제한Algorithm/BOJ 2021. 3. 4. 17:06
출처: www.acmicpc.net/problem/1939 분류: 이분 탐색 접근방식 하 이번 문제도 너무 어려웠습니다... 설명이 애매해서 이해도 어려웠고 메모리제한............ ㅂㄷㅂㄷ 먼저 문제의 마지막에 " 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. " 라고 되어있어서 마지막에 주어진 두 섬으로 한 번에 가는 경우를 체크하는건가? 그럼 중간에 경로들은 왜 주어진거지? 문제가 좀 이상한데? 라고 생각했었습니다. 결국 여기서 말하는 한 번의 이동이란 처음 섬에서 특정 중량으로 출발시킨 짐이 목표 섬까지 도착하는 경로를 의미합니다. 중량을 기준으로 이분 탐색을 해서 각 중량으로 이동이 가능한지 체크해서 해결했습니다. var mostWeight = 0..
-
백준 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 정해서 이분탐색을 해야합니다. 다음에는 해당 거리를 최소 간격으로 해서 공유기를 설치할 수 있는지 없는지만 체크해주면 됩니다. 이건 일단 나중에 생각해보죠 :( 자 그럼 공유기 사이의 거리가 가장 짧은 경우는 어떤 경우일까요? 바로 옆집에 공유기를 ..
-
백준 13423 Three dotsAlgorithm/BOJ 2021. 3. 3. 15:05
출처: www.acmicpc.net/problem/13423 분류: 이분 탐색 접근방식 간격이 같은 점 3개가 몇 개나 있는지 찾는 문제입니다. 이 문제는 이분탐색을 사용한 n^2 * logN 과 n^2 의 두 가지 풀이가 가능합니다. 두 풀이 모두 기본적으로 주어진 점들은 정렬을 하고 시작합니다. 먼저 이분 탐색을 어떻게 사용하는지 살펴보겠습니다. 원리는 간단합니다! 점 2개를 선택하고 마지막 점이 있는지 없는지를 이분탐색으로 찾아줍니다. 점 2개를 선택해서 거리가 나왔다면 두 번째 점 + 거리 에 해당하는 점이 있는지 찾아주면 됩니다. 저는 이분탐색의 범위를 그냥 매번 0과 n-1 로 두고 시작했는데 두 번째 점까지는 선택하고 왔기 때문에 low의 범위는 좁혀주면 좀 더 효율적일 것 같아요! for ..
-
백준 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. 27. 14:04
출처: programmers.co.kr/learn/courses/30/lessons/72411 분류: 조합 접근방식 카카오 블라인드 2번 문제였습니다! 주어진 코스의 개수에 해당하는 조합을 모두 찾고 그 중에서 가장 많은 사람이 먹었던 메뉴들을 골라주면 됩니다. 여러 개라면 모두 넣어줍니다. 주어진 입력 범위가 그리 크지 않기 때문에 ( 20(orders) x 10(각 order의 최대 길이 ) x 10(course) x 10(각 course의 최대 길이) = 20000 정도?) 그냥 다 돌면서 조합을 찾아주고 필터해주면 됩니다. 조합을 찾는 방식은 어렵지않게 찾아볼 수 있습니다 :) 저는 각 코스 문자열의 인덱스를 돌면서 해당 인덱스를 추가해서 재귀, 추가하지 않고 재귀를 돌려서 만들었습니다. func..
-
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 =..