문제 링크 https://www.acmicpc.net/problem/1620 시간, 공간 제한 시간 : 2초 공간 : 256MB 문제 접근 방향 - key와 value 값을 저장하고 해당 자료구조를 탐색하여 적절한 값을 찾는 문제 - 단순히 배열을 자료구조로 선택할 경우 인덱스접근은 O(1)이지만 string을 찾기 위해서는 선형 탐색시 O(n)이된다. - 입력 최대 값이 100,000이고 선형 탐색을 통한 문제 해결시 전체 시간 복잡도는 O(n^2)으로 시간초과 발생한다. - string을 찾기 위해 O(logn)정도의 탐색 시간 복잡도가 필요하고 해당 시간 복잡도를 가진 map 자료 구조를 사용한다. - map은 key, value 한쌍을 저장할 수 있는 자료 구조이고 내부는 레드블랙트리라는 균형 이..

문제 링크 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 시간, 공간 제한 - 시간 제한 : 2초 - 메모리 제한 : 128MB 초기 문제 접근 방향 1. 입력이 9이고 시간제한이 2초 이므로 모든 경우의 수를 탐색할 때 시간초과에 걸리지 않을 수 있겠다고 생각 2. 모든 경우의 수의 경우 조합으로 알 수 있음 9개 중 순서에 상관없이 7개를 뽑고 뽑은 것들의 합이 100 이되면 출력하자! 조합은 재귀의 방식으로 구현 해보자 #include #incl..