Algorithm (62) 썸네일형 리스트형 [Algorithm] 프로그래머스 베스트앨범 c++ (Map 활용) 알고리즘 풀이는 python으로 구현한 글에 있다. 여기서는 C++의 Map을 활용하는 방법을 기록하기 위해 같은 알고리즘을 들고왔다. Map 활용 예시 선언 #include map genresCnt; //key=string, value=int map playsCnt; //key=int, value=int 삽입 //1. insert와 make_pair 활용 genresCnt.insert(make_pair(genre, plays[i])); //2. 배열처럼 사용 genresCnt[genre] += plays[i]; 조회 genresCnt.count(genre) //genre는 key -> key에 해당하는 value 개수 반환 정렬 map자체를 정렬하는 것이 아니라 map을 vector로 변환 후, vec.. [Algorithm] 프로그래머스 베스트앨범 python https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 장르 별 재생된 노래를 { key: 장르, vaule: 재생 횟수 }형식으로 딕셔너리에 담는다. -> genresCnt genresCnt를 value 기준으로 내림차순 정렬한다. genresCnt의 key와 일치하는 genres의 인덱스를 찾고, 인덱스에 해당하는 plays를 { key: 장르의 인덱스, value: 인덱스에 대응하는 재생 횟수 }형식으로.. [Algorithm] 프로그래머스 위장 python https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 풀이 clothes의 종류를 key로, 종류에 해당하는 옷의 개수를 value로 딕셔너리에 넣는다. 옷을 선택하는 조합을 계산한다. (조합 식을 알면 간단한데, 모르면 어려움) 예시 예제 1의 딕셔너리 형태는 { headgear: 2, eyewear: 1 } 이다. 이때 각각의 옷의 종류에서 선택할 수 있는 경우의 수는, headgear -> 0개, 1개, 2개 eyewear -> 0개, 1개 따라서 옷을 선택하는 모든 경우의 수는 3 * 2 = 6 이고, headgear 0개, eyewear 0개를 선택하는 경우(아무것도 선택하지 않는 경우)를 .. [Algorithm] 프로그래머스 전화번호 목록 python 풀이 phone_book 정렬하기 현재 전화번호를 바로 다음 번호와 비교한다. 그 값이 같다면, 다음 번호가 현재 번호를 접두사로 가지고 있다는 뜻이다. Q. 현재 값과 다음 값의 비교만으로도 가능한 이유는? A. 정렬을 하는 순간 인접한 번호들끼리 비슷(?)해지기 때문이다. 놓지고 있던 것이 바로 숫자로 이루어진 문자열의 정렬 후 결과였다. phone_book = ["119", "97674223", "1195524421"] phone_book.sort() print(phone_book) //["119", "1195524421", "97674223"] -> 아스키 코드 기반으로 정렬되기 때문에 1195524421가 97674223앞에 있다. 소스코드 def solution(phone_book): phon.. [Algorithm] 프로그래머스 입국심사 c++ 풀이 BinarySearch 심사를 받는 시간을 기준으로 이진탐색을 수행한다. (구하는 것: 시간) left에 최소 심사 시간, right에 최대 심사 시간을 넣는다. mid 시간동안 심사 받을 수 있는 사람의 수(= cnt)를 카운팅한다. cnt = n 인 경우, n명 이상 심사를 받은 경우로, mid 시간에 n명 심사가 가능하다는 뜻이다. 즉, 최적해는 mid시간보다 작거나 같은 값이 된다. 소스코드 #include #include #include using namespace std; long long solution(int n, vector tim.. [Algorithm] 백준 17298 오큰수 c++ https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 수열(a)의 왼쪽부터 인덱스와 스택을 활용해 오큰수 탐색한다. 스택에 들어있는 값은 아직 오큰수를 구하지 못하였거나 오큰수가 없는 수의 인덱스이다. 세부 풀이 우선 스택에 첫 인덱스인 0을 넣고 다음 인덱스로 넘어간다. 스택에 들어있는 값과 현재 인덱스에 각각 대응하는 값을 비교한다. 현재 인덱스의 값이 더 큰 경우 오큰수를 발견한 것이다. nge에 값을 넣는다. (스택에 들어있는 값이 더 큰 경우 오.. [Algorithm] 백준 13305 주유소 c++ https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 Greedy 제일 왼쪽 도시의 주유 가격을 현재 가격으로 설정한다. n 번째 도시에서 n + 1 번째 도시로 넘어가기 위한 거리만큼 주유를 해서 비용을 누적한다. n + 1 번째 도시의 비용이 더 저렴한 경우 현재 가격을 n + 1 번째 도시의 주유 가격으로 업데이트한다. 주의) 데이터 타입을 long long으로 해야 한다! 소스코드 #include #include using.. [Algorithm] 백준 1463 1로 만들기 c++ https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 DP N에서 1을 만드는 방법을 생각하지 않고, 1에서 N을 만드는 방법으로 구현한다. (bottom-up) N = 1인 경우 f[1]에 0을 넣고(basecase) 1에서 +1, *2, *3을 했을 때의 값인 f[2], f[3]에 1(f[1] + 1)을 넣는다. 즉, f[i+1] = f[i*2] = f[i*3] = f[i] + 1 이다. 다만 i보다 더 큰 수(j)로부터 최소의 횟수를 만들 수 있으므로 min(f[i] + 1(현재값), f[j] + 1)으로 값을 업데이트한다. 주의사항) 1에서 N이 되는.. 이전 1 ··· 4 5 6 7 8 다음
