Algorithm Problem/Python

[python] 프로그래머스 - 풍선 터트리기(월간 코드 챌린지 시즌1)

🤔문제 해결 Lv3 풍선이 살아남을 수 있는 조건: 내 풍선 기준 왼쪽 풍선 크기가 클 때 내 풍선 기준 오른쪽 풍선 크기가 클 때 만약 왼쪽과 오른쪽 둘다 크기가 작으면 풍선은 죽는다 이 문제에서 핵심은 풍선의 크기가 가장 작은 녀석들을 하나씩 뽑아주면 되는 것! 값을 기준으로 정렬을 해주면 크기가 가장 작은 풍선(5)은 무조건 살아남는다. - (모두 다 터트릴 수 있다) 크기가 두번째로 작은 풍선(6)도 무조건 살아남는다. - (자신보다 작은 풍선(5)을 터트릴 찬스가 1번 있기 때문) 크기가 세번째로 작은 풍선(7) 부터는 인덱스의 상황에 따라 결정된다. 만약 7이 앞의 두 풍선 사이에 있을 경우 자신의 양쪽이 모두 작기 때문에 풍선은 죽는다. 하지만 두 풍선 사이가 아니라면 ( 5 < 6 < 7 ..

[python] 백준 - 5014. 스타트링크

🤔문제 해결 G5 | BFS, 그래프 갈 수 있는 길이 2가지인 BFS 문제. 한 지점에서 올라가거나 내려가거나 하면서 원하는 층에 도착할 수 있는지 판별한다. 최초 시작점 S에서 올라가거나(U) 내려간다(D) 만약 올라갈 때 건물의 높이보다 높으면 못올라가고, 내려갈 때 1층보다 낮으면 못내려간다. 또 visited리스트를 만들어둬서 이미 방문했었는지 보고 방문을 안했던 층만 방문한다. BFS로 하기 때문에 이미 방문한 층에 한번 더 들르면 큰값이 들어가게 되므로 무조건 손해이다. 계속 방문을 하면서 원하는 지점(G)에 도착한다면 그 값을 리턴해주고, 도착하지 못한다면 'use the stairs' 를 리턴해준다. 💨 💻소스 코드 from collections import deque def bfs():..

[python] 백준 - 3055. 탈출

🤔문제 해결 G5 | BFS, 그래프? 단순히 최단거리를 찾는 것과 달리 맵이 계속 변하는 문제이다. 로직은 간단하다. 고슴도치를 상하좌우로 이동시킨다. 물도 상하좌우로 흘러넘친다. 다시 고슴도치를 상하좌우로 이동시킨다. (하지만 물에 잠겨있는 고슴도치는 이동할 수 없다) 다시 물을 상하좌우로 흘러넘치게한다. 위의 과정을 반복하면서 고슴도치가 굴에 도착하면 끝 💨 💻소스 코드 def flood(w): new_water = [] for x, y in w: for k in range(len(dx)): nx = x + dx[k] ny = y + dy[k] if 0

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

[python] 백준 - 2225. 합분해

🤔문제 해결 G5 | dp, 조합론 DP는 역시 손으로 해야 제맛이다. 예시의 20, 2는 너무 크기 때문에 6, 4로 바꿔서 구해봤다. 열은 N 행은 K이다. 즉 2열 3행은 2를 숫자 3개로 만드는 방법의 가짓수다. 딱 보면 규칙이 보일 것이다. i, j 는 i-1,j 와 i,j-1의 합이라는 것을... 원래의 규칙은 경우의 수를 모두 직접 구해보면 3열4행을 구할 때는 3행의 0~4열까지의 숫자를 더한 값이다. 그 이유는 0을 숫자 2개로: (0,0) 1을 숫자 2개로: (0,1), (1,0) 2를 숫자 2개로: (0,2), (1,1), (2,0) 각각의 경우의 수 뒤에 2, 1, 0 을 붙여주면 숫자 2를 3개로 구성하는 경우의 수는 6이 나온다. 💨 💻소스 코드 N, K = map(int, in..

[python] 백준 - 9251. LCS

🤔문제 해결 G5 | 다이나믹프로그래밍, 문자열 LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다. 순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다. 예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다. LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다. 먼저 위와 같이 DP를 구성한다. 먼저 1번 째 행을 채워보면 AC와 C가 만나서 LCS는 1이다. 두번 째 행을 보자. A와 CA가 만나서 LCS는 1이다. ACA와 CA가 만나서 LCS는 2이다. 세번 째 행을 보자. A와 CAP =..