반응형 Algorithm143 [Heap, 난이도 중] 프로그래머즈, 이중우선순위큐 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리이다. 삽입, 삭제의 시간 복잡도가 O(logn) 밖에 안된다. 구조를 최대 힙 기준으로 간단히 설명 해보자면 이렇다. 삽입 : 처음에는 힙의 마지막 인덱스에 두고 부모 노드보다 클 경우 계속해서 부모 노드와 swap 해나가면 된다. 삭제 : 힙의 마지막 인덱스를 root에 두고 두 자식 노드들중 큰 값을 가지는 노드와 swap해나가면 된다. 더 자세한 설명이 필요하다면 위키백과를 확인해보면 좋다. ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 .. 2020. 9. 11. Sort 고득점 kit 풀이 완료, 후기 정렬은 대학 1학년 과정부터 나오는 알고리즘으로 매우 기초적인 개념이다. 그러나 방대한 데이터범위가 주어졌을 경우에는 시간 복잡도를 줄이지 않으면 안되는 상황이 오게 된다. 고득점 Kit의 3문제에서는 모두 퀵정렬(Quick sort)를 이용했으며 시간 복잡도는 O(nlogn)이다. C++에서는 algorithm 헤더 파일에 sort함수가 내장되어 있고 sort함수의 3번째 인자에 boolean을 반환하는 함수를 넣어줘서 어떤 기준으로 정렬할 것인지도 정할 수 있다. 정렬 알고리즘은 그리디, 다이나믹, 크루스칼 등등 많은 알고리즘 안에서 이용 되므로 배우지 않으면 안된다. 문제모음 [난이도 하] H-Index kimcoder.tistory.com/96 [난이도 중] 가장 큰 수 kimcoder.tisto.. 2020. 9. 11. 2020 SCPC/Programmers 월간 코드 챌린지 결과 2020 SCPC 예선 2차까지 진출 Programmers 월간 코드 챌린지 4910명중 163위 역시 알고리즘을 배우니 문제를 봤을 때 접근법부터가 달라지는 것 같다. 그래도 아직 갈길이 멀기 때문에 알고리즘 공부는 멈추지 않을 것이다. 2020. 9. 10. [정렬, 난이도 하] 프로그래머즈, H-Index 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이라고 했을 때 가능한 h의 최댓값을 구하는 문제이다. 단순히 citations를 오름차순으로 정렬하면 문제를 쉽게 해결할 수 있다. 오름차순으로 정렬한 후에 n-h번째에 있는 논문의 인용 수가 h이상이라는 뜻은, 논문의 인용수가 h이상인 논문의 수는 h개 이상이라는 뜻이 된다. 본인의 소스코드에서 사용한 정렬은 시간 복잡도가 O(nlogn) 이므로, 시간복잡도도 O(nlogn) 밖에 되지 않는다. 테스트케이스 16개 모두 통과 #include #include int maxi(int a,int b){ if(a>b) return a; else return b; } using namespace std; int solution(vector.. 2020. 9. 10. [정렬, 난이도 중] 프로그래머즈, 가장 큰 수 정렬 방식을 찾기에 쉬운 문제는 아니었다. 문자열을 그대로 내림차 순으로 정렬 한다면 예제 2에서는 30이 3보다 앞에 오게 된다. 303 2020. 9. 10. [그리디, 난이도 중] 프로그래머즈, 단속카메라 이 문제 같은 경우에는 차량들의 진출 지점을 기준으로 오름차순으로 정렬해야 한다. 그리고 최근에 설치한 카메라의 지점을 기록하는 변수(recent_camera) 가 필요하다. 입출력 예 정렬 전 정렬 후 첫 차량(정렬 후)의 진출 지점에 카메라를 설치한다. (recent_camera=-13, answer=1) 두 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-13) 세 번째 차량의 진입 지점은 recent_camera의 이후이므로 진출 지점에 카메라를 설치한다. (recent_camera=-3) 네 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-3) 이렇게.. 2020. 9. 10. [정렬, 난이도 하] 프로그래머즈, K번째수 (벡터 복사) 기초적인 정렬문제이다. 구간을 잡고 정렬해서, 그 구간내에서 원하는 인덱스값을 추출하면 된다. 그런데 테스트케이스가 여러개이기 때문에 벡터를 테스트케이스마다 초기화해줘야 한다. 본인 같은 경우에는 구간을 잡을 때, 구간을 잘라서 다른 벡터에 따로 할당시켰다. 벡터를 할당하는 함수의 사용법이다. 할당받을 대상인 벡터를 V1이라고 하고 할당할 값들이 있는 벡터를 V2라고 한다면 V1.assign(V2.begin()+firstindex, V2.begin()+lastindex+1) 만약 V2벡터의 1번째 인덱스부터 4번째 인덱스까지 복사하여 V1벡터에 붙여넣고 싶다면 V1.assign(V2.begin()+1, V2.begin()+5) 로 작성한다. (2번째 인자 값의 이전까지만 포함) 통째로 복사하고싶다면 V1.. 2020. 9. 10. [스택/큐, 난이도 중하] 프로그래머즈, 프린터 문제의 조건을 보고 스택,큐중 어느 것을 요구하는지 파악해보자. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. '앞', '마지막' 이라는 단어가 나오는 것을 보아 큐 문제임을 알 수 있다. 그리고 둘 이상의 문서끼리 중요도가 같을 수 있고, 문서의 인덱스까지 신경써줘야 하는 문제이다. 그래서 큐에 문서의 중요도, 인덱스 두 정보를 pair을 이용해 정리했다. 문서는 최대 100개 있고, 중요도는 1~9의 정수로 표현할 수 있다. J보다 중요도가 높은 문서를 찾기 위해 큐에 있는 모든 요소를 확인하는 것 보다는, 중요도별로 .. 2020. 9. 9. [동적계획법, 난이도 중상] 프로그래머즈, 도둑질 Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다. 집이 일렬로 있는게 아니라 원형으로 배치 되어있기 때문에 접근법을 좀 다르게 생각해줘야 한다. 결론부터 말하자면 3가지 경우에 대해 DP를 수행하여 이들 중 최댓값을 구하면 된다. 3가지 경우는 이렇다. 0번째 집부터 터는 경우 1번째 집부터 터는 경우 2번째 집부터 터는 경우 3번째 집부터 터는 경우는 1번째 집을 털 수 있는 상황인데도 털지 않는 경우이므로 최대값이 나올 일이 없다. 케이스별로 DP수행 직전 상황을 그림으로 간략하게 표현하였는데, 회색은 털 수 없는 집이다. 1. 0번째 집부터 터는 .. 2020. 9. 8. 이전 1 ··· 7 8 9 10 11 12 13 ··· 16 다음
