my devlog;

즉, citations 배열에서 h 이상의 값을 가지는 원소가 h개 이상인 h의 최대값을 찾는 것이다. 문제 설명이 다소 혼란스러워서 문제 자체를 이해하는 데에 어려움을 겪는 사람이 많아보였다. 나도 문제를 읽으면 읽을수록 헷갈렸기에, 주의할 점과 테스트 케이스를 자세히 적어보았다. 주의해야 할 점 1. h가 반드시 citations 배열의 원소값이어야 하는 것은 아니다. -> citations = [10, 9, 4, 1, 1], answer = 3 2. h 이상의 값을 가지는 원소가 h개여야 하는 것은 아니다. -> citations = [0, 1, 1], answer = 1 3. h 값은 citations 배열의 size 값보다 큰 값일 수 없다. -> citations = [31,66], answe..

탐색 : 여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 키로 항목을 서로 구별. 배열, 연결 리스트, 트리, 그래프, 해시 테이블 등을 사용 ① 순차 탐색 ▷ 아이디어 : 처음부터 마지막까지 하나씩 순차적으로 확인 ▷ 프로그램 int sequential_search(int key, int low, int high){ for(int i = low; i high) return -1; int middle = (low+high)/2; if (key == list[middle]) return middle; else if (key < list[middle]) return search_binary(key, low, middle-1); else return search_binary(key, middle+1, ..

참고 : 선택 정렬, 삽입 정렬, 버블 정렬https://hyunah-home.tistory.com/entry/%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC 기본 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 hyunah-home.t..

다양한 방법으로 풀 수 있는데, 나는 큐를 사용해서 풀었다. 주의할 점 : 같은 숫자들이 있는 경우에도 반드시 k개의 수를 제거하여 가장 큰 수를 만들어야 한다는 점. 작은 수를 골라서 제거하는 방식으로는 틀리기 쉽다. #include #include #include #include using namespace std; /* 처음에 사용한 직접 정의한 최대값 인덱스 찾기 함수 int find_max_index(string &n, int start, int end){ int max = -1; int max_index = 0; for(int i = start; i 0){ index = max_element(number.begin()+start+1,number.begin()+start+2+k) - number..

정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 정렬 안 된 리스트를 가정함. 정렬 안 된 리스트에서 최소값이나 최대값을 선택해 한쪽으로 몰아넣음. ▷ 알고리즘 ; 오름차순 정렬 기준 1. 오른쪽 리스트에서 최소값의 인덱스 선택 2. 오른쪽 리스트의 첫번째 수의 값과 최소값을 교환 3. 왼쪽 리스트 크기 1 증가, 오른쪽 리스트 크기 1 감소 4. 오른쪽 리스트가 소진될 때까지 1~3 과정 반복 ▷ 프로그램 void selection_sort(int list[], int n){ int least, temp; for (int i = 0; i < n-1; i++) {..

문제 설명 : 왼쪽의 보드에서 각 컬럼의 맨 위에 있는 인형을 집어 오른쪽의 바구니로 옮기는 과정을 실시한다. 오른쪽 바구니의 격자 아래칸부터 차곡차곡 쌓이게 된다. 이때 오른쪽 바구니에서 같은 모양이 두 개가 겹쳐지면 두 인형은 떠뜨려지면서 사라진다. 인형이 집어지지 않는 경우는 없고, 인형이 없는 곳에서 크레인 작동시키는 경우에는 아무 일도 일어나지 않는다. 오른쪽의 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다. 오른쪽의 바구니를 스택으로 구현하여 스택의 top 원소와 집어넣고자 하는 원소의 값이 일치하면 스택을 pop하는 방식으로 풀면 된다. 스택을 이용하는 간단한 문제. #include #include #include using namespace std; int push(stack &s..

정수로 주어진 numbers를 string으로 변환하여 정렬하거나 각 숫자의 자리수별로 비교하여 처리해주면 된다. 나는 전자의 방법을 썼다. #include #include #include using namespace std; bool compare(string x, string y){ return x+y > y+x; } string solution(vector numbers) { vector numbers_str; string answer = ""; for(int i = 0; i

DAG(Directed Acyclic Graph) : 사이클이 없는 방향 그래프. DAG에서 에지 가 있다면 정점 u는 정점 v를 선행함. 위상 정렬(topological sort) : 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 것. 선행관계가 없는 것은 뭐가 먼저 나오든지 상관이 없기 때문에 위상 정렬 결과는 여러 가지가 존재할 수 있음. ▷ 알고리즘 1. 진입차수가 0인 임의의 정점(선행자가 없는 정점)을 큐(혹은 스택)에 삽입 2. 정점 개수만큼 시행하는 반복문 생성 3. 반복문 내부에서는, 큐에서 정점을 하나씩 꺼내어 출력하고 출력한 정점에 붙어있는 에지들을 제거하여 진입차수 재계산 4. 진입차수를 재계산하여 진입차수가 0이 된 것은 큐에 삽입 위상정렬이 불..

최단 경로 : 그래프에서 정점 u로부터 정점 v로 가는 경로 중에서 에지들의 가중치 합이 최소가 되는 경로. 혹은 에지의 개수가 가장 적은 경로. 다익스트라 알고리즘 (Dijkstra Algorithm) : 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾을 수 있는 알고리즘. ▷ 아이디어 : 방문하지 않은 정점 중에서 가장 비용이 적은 에지로 연결된 정점을 방문. 시작 정점으로부터 해당 정점을 경유지로 하여 다른 정점을 방문하는 비용이 더 작다면, 최단 경로값을 갱신. 위의 그림에서 distance[u]가 distance[w]값보다 작아서 가장 비용이 적은 에지로 연결된 정점 u가 새롭게 추가되었다면(방문되었다면), 시작 정점 v로부터 해당 정점 u를 거쳐서 다른 정점인 w로 가는 비용을 계산한다..

힙을 사용하여 문제를 해결하는 능력만 있다면 풀 수 있는 문제. 주의할 점 : 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우를 처리해야 한다는 것. 모두 섞어서 하나의 스코빌 지수로 합하였는데도 K 이상이 되지 않는 경우를 처리해주어야 함. #include #include #include using namespace std; int solution(vector scoville, int K) { priority_queue pq; int answer = 0; for(int i = 0; i= K) break; // 조건 충족. 성공. if(pq.empty()) { // 힙이 빈 경우. 섞어서 새로운 스코빌 지수 만들 수 없음. 실패. answer = -1; break; } int second = ..