문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 예상 집의 좌표 범위가 10억을 넘으므로 이분탐색을 통해서 범위를 줄여가야겠다고 생각했다. 가장 인접한 공유기 거리를 구하고 그 거리로 집 배열을 탐색하면서 C개 이상 설치가 가능한지 여부를 파악한다. 풀이방법 (접근 방법 & 시간복잡도) 1. 집의 위치를 배열에 넣고 오름차순으로 정렬한다. 2. start = 1, end = hous..
문제 https://www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 풀이 예상 각 주전자에서 몇으로 나눌지 조합해서 구하는 것은 K가 100만을 넘으므로 불가능 하다고 생각했다. 막걸리의 나눌 ml 수를 구하고 해당 수로 막걸리를 나눴을 때 몫의 합이 K 이상이면 된다고 생각해서 막걸리의 ml를 이분탐색으로 구하는 방법을 선택했다. 풀이방법 (접근 방법 & 시간복잡도) 1. 막걸리를 배열에 넣고, 총 막걸리 ml 를 구한다. 2. start = 0, end =..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX6PP9G6p1sDFAS9 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 진 횟수를 기준으로 생각하면 되는 문제 풀이방법 (접근 방법 & 시간복잡도) 1. 진 횟수를 카운트한다. 2. 진횟수가 8이상이라면 NO, 아니라면 YES를 출력한다. 시간복잡도 => O(N) import java.io.BufferedReader; import java.io.InputStreamReader; public class Solution { public static void..
문제 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 풀이 예상 처음엔 정렬을 하고 4개의 포인터로 풀어야 하나 해서 해봤는데 틀렸다고 나오길래 절망해서 다른 분들의 풀이를 참고했다. 참고한 방법은 정렬시키고, 2개의 눈덩이를 고정시켜 그 범위 안에서 다른 눈덩이를 고르는 것 이다. 풀이방법 (접근 방법 & 시간복잡도) 1. 눈덩이를 오름차순으로 정렬시킨다. 2. 눈덩이 2개를 for문으로 고정시킨다. i: 0~N..
문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 예상 투포인터를 이용한 풀이 풀이방법 (접근 방법 & 시간복잡도) 1. startPoint = 0, endPoint = N-1 에 두고 시작한다. 2. 합의 절댓값이 diff보다 작다면 answer에 해당지점을 갱신한다. 3. nums[startPoint] + nums[endPoint] 가 0보다 작다면 startPoint를 증가시키고 아니라면 endPoint를 감소시킨다. 시간복..
문제 https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 예상 조건이 굉장히 많은 구현 풀이방법 (접근 방법 & 시간복잡도) 1. 루돌프와 산타의 위치 배열(탐색할 때 맵을 보지 않고 이 배열만 보기 위해), 점수 배열, 탈락여부 배열, 기절 배열 생성 2. 루돌프 움직이기 2-1. 산타를 순회하면서 표적 산타를 찾는다.(표적 산타는,..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX4EJPs68IkDFARe SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 자릿 수 마다 개수를 저장할 배열을 만들어 저장하고 앞쪽에서 부터 바꿔야 할 숫자를 저장한 후, 바꿔야될 숫자면 뒤쪽에서부터 바꿀 숫자를 찾는다. 풀이방법 (접근 방법 & 시간복잡도) ex) 142857 - 작은 숫자 찾기 1. 각 자리의 숫자를 배열에 저장한다. nums[0] nums[1] nums[2] nums[3] nums[4] nums[5] nums[6] nums[7] num..
문제 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 풀이 예상 투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 1. isHave[] 배열에 해당 알파벳이 나오면 수를 증가시킨다. a(0), b(1), c(2), ... 2. count(알파벳 종류의 개수) 가 N개 보다 적다면 endPoint를 늘리고 처음 나온 알파벳이라면 count도 +1해준다. 3. count(알파벳 종류의 개..
