본문 바로가기

DFS13

[LeetCode] Number of Islands https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 매우 유명한 섬 문제 dfs로 풀이했다 class Solution: def numIslands(self, grid: List[List[str]]) -> int: move = [(0,1),(0,-1),(1,0),(-1,0)] def OOB(x, y): return x=len(grid) or y=l.. 2022. 3. 25.
[프로그래머스] 양과 늑대(Python) https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 쉽지 않았던 문제다. 풀면서 생겼던 문제는 현재 상태에서 갈 수 있는 노드를 찾는 과정에서 객체를 같이 참조하면서 무한루프를 돌았다. 그 부분을 어떻게 할지 고민했다. 알고리즘은 다음과 같다. 1. 루트 노드부터 .. 2022. 1. 28.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 동굴 탐험 (Python) https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr DFS에 조건을 잘 걸어야 하는 문제다 from collections import defaultdict import sys sys.setrecu.. 2021. 12. 9.
[프로그래머스] 퍼즐 조각 채우기 (Python) https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr dfs로 풀이했다. 알고리즘은 다음과 같다. 1. 게임보드의 모양을 구한다. 모양은 2차원 배열의 좌표 순서대로 찾으며, 방문하지 .. 2021. 11. 29.
[프로그래머스] N-Queen (Python) https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 다른 풀이를 참고했다. 아직 dfs를 짜는데 좀 익숙하지 않은 것 같다. 나중에 다시 살펴봐야겠다. import sys sys.setrecursionlimit(10**6) def dfs(queen,n,row): answer = 0 if n == row: return 1 for i in range(n): queen[row] = i for j in r.. 2021. 11. 23.
[프로그래머스] 모두 0으로 만들기 (Python) https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr DFS 문제다. queue로 BFS 풀려했는데 잘 풀리지 않았다 DFS 방식이 좀 친숙해지는 계기가 된 것 같다. import sys sys.setrecursionlimit(300000) answer =0 def solution(a,edges): global answer if sum(a) !=0: return -1 graph = [[] for .. 2021. 11. 17.
[프로그래머스] 빛의 경로 사이클 (Python) https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 각각의 위치에 대해서 모든 방향으로 방문했는지 체크하면서, 이동할 때에 규칙을 잘 설정해야 한다. 마지막에 오름차순으로 정렬하는걸 못 봐서 한참 헤맸다. 나의 풀이 from collections import deque def solution(grid): answer =[] len_x, len_y = len(grid),len(grid[.. 2021. 11. 7.
[프로그래머스] 피로도 (Python) https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 그리디 + 완전 탐색으로 풀었다. 던전 총개수를 세고, 최대 던전 개수부터 내려오면서 순열을 만든 다음 모두 탐색하며 조건에 만족하면 바로 return 하도록 코드를 작성했다. 나의 풀이 from itertools import permutations def solution(k, dungeons): dungeons_count = len(dungeons) d.. 2021. 11. 1.
[프로그래머스] 여행 경로(Python) https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 처음 문제를 풀 때는 알파벳 정렬만 따져서 풀어서 일부 문제가 안 풀렸다. 내가 틀리는 유형의 테스트 케이스는 하단과 같다. tickets = [["ICN", "AOO"], ["AOO", "BOO"], ["AOO", "COO"], ["COO", "AOO"], ["BOO", "ZOO"]] answer.. 2021. 10. 21.
[프로그래머스] 타겟 넘버 (Python) https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 참고 https://hkim-data.tistory.com/31?category=1016184 #2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0d.. 2021. 10. 21.
#2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 이 포스트는 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다. 그리디 알고리즘 : 현재 상태에서 지금 당장 좋은 것만 고르는 방법-> 이 방법을 이용했을 때 최적의 해를 구할 수 있는지 검토하는 것이 필요함. 스택 , 큐 : - 스택은 선입 후출 형태 list를 그대로 사용한다. append, pop을 활용. - 큐는 선입선출 형태 from collections.. 2021. 10. 20.

티스토리툴바