Algorithm Problem/Python

[python] 백준 - 1743. 음식물 피하기

🤔문제 해결 S1 | BFS 이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다. 각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다. 주변의 쓰레기를 선택할 때마다 visited 에 add 해준다. 또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다. 💨 set() 을 쓰는 이유 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다. 하지만 if tmp in list : list의 경우 O(n) 이다. 💻소스 코드 import sys from collections import deque def bfs(x, y): q = deque() q.append((x, y)) cnt..

[python] 프로그래머스 - 외벽 점검(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 3 | 정답률: 0.6% 주어진 값의 크기가 크지 않기 때문에 완전탐색으로 해결이 가능하다. 먼저 친구를 순열로 만든다. ex) [1,2,3] 이면 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 외벽이 원형이므로 앞과 뒤가 이어져 있다고 생각해야 한다. 취약점도 첫번째 취약점을 먼저 갈것인가 두번째 취약점을 먼저 갈것인가... 순서를 정해서 가야한다. - 첫번 째 테스트케이스의 취약점([1, 5, 6, 10])을 배열(n=12)로 나타내면 [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0] 위의 경우는 첫번째 취약점(1)이 가장 먼저 나오는 경우 - 다음 취약점 2가 가장 먼저 나오는 경우는 0,1을 맨뒤로 옮겨주면 된다. ..

[python] 백준 - 11052. 카드 구매하기 / 16194. 카드 구매하기 2

🤔문제 해결 S1 | 다이나믹 프로그래밍 dp 리스트를 만든다. dp[i]: 카드 i장을 구매하기 위한 지불 금액의 최솟값 dp[0] = float('inf') (파이썬에서의 최댓값) dp[i-j] + dp[j]: 카드를 j장 구매하기 위한 최솟값과 카드를 i-j장 구매하기 위한 최솟값의 합 ex) dp[2] + dp[3]: 카드를 2장 구매하고 3장구매할 때의 최솟값 dp[i-j] + dp[j] 와 dp[i] 의 값을 비교하여 더 작은 값을 dp에 저장 테스트케이스 1번 예시 dp[0] = float('inf') dp[1] = 1 dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2 dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1..

[python] 백준 - 1722. 순열의 순서

🤔문제 해결 S1 | 수학, 조합론 순열을 보면 itertools의 permutation이 생각난다. 하지만 이 문제에서는 N이 20까지 이므로 20!을 구하는것은 불가능. 먼저 소문제1일 때의 경우를 살펴보자. N = 5, K = 35 일 때(5개의 숫자, 35번째 순열) N = 5 이므로 5! = 120이다. 120 / N 으로 나누면 24가 되는데, 이는 각각의 앞자리 5개가 가지는 경우의 수이다. 앞자리가 1이면 1 ~ 24번째, 앞자리가 2이면 25 ~ 48번째, 앞자리가 3이면 49 ~ 72번째 ... 이다. K = 35이면 25~48이므로 앞자리가 2라는 것을 알 수 있다. 다음 스텝으로 넘어가면 n = 4, k = 35 - 24 = 11이다. 즉, 맨 2 이전의 숫자인 1이 맨 앞자리에 오..

[python] 백준 - 2240. 자두나무

🤔문제 해결 S1 | 다이나믹프로그래밍 1. 답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다. 다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다. 하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다. 홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다. 2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다. dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때 3. %중요% (1) 받아 먹는 조건: a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면 b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 ..

[python] 백준 - 9084. 동전

🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하여 만들 수 있으면 카운트를 세어준다. 4. 위의 표 처럼 각 동전을 꺼냈을 때 미리 만들어진 금액(인덱스)에 꺼낸 동전을 더해서 값을 쌓는다. 💨 다이나믹프로그래밍은 한번 해결한 문제는 다시 해결하지 않는다. 그리고 작은 문제를 해결하여 큰 문제를 해결한다는 의미!!!!!!!!! DP는 항상 어렵다.... 💻소스 코드 def _dp(): dp = [0] * (target + 1) # 경우의 수를 업데이트 할 리스트 dp[0] = 1 for coin in coins: # print('꺼낸 동전: ',c..