rainyCode rainyCode

#골드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..

#백준 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/..

Lv2. 문제링크 2023 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📎알고리즘 n이 10만 개라는 것에서 n^2 이 걸리는 완전 탐색은 배제해야 함을 알 수 있다. 그리디 하게 풀어야 하는 문제이다. 일단, 처음부터 제일 멀리 있는 집에 가서 작업을 최대한 끝내야 먼 곳을 최소한으로 갈 수 있을 것이다. 그래서 가장 먼 집부터 탐색해서 배달, 수거할 상자 개수를 각각의 변수에 더해주고 이 값을..

🥇문제 링크 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)를 사용해 주었다. 쉽게 ..

문제링크 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 알고리즘 시작점이 주어지고 다른 노드까지의 최단거리를 주는 문제는 다익스트라 알고리즘의 정석이라고 할 수 있다. 간선의 가중치가 모두 양수이기 때문에 다익스트라 알고리즘을 사용할 수 있고, 만약 가중치에 음수가 포함된다면 밸만포드(Bellman-Ford) 알고리즘을 사용해야할 것이다. 다익스트라 알고리즘도 우선순위 큐를 사용하면 시간복잡도를 O(Nlo..