알고리즘 문제풀이
-
[C++] 백준 12865번 - 평범한 배낭 (knapsack) 문제알고리즘 문제풀이/백준 2024. 1. 12. 11:46
#골드5 백준 12865번 문제는 정말 유명한 알고리즘인 knapsack 알고리즘의 대표문제이다. knapsack 알고리즘은 쪼갤 수 있냐 없냐에 따라 두 가지로 나뉘는데 만약 쪼갤 수 없다면, brute force와 dynamic programming으로 풀 수 있다. 그러나 brute force 방법은 시간복잡도가 O(2^n)만큼 잡아먹어서 n이 크다면 극악의 시간복잡도이다. 그래서 웬만한 ps에는 쓰이지 않을 것이다. 반면에 dp는 중첩 for문으로 이차원 배열을 사용하기 때문에 O(n^2)으로 쓸만하다. 추가적으로 만약 쪼갤 수 있는 knapsack 문제이면 greedy하게 해결도 가능하다. 이 방법은 다른 포스팅에서 다뤄보겠다. 문제 링크 https://www.acmicpc.net/problem..
-
[C++] 백준 9663번 - N-Queen (백트래킹) 문제알고리즘 문제풀이/백준 2024. 1. 12. 11:25
#골드4 백준 9663번 문제는 백트래킹의 대표 문제인데, 백트래킹을 돌 조건식만 잘 세울 수 있다면 문제없이 풀 수 있을 것이다. 자네, 체스를 좀 해보았는가..? 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 이 문제의 핵심은 두 개이다. 1. 같은 행에는 퀸 1개만 놓을 수 있다는 것 2. 두 개의 퀸이 대각선에 존재하는지 체크하는 식이다. 같은 행에 퀸은 한개만 존재하기 때문에, col이라는 배열에서 i번째 원소의 값은 NxN 체스..
-
[C++] 백준 15654번 - N과 M(5) (백트래킹) 문제알고리즘 문제풀이/백준 2024. 1. 10. 21:17
#백준 15654번 N과 M(5) 백준 15654번 문제는 백트래킹 개념과 dfs 개념만 알고 있으면 쉽게 해결할 수 있는 문제이다. 바로 전에 N과 M(4)를 풀고와서 혼자 힘으로 해결할 수 있었다. 개꿀! 문제 링크 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 이 문제에 대한 자세한 플로우는 비슷한 문제인 N과 M(4)에 흐름을 자세히 설명해 생략하겠다. https://rainycode.tistory.com/entry/..
-
[C++] 백준 15652번 - N과 M(4) (백트래킹) 문제 풀이알고리즘 문제풀이/백준 2024. 1. 10. 19:29
#백준 15652번 N과 M(4) 백준 15652번 문제는 문제도 간단해서 언뜻 보기에는 쉬워 보이지만 백트래킹, 재귀에 관한 개념이 제대로 잡혀 있지 않다면 본인처럼 헤맬 수 있다. 문제 링크 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 dfs 함수는 재귀함수이고, 두 개의 파라미터를 가진다. num과 k인데, num은 1~N까지 숫자, 즉 출력되는 숫자라고 생각하면 된다. 그리고 변수 k는 배열의 길이이다. 배열의 길이를 파라..
-
[Python] 프로그래머스 - 이모티콘 할인행사 - 중복순열, 완전탐색알고리즘 문제풀이/프로그래머스 2023. 6. 23. 19:20
Lv2. 문제링크 2023 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📎알고리즘 먼저, 할인율이 [10,20,30,40]으로 한정되어 있고, 이모티콘 최대 개수가 7개인 것을 보아, 이건 완전탐색으로 풀어도 되겠구나 라는 생각이 들었다. 모든 조합을 따져봐야하는데, 이모티콘의 index 순서에 따라 할인율 조합을 구해야 하므로, 중복 순열을 사용하면 된다. itertools.product 라이브..
-
[Python] 프로그래머스 카카오 문제 - 택배 배달과 수거하기 - 그리디알고리즘 문제풀이/프로그래머스 2023. 6. 19. 04:31
Lv2. 문제링크 2023 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📎알고리즘 n이 10만 개라는 것에서 n^2 이 걸리는 완전 탐색은 배제해야 함을 알 수 있다. 그리디 하게 풀어야 하는 문제이다. 일단, 처음부터 제일 멀리 있는 집에 가서 작업을 최대한 끝내야 먼 곳을 최소한으로 갈 수 있을 것이다. 그래서 가장 먼 집부터 탐색해서 배달, 수거할 상자 개수를 각각의 변수에 더해주고 이 값을..
-
[Python] 프로그래머스 - 개인정보 수집 유효기간 - 구현알고리즘 문제풀이/프로그래머스 2023. 6. 16. 17:04
Lv1. 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📎알고리즘 내가 처음에 했던 것처럼 년, 월, 일로 경우를 나눠서 계산하려면 너무 많은 경우가 나오고 이걸 구현하려면 if 가 3개 이상 중첩된 내 코드를 보고 있으면 어지럽다. 단순 구현문제라, 방향만 잘 잡으면 되는데 이렇게 날짜를 비교할 때 년, 월, 일을 한번에 일자로 변환시켜 주면 그냥 대소만 비교하면 된다. def dateChanger(date): #년월일을 일 총합..
-
[Python] 백준 11779번 최소비용 구하기 2 - 다익스트라 알고리즘 최단경로 구하기알고리즘 문제풀이/백준 2023. 5. 24. 19:24
🥇문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📎알고리즘 난이도: Gold3 그냥 다익스트라를 사용했다면 실버 난이도였겠지만 골드 문제답게 경로 출력을 추가로 시켜서 난이도가 확 올라간 모습이다. 기본적으로 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 이용해 주면 된다. 시간 복잡도를 O(N^2)에서 O(NlogN)으로 줄이기 위해 우선순위 큐(파이썬에서는 heapq)를 사용해 주었다. 쉽게 ..