본문 바로가기

알고리즘

 (32)
[백준] 1202번 보석도둑 [문제] 각 보석은 무게 M와 가격 V를 가지고 있다. 가방이 K개 있고, 각 가방에 담을 수 있는 최대 무게는 C이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. [풀이] 복잡하게 생각할수록 어려워지는 문제인것 같습니다. 풀이 방향은 맞췄지만 너무 복잡하여 예외 처리가 되질 않아 자꾸 틀렸습니다.. ㅠㅠ 꾸준함(https://jaimemin.tistory.com/760)님의 블로그를 참조하여 코드를 단순하고 깔끔하게 수정하였습니다. 풀이 방식의 핵심은 Max-Heap을 사용하는 것입니다. 해당 가방의 무게만큼 heap에 넣고 최대값만 쏙쏙 빼내는 방식입니다. 1. 가방과 보석을 모두 무게를 기준으로 오름차순 정렬합니다. 2. i번째 가..
문자열 탐색 알고리즘 KMP 특별한 의미는 없고 Knuth, Morris, Pratt 이 세 사람이 만든 알고리즘이라 하여 KMP라고 하네요 ㅎㅎ A B A C A B A B A B A B 만약 위와 같이 ABACABAB문장에서 ABAB를 찾는다 할때 보통 ABC를 한칸씩 오른쪽으로 옮기면서 비교하는 방법을 생각하기 쉽습니다. 하지만 그렇게하면 loop의 이중 중첩으로 문장이 매우 길어졌을 때 시간 복잡도가 (On2)이 되어 시간초과가 나곤 합니다. 그래서 나온것이 이 알고리즘! 간단히 말하면, 찾고자하는 패턴의 반복되는 부분만큼(A)은 건너뛰어서 불필요한 검색(B)을 줄이는 것입니다. 위의 예를 보면 앞의 AB와 뒤 AB가 겹치고 2자리까지 일치했습니다. 이때 겹치는 2칸만큼 건너띄워서 검색을 합니다. A B A C A B A B..
[백준] 1969번 DNA [문제] Hamming Distance(이하 HD)란 길이가 같은 두 DNA가 있을 때, 각 위치의 문자가 다른 것의 개수입니다. 예로, AGCAT와 GGAAT의 HD는 0, 3번째가 다르므로 2입니다. DNA들이 주어져 있을 때 HD의 합이 가장 작은 새로운 DNA s를, 그리고 이 s는 사전순서로 가장 앞에 오는 것 구하기! DNA가 a, b, c, d 이렇게 4개 주어졌다 하면, s와 a의 HD, s와 b의 HD, ... , s와 d의 HD 를 합한게 최소가 되는 s를 구하라는 의미입니다. [풀이] 생각보다 단순하게 Greedy하게 풀 수 있는 문제입니다. 문제상의 예시를 바탕으로 보면 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 우선 0번째 index를 보면 T..
[백준] 1449번 수리공 항승 [문제] 파이프의 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 각 새는 포인트를 길이가 L인 테이프를 붙여 막는다. 막을때 앞뒤 각 0.5의 간격을 두어야 하고 테이프를 자르거나 겹쳐붙일 수 없다. 사용되는 테이프의 개수는? [풀이] 간단한 문제인데 생각보다 너무 복잡하게 풀어서 재정리 후 코드를 간소화 시켜보았습니다. 테이프의 시작점을 잡고 start(시작점) + L(테이프길이)로 비교하며 두가지 케이스로 나누었습니다. 1. 현재 구멍난 곳이 start + L 보다 크거나 같을 때 2. 현재 구멍난 곳이 start + L 보다 작을 때 1번의 경우는 마지막 구멍일 경우에 tape 개수를 한번 더 + 해주었고 2번의 경우는 마지막 구멍이 아닐 경우에는 continue, 마지막일 경우에만 + 해주어 ..
[백준] 2352번 반도체 설계 [문제] 위 사진처럼 반도체 설계를 하는데 선들이 겹치지 않으면서 최대 몇개까지 연결할 수 있는지 구하는 문제입니다. [풀이] 복잡하게 생각이 들지만 Greedy 방식으로 생각보다 단순하게 풀 수 있는 문제였습니다. 우선 안겹치는 선들을 cache라는 변수에 저장을 해나가는 방식입니다. 크게 아래 두가지 경우로 나누면 되는데, 1. 다음 포트와 연결된 선이 현재 최신 cache와 연결된 선과 겹칠 경우 2. 다음 포트와 연결된 선이 현재 최신 cache와 연결된 선과 겹치지 않을 경우 1번의 경우에는 겹치지 않으니 그냥 cache에 추가해주면 되고, 2번의 경우에는 STL의 lower_bound를 활용해서 다음 포트와 연결된 선을 기준으로 그것보다 큰 가장 작은 정수 값을 찾아 교체합니다. * lower..
[백준] 1700번 멀티탭 스케줄링 [문제] 사용할 전자 기기의 순번이 정해져있고 멀티탭에서 가장 적게 콘센트를 뽑으면서 모든 전자기기를 사용하고 싶을 때, 콘센트 뽑는 횟수의 최소값은? [풀이] 크게 3가지 정도로 나눠서 풀이할 수 있습니다. 1. 멀티탭이 비어있을 경우 2. 다음 순번의 기기가 이미 멀티탭에 꽂혀있는 경우 3. 다음 순번의 기기가 멀티탭에 없을 경우 -> 제일 마지막에 다시 사용되거나 사용될 일 없는 기기 찾기 처음에는 너무 복잡하게 생각해서 정답은 맞췄지만 코드가 100줄이 넘어갔는데 풀이를 정리해서 큰 틀부터 정리해 나가니 코드가 반토막이 났습니다... 이미 멀티탭에 꽂혀있는 전자기기의 경우는 따로 boolean array를 통해 구분하여 추가적인 서치가 필요 없도록 했습니다. 아래는 해당 코드입니다! 1 2 3 4..
[백준] 1946번 신입 사원 [문제] 신입 사원을 뽑는데, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 이 조건을 만족시키면서 선발할 수 있는 최대 인원수는?? [풀이] 우선, 서류 성적을 기준으로 정렬을 하면, 어짜피 서류성적은 이미 정렬해놔서 고려할 필요가 없고 본인보다 서류 성적이 높은 사람들의 최고 면접 점수보다 본인의 면접 점수가 높으면 합격할 수 있습니다. 1 5 3 2 -> 1 4 1 4 2 3 4 1 3 2 2 3 4 1 5 5 5 5 예제를 바탕으로 위의 값(왼쪽)을 입력했다고 했을 경우, 1등은 다른 지원자보다 떨어질 수가 없기에 기준점으로 잡고자 우선 오름차순 정렬(오른쪽)을 해줍니다. 그 후, 면접성적이 본인보다 서류 성적이 높은..
[백준] 2437번 저울 [문제] 무게가 양의 정수인 N개의 저울 추가 주어졌을 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값 구하기. [풀이] Greedy 방식으로 해결할 수 있는 문제로, 각 추를 정렬 후 누적합을 구하면서 해결해 나갈 수 있습니다. 우선, 추의 배열을 w, 누적합의 배열을 acc라고 정의하겠습니다. 무게가 1인 추가 있을 때, acc[i-1] + 1 >= w[i] 일 경우 acc[i-1] ~ acc[i] 사이의 모든 수를 만들 수 있습니다. 만약 저 조건에 해당하지 않는다면 acc[i-1] + 1이 만들수 없는 수 입니다. 그리고 무게가 1인 추가 없다면 당연히 답은 1이겠죠? 문제에 제시된 예제를 통해 설명하도록 하겠습니다. i 0 1 2 3 4 5 6 추(w) 1 1 2 3 6 7 ..

티스토리툴바