본문 바로가기

Algorithm/Programmers

 (15)
[프로그래머스 코딩테스트 고득점 Kit - 완전탐색] 모의고사 완전탐색 문제 https://programmers.co.kr/learn/courses/30/lessons/42840 [문제 설명] 특수한 패턴으로 찍는 세 사람들 중 답을 누가 가장 많이 맞힐 수 있는지에 대한 문제입니다. 설명이 필요할 만큼 어려운 문제는 아닙니다. 각 사람들이 갖고 있는 패턴과 정답을 비교해 나가면서 누가 가장 많이 맞췄는가를 세주면 문제는 해결됩니다. 1번 수포자의 경우 [1, 2, 3, 4, 5]의 패턴을 가지고 있습니다. 2번 수포자의 경우 [2, 1, 2, 3, 2, 4, 2, 5]의 패턴을 가지고 있습니다. 3번 수포자의 경우 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]의 패턴을 가지고 있습니다. 여기서 어려울 수 있는 딱 하나의 문제가 있는데, answer의 길이..
[프로그래머스 코딩테스트 고득점 Kit - 정렬] H-Index 정렬 문제 https://programmers.co.kr/learn/courses/30/lessons/42747 유명한 정렬 문제입니다. https://www.acmicpc.net/problem/12109 물론 백준에도 있습니다. [문제 설명] H-Index를 구하는 문제입니다. 문제 자체는 어렵지 않은데 H-Index라는 개념을 이해하는 것이 어렵게 느껴질 겁니다. 특히나 프로그래머스의 H-Index설명이 더 구체적이라 헷갈리는 분들도 많을 겁니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 지문에서는 위처럼 설명되어 있으나, 사실 밑줄 친 부분만 읽어도 무방합니다. 오히려 밑줄 친 ..
[프로그래머스 코딩테스트 고득점 Kit - 정렬] 가장 큰 수 정렬 문제 https://programmers.co.kr/learn/courses/30/lessons/42746 [문제 풀이] 주어진 정수를 잘 조합하여 가장 큰 수를 만드는 문제입니다. 단순하게 생각하자면 모든 조합을 전부 구하고 가장 큰 수를 확인할 수도 있습니다. numbers의 길이가 n, numbers원소의 길이가 l이라 하면 시간 복잡도는 $O(n! \, n^2 \, l)$의 시간 복잡도를 갖습니다. (모든 조합을 구하는 시간 복잡도 $O(n!)$, 길이가 $nl$인 문자열들 중 최댓값을 찾는 시간 복잡도 $O(n \, nl)$ n의 최대가 10만이므로 말도 안 되는 풀이입니다. 모든 원소에 대한 조합을 전부 구하고 비교하는 과정이 매우 비효율적입니다. 하지만 2개의 원소만 뽑아서 구해본다면,..
[프로그래머스 코딩테스트 고득점 Kit - 정렬] K번째수 정렬 문제 programmers.co.kr/learn/courses/30/lessons/42748 [문제 풀이] 주어진 배열에 대해 [i, j] 범위에 대해 k번째 수를 구하는 문제입니다. 배열을 주어진 범위에 대해 잘라서 정렬한 후 k번째 수를 출력하면 해결이 가능합니다. for문을 사용하여 특정 범위만큼을 잘라 새 배열에 넣거나 c++의 경우는 포인터를 사용하여 for문 없이 간결하게 떼어낼 수 있습니다. i, j, k는 1번째부터 시작하고 인덱스는 0번째부터 시작함에 주의하셔야 합니다. 문제를 꼬아놓거나, 기술적으로 어려운 부분이 없는 문제라서 간단한 문제입니다. [소스 코드] / C++ #include #include #include #include using namespace std; vecto..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 이중우선순위큐 우선순위 큐 문제 programmers.co.kr/learn/courses/30/lessons/42628 www.acmicpc.net/problem/7662 위 문제와 동일한 문제입니다. 테스트 케이스는 백준이 더 강력합니다. [문제 풀이] 이중 우선순위 큐를 구현하는 문제입니다. 사실 자료구조에 대해 숙련이 되어 있다면 매우 간단한 문제입니다. 레드 블랙 트리 기반의 자료 구조들은 최댓값, 최솟값을 무려 $O(1)$에 불러올 수 있기 때문입니다. 즉 C++의 multiset같은 경우, 그 자체로 이중 우선순위 큐의 역할을 할 수 있습니다. 자바의 경우 TreeSet은 중복이 안되므로 TreeMap을 사용하여 중복 처리를 해주는 방식으로 해결할 수 있습니다. 자바는 TreeSet이면 first, last..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 디스크 컨트롤러 구현 문제 programmers.co.kr/learn/courses/30/lessons/42627 [문제 풀이] 모든 작업에 대해 (작업이 끝난 시간) - (작업이 요청된 시간)의 합을 최소로 만드는 문제입니다. 하나의 디스크는 하나의 작업만 처리가 가능합니다. 작업 시간이 전혀 겹치지 않는다면 이 문제는 전혀 문제가 아닙니다. 그러나 작업 시간이 겹치는 경우에 어느 작업부터 시작해야 하는지 골라야 하는 것이 어려운 문제입니다. (작업이 끝난 시간) - (작업이 요청된 시간)만 보면 생각하기 쉽지 않으니 조금 형태를 바꿔보겠습니다. (작업이 끝난 시간) - (작업이 요청된 시간)은 (작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)으로 치환할 수 있습니다. 이해가 안 될 수도 있으니 그..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 더 맵게 우선 순위 큐 문제 programmers.co.kr/learn/courses/30/lessons/42626 [문제 풀이] 모든 음식이 K 이상의 스코빌 지수를 가질 때까지 음식들을 섞는 횟수를 구하는 문제입니다. 음식을 섞는 레시피는 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 입니다. 음식의 개수 N의 제한이 1,000,000입니다. 제한이 상당히 높으니 효율적으로 코드를 짤 필요가 있습니다. 매번 음식을 섞을 때마다 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 뽑아낸다면 시간 복잡도가 음식의 개수 N, 섞는 횟수 M에 대해 $O(NM)$이 나옵니다. 섞는 횟수 M은 최악의 경우 N - 1이므로 결국 $O(N^2)이 됩니다. N이 100,000이어도..
[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 프린터 큐 문제 programmers.co.kr/learn/courses/30/lessons/42587 [문제 풀이] 원형으로 계속 돌아가는 문서 중 우선순위가 가장 높은 것을 먼저 출력하는 문제입니다. 원형으로 문서를 계속 돌리고 확인해야 하므로 큐를 써야 한다고 생각할 수 있습니다. 가장 직관적으로 생각해보면 우선 배열을 순회하면서 1~9까지의 중요도가 몇 개씩 있는지 확인하고 큐 안에 문서에 대한 정보를 넣어야 합니다. 구해야 하는 답이 위치를 기반으로 찾게 됩니다. 그러므로 큐 안에 넣을 문서에 대한 정보는 위치가 필수적으로 들어갑니다. 중요도까지 넣어도 되지만 위치를 넣었다면 그 위치에 대한 중요도를 priorities배열로 구할 수 있기 때문에 넣지 않아도 좋습니다. 예를 들어 priorities가 ..

티스토리툴바