목록알고리즘 (89)
개발자 김수진
[문제] programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr [풀이] Union-Find 알고리즘을 사용해서 풀었다. (Union-Find 알고리즘 : https://tnwlswkd.tistory.com/33 ) 고객이 원하는 방이 아직 배정받지 않은 방이라면 해당 고객에게 배정해주고 map에 다음 칸의 방으로 초기화한다. 이미 배정받은 방이라면 Find 함수를 통해 해당 방을 기준으로 다음 방에서 비어있는 방을 찾아 배정해준다. 또한 배열이 아닌 맵을 사용한 이유는 k의 범위가 1 이상 10^12 이하이므로 배열을 사용하면 10^12 크기의 배열을 선언하여 메모리 부족이 발생하게 된다. 항상 Union..
[문제] www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net [풀이] 연속된 구간의 부분합을 구하는 문제이므로 투포인터 알고리즘을 사용해서 풀었다. (투포인터 알고리즘 : https://tnwlswkd.tistory.com/44 ) start부터 end까지의 부분합이 S 이상인 경우 구간의 길이를 구하고 start를 한 칸 뒤로 움직여서 구간의 길이를 좁힌다. 이 때 start와 end가 같다면 최소 구간이 되므로 1을 출력하고 끝낸다. 부분합이 ..
[문제] programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr [풀이] 반복문을 사용해 한 명씩 보내면서 구할 수 있다. 하지만 stones 배열의 길이가 200,000이므로 시간초과가 발생하여 효율성 부분에서 틀린다. 따라서 이분 탐색을 사용하여 찾아가는 방식으로 하였다. (이분탐색 정리 : https://tnwlswkd.tistory.com/112 ) stones 배열에서 left는 1, 가장 큰 값으로 right를 초기화 한다. 중간 값을 구해가면서 left, right 값을 조절하여 건널 수 있는 학생수의 최댓값을 찾는다. mid를 기..
[문제] programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr [풀이] 앞쪽에 위치한 원소일수록 집합에 가장 많이 포함되어 있어 따라서 원소가 나온 내림차순 횟수를 정렬하여 가장 많이 나타난 원소부터 answer에 insert [코드] #include #include #include #include using namespace std; bool cmp(pair a, pair b..
[문제] programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr [풀이] next_permutation 함수를 사용해 완전탐색으로 풀었다. 먼저 vector에 숫자와 연산자를 구분해서 담아줬다. 그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다. 우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식..
[문제] programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr [풀이] 1,4,7을 누를경우 왼손 3,6,9를 누를 경우 오른손 나머지는 현재 왼손, 오른손의 위치를 기준으로 가까운 손으로 누르도록 구현 만약 거리가 같다면 왼손잡이,오른손잡이인지 확인하고 이에 맞게 누르도록 [코드] #include #include us..
[문제] www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net [풀이] 보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제 무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해 ..
[문제] www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net [풀이] 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다. 단 공의 색깔이 같거나 공의 크기가 같다면 잡을 수 없다. 처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다. 하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다. 따라서 다른 방법을 생각했다. 먼저 공의 크기를 ..