분류 전체보기

[python] 프로그래머스 - 단어 퍼즐(2017 팁스타운)

🤔문제 해결 Lv4 | 다이나믹 프로그래밍 풀이 방법은 앞에서 부터 문자 하나하나 선택한다. 'b', 'a', 'n', ... 그 문자로 끝나는 단어가 strs에 들어있는지 확인한다. 있으면 현재까지 썼던 단어 개수(dp[i])와 그 문자를 사용했을 때의 단어 개수를 비교해서 최솟값으로 갱신 (말이 너무 어렵다...) ["ba", "na", "n", "a"] 와 "banana"로 테스트 해보면 맨처음 "b"로 끝나는 단어는 없으므로 pass 다음 "a"로 끝나는 단어는 "a"와 "ba"가 있다. - "na"는 조건에 맞지 않음 "a"를 선택했을 때는 아무일도 없다. why? 처음에 b로 끝나는 단어가 없어서 값이 무한대인 상태 "ba"를 선택하면 1로 갱신해준다. - (단어 하나만으로 "ba"를 만들었다..

[python] 프로그래머스 - 징검다리

🤔문제 해결 Lv4 | 이분 탐색 딱 보자마자 이분탐색인지는 모르겠다. 하지만 문제 카테고리에 써있다. 이분탐색을 하려면 어떤 값을 왔다 갔다 이분탐색할지 정해야 한다. 여기서는 답으로 구해야 하는 최댓값을 이분탐색 했다. 먼저 답을 정해놓고 시작한다. 0과 마지막 지점인 distance(25)를 가지고 가운데 값으로 12로 정했다. 이 문제에 답이 12라면 바위를 n개 제거했을 때 최소 거리가 12인 녀석이 있어야 한다. 처음 위치를 0으로 두고 다음 바위까지의 거리가 mid(12) 보다 작으면 제거 아니면 그 바위로 이동 0 에서 2 까지의 거리 2 12: 살려둠 and 14로 이동 14 에서 17 ..

[python] 프로그래머스 - N-Queen

🤔문제 해결 Lv3 | 백트래킹, DFS 규칙은 체스말의 좌우, 위아래, 대각선 모두 겹치지 않게 하는 것이다! 하지만 모든 규칙을 하나하나 체크하면 효율성 마지막에서 시간초과가 발생한다! 위아래 규칙: visited 리스트를 만들어서 세로(열) 한칸에 하나씩만 들어갈 수 있게 한다. 좌우 규칙: 한번 말을 놓으면 무조건 다음 행으로 넘어간다. 대각선 규칙: 말을 놓을 준비를 하고, 그 자리의 왼쪽 위대각선과, 오른쪽 위대각선에 말이 있는지 체크! 마지막 행까지 말을 둘 수 있으면 성공! 💨 💻소스 코드 def solution(n): answer = 0 chess = [[0] * n for _ in range(n)] # 체스판 visited = [0] * (n + 1) # 세로칸 방문 체크 # 조건에 일..

[python] 프로그래머스 - 도둑질

🤔문제 해결 Lv4 | DP "인접한 집은 털 수 없다" 까지는 크게 어려운 문제가 아니지만 "마을이 원형으로 되어 있다" 에서 한번 더 생각하게 하는 문제!! -> 0번째 집을 터는 경우( 마지막 집을 털지 못한다 )와 0번째 집을 안터는 경우 두가지로 나눌 수 있다. 먼저 0번집을 털 경우! 0번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 0번집을 턴다. dp[0] = money[0] 1번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 1번집을 터는 경우지만 우리는 1번집을 반드시 털었다고 가정했으므로 인접한 2번집은 털 수 없다. dp[1] = 0 2번집에 들렀을 때: 인접한 1번집이 아닌 0번집 또는 -1번집(2번일 때는 없다) 중 돈을 많이 가져왔던 집에서 온다. dp[2] = money[i..

[python] 프로그래머스 - 여행경로

🤔문제 해결 Lv3 | DFS 간단한 DFS 문제인줄 알았지만 조금 복잡한 문제이다. 그냥 풀면 테스트케이스 1,2번이 틀리게 된다. 이유는 중간에 길이 끊어지면 안되기 때문.예를 들어 이런 테스트 케이스가 있다고 했을 때 - ( 예외 케이스 ) 위와 같이 두가지 경로가 나올 것이다. 문제에서는 오름차순대로 진행하라고 했지만 B를 먼저가게 된다면 모든 티켓을 이용할 수 없기 때문에 답이 되지 않는다. 여기서 D까지 갔다가 길을 못찾고 A로 다시 돌아가야 하는데 어떻게 할까 고민하던중 길이 끊어진 D가 마지막이겠다 라고 생각해서 경로를 거꾸로 넣기로 했다. 길이 끊어져 있는 answer에 D를 저장하고, D가없어지면 B도 끊어진다. answer 에 B를 저장한다. 하지만 A는 B가 없어도 C가 있기 때문에..

[python] 프로그래머스 - 무지의 먹방 라이브(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv4 | 우선순위 큐? 가장 처음 생각난건 역시 1초씩 전부 돌아보자!! 하지만 역시나 시간초과 발생 😂🤣 음식을 한꺼번에 뺄순 없을까 생각해서 가장 적은 음식의 수만큼 사이클을 돌기로 했다. 예를 들어 음식이 [ 5,5,3,3,6 ] 이라면 3만큼 한꺼번에 돌아주는 것이다. 음식이 3만큼 있고, 전체 길이가 5 이므로, 15초 뒤에는 [ 2,2,0,0,3 ] 이 된다고 상상만!!! 직접 빼주고 하면 시간 초과 다음은 2만큼 있고, 전체 길이가 3 이므로 (0은 취급 안함), 6 초 뒤에는 [ 0,0,0,0,1 ] 역시 상상만 하자 위의 방법 처럼 한꺼번에 빼주는데 가장 적은 음식은 어떻게 꺼내냐하면 바로 힙큐를 쓰자. 힙큐에 음식의 양과 해당 음식의 번호를 차례로 넣으면 가장 작은 음식을..