목록분류 전체보기 (104)
개발자 김수진
문제 https://programmers.co.kr/learn/courses/30/lessons/82612?language=cpp 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 풀이 단순 반복문 사용해서 최종 금액 구하는 문제 가지고 있던 금액의 범위가 1부터 1,000,000,00 까지 이므로 long long 사용 ( int형 범위 -2,147,483,647 to 2,147,483,647 ) 코드 using namespace std; long long solution(int price, int..
[문제] programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr [풀이] 특별한 알고리즘을 사용해서 해결해야되는 문제일줄 알았는데 내가 가장 많이 다루었던 DFS 알고리즘을 사용해 해결하는 문제라는게 놀라웠다. 한..
[문제] 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을 출력하고 끝낸다. 부분합이 ..
[개념] 이분탐색이란 탐색기법중 하나로 중간값을 기준으로 탐색 범위를 절반씩 줄여가며 탐색한다. 따라서 처음부터 끝까지 모두 탐색하는 기법은 worst case의 경우 시간복잡도가 (O(N))이다. 하지만 이분탐색의 경우 탐색범위를 절반씩 줄여나가기 때문에 O(logN)으로 완전탐색보다 빠르다. 1. 탐색하고자 하는 배열은 이미 정렬이 되어있다. 2. left, right 값을 통해 중간값인 mid 값을 구한다. 3-1. 찾고자하는 값이 mid 위치에 존재하는 값보다 클 경우 , left를 mid 뒤로 옮긴다. 3-2. 찾고자하는 값이 mid 위치에 존재하는 값보다 작을 경우 , right를 mid 앞으로 옮긴다. 4. 다시 위의 과정을 left가 right 값보다 커질 때까지 반복한다. - 예시 배열의..
[문제] 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/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr [풀이] 각각의 banned_id마다 가능한 user_id의 index를 vector에 push DFS를 통해 banned_id마다 제재 id를 구한다. banned_id에 대해 user ID를 모두 선택했을 경우, 선택된 user ID의 index로 문자열을 만들어 set에 insert해준다. set을 통해 중복된 경우를 제거하여 모든 경우의 수를 구할 수 있다. ..
[문제] 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..