알고리즘 문제풀이

프로그래머스 코딩테스트 고득점 Kit - 힙(Heap) 더 맵게 - Level2 문제 문제에서 주어진 Operation을 한번 수행할 때 마다, 전체 음식의 수는 1개씩 줄어든다. 즉, 최대 $N$번 Operation을 수행한다. scoville의 길이가 최대 $1,000,000$인 것을 고려한다면 , 매 Operation마다 $O(N)$ 의 탐색으로 최소 값을 찾는 것은 시간 초과인 것이 자명해보인다. 즉 $O(logN)$ 이하로 최솟 값을 찾아야 하는데, 이 때 쓰일 수 있는 자료구조가 Min-heap이다. Min-Heap의 특성 상 각각의 서브트리에 존재하는 루트노드가 항상 자식 노드보다 큰 것이 보장되고 최상위 루트 노드의 값이 전체 노드의 최솟값이므로 $O(1)$에 최소값을 찾을 수 있다. 이 ..

프로그래머스 고득점 Kit - 해시 Hash Table 방식의 충돌 issue + string hashing에 필요한 cost를 고려하여 Red-Black Tree 기반의 Map을 사용하였습니다. 접근 시간 : $O(logN)$ 삽입 시간: $O(logN)$ 완주하지 못한 선수 문제 participant 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 증가 completion 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 감소 Map에 존재하는 노드 중, 값이 1이상인 것은 마라톤 경기를 완주하지 못한 사람. #include #include #include using namespace std; string solution(vector participant, vector ..

프로그래머스 코딩테스트 고득점 Kit - 정렬 K번째 큰 수 - level1 문제 주어진 commands에 포함되어 있는 parsing정보를 이용하여 array를 파싱한 데이터를 정렬하여 값을 구하면 되는 간단한 문제 $K: commands의 길이$, $N : Array의 길이$ 라 할 때 총 시간 복잡도는 $O(KNlogN)$가 된다. #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; for(const auto& cmd : commands){ int from = cmd[0], to = cmd[1], kth = cmd[2]; vector subArray; ..

[프로그래머스 코딩테스트 고득점 Kit] - 스택/큐 아래 코드들은 Case에 맞게 straightforward한 설명을 위해, 별도의 리팩토링을 하지 않은 코드입니다. 기능개발 - level 2 문제 작업의 개수progresses, speeds 의 크기

백준 16472번 - 고냥이 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 512MB 1285 553 417 42.464% 문제 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다. 현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 ..

백준 1240번 - 노드사이의 거리 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2초 128MB 1832 969 762 53.586% 문제 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 예제 입력1 4 2 2 1 2 4 3 2 1 4 3 1 2 3 2 예제 출력1 2 7 출처 출처 알고리즘 분류 그래프 이론 그래프 탐..