알고리즘/코테 스터디 (2024)37 15651 N과 M (3) 💡문제 분석 요약N, M 값을 받고 1 ~ N까지의 숫자중에서 M개의 숫자를 중복 허용하여 출력한다.오름차순으로 출력한다.💡알고리즘 설계이전에 풀었던 N과 M(9) 문제처럼, DFS를 이용한다.m개의 원소가 모이면 print해주는 탈출조건을 작성해준다.💡코드n, m = map(int, input().split())s = []def backTracking(): # DFS를 이용함 if len(s) == m: # m개가 모였다면 출력 print(*s) return for i in range(1, n+1): # m개의 숫자가 모이는 과정인데, prev를 통해 중복 출력을 방지함. s.append(i) # 1~n까지 값을 넣는 것이기 때문에 굳이 list .. 2024. 7. 23. 15663 N과 M (9) 💡문제 분석 요약N개의 숫자 중에서 M개를 뽑아 순열로 출력한다.이때 중복된 숫자는 출력하지 않는다. ex) 4 4 2중에서 1개 출력하면, 2 4만 출력됨.💡알고리즘 설계DFS 사용 : 백트래킹은 DFS, BFS 둘 다 가능하지만 재귀를 사용한다는 점과 되돌아온다는 맥락에서 DFS가 더 편하고 적합했다.💡코드n, m = map(int, input().split())lst = sorted(list(map(int, input().split())))visited = [0] * ntemp = []def backTracking(): # DFS를 이용함 if len(temp) == m: # 출력조건. m개의 숫자가 쌓일 때까지 백트래킹을 진행함. 다 모이면 출력 print(*temp) .. 2024. 7. 22. 1743 음식물 피하기 💡문제 분석 요약이전에 풀었던 단지 번호붙이기 문제와 거의 유사했다.한마디로 음식물이 뭉쳐져있으면 커지고, 제일 크게 커진 음식물 크기를 구하는 문제였다.이는 DFS, BFS로 탐색하여 해당 구역에 1이 몇개 있는지 구하는 맥락이다.💡알고리즘 설계BFS, DFS 모두 가능하다.💡코드import syssys.setrecursionlimit(10 ** 6)n, m, k = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0] * m for _ in range(n)]foods = [] # 음쓰들foodWaste = 0 # 음쓰dx = [0, 0, 1, -1]dy = [1, -1, 0, 0]for _ in range(k):.. 2024. 7. 21. 2178 미로 탐색 💡문제 분석 요약N, M이 주어졌을 때 N행 M열에 대해 미로를 탈출한다.미로를 탈출하는 최소 거리를 구한다.💡알고리즘 설계최소의 칸수를 구하는 것이므로 BFS를 시도하면 될 것 같다.⚠️주의) 이동 거리가 모두 1로 동일하다면 그냥 BFS 쓰면 되는데, 그게 아니라면 다익스트라를 사용해야한다 !!!!!💡코드import sysfrom collections import dequeinput = sys.stdin.readlinen, m, = map(int, input().split())maze = [[0] * m for _ in range(n)]for i in range(n): # 미로 초기화 tmp = input().rstrip() for j in range(m): maze[i].. 2024. 7. 20. 1697 숨바꼭질 💡문제 분석 요약n, k가 주어졌을 때 n이 k에게 가는 최단 시간을 측정한다.n은 n-1 , n+1 , 2*n 이렇게 3개의 방법으로만 움직일 수 있다.💡알고리즘 설계최단경로이긴 하지만, DP처럼도 풀 수 있어보였다. n을 2*(n-1) , 2*(n+1), 2*n 이렇게 3개중에 하나로 쭉 이어나가다보면 되지 않을까 했지만 실패했다.결국, 최단경로를 찾는 매커니즘은 BFS이기 때문에 BFS로 접근해야했다.💡코드from collections import dequen, k = map(int, input().split())maxSize = 100000visited = [0] * (maxSize + 1) # 각 위치를 방문했는지 여부 & 해당 위치까지 도달하는 데 걸린 시간# 0이 아니니까 방문했다! .. 2024. 7. 19. 1012 유기농 배추 💡문제 분석 요약이 문제와 거의 유사했다. 그리고 저 문제에다가 이차원 배열을 탐색하는 nx, ny 요소만 추가하면 됐다. 이 부분은 여기 문제와 유사했다. 저 두 문제의 방법을 합치면 될 것이다 !결국, 지렁이가 몇마리냐 구하는 것은 DFS/BFS가 몇번 실행되느냐를 구하면 되는 것과 같은 맥락이었다. DFS가 아직은 더 편해서 DFS로 접근해보았다. 결국 모든 노드를 방문하는 맥락에서는 두 방법 모두 사용 가능하다.💡알고리즘 설계인접행렬, 인접리스트 2가지 방법으로 풀 수 있지만 인접행렬로 풀어보았다. 💡코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(5000)# 순서대로 상, 하, 좌, 우로 이동하는 것을 의미dx = [0, 0, 1,.. 2024. 7. 18. 11724 연결 요소의 개수 💡문제 분석 요약방향 없는 그래프에서, "연결 요소"의 개수를 구한다. 연결요소라는 것이 생소했는데, 이는 노드끼리 연결된 묶음의 개수이다.이 말도 이해가 되지 않았지만, 한마디로 DFS가 수행되는 개수를 구하면 된다고 한다.💡알고리즘 설계DFS를 사용하고, 재귀를 이용한다.N의 값이 재귀를 고려하면 꽤 크기 때문에, sys.setrecursionlimit(10**7) 이러한 장치를 걸어줘야한다. (나중에 알게됨)💡코드import sysimput = sys.stdin.readlinesys.setrecursionlimit(10**7)n, m = map(int, input().split()) # 정점개수 n , 간선개수 mgraph = [[False] * (n + 1) for _ in range(n +.. 2024. 7. 17. 2667 단지번호붙이기 💡문제 분석 요약정사각형 모양 지도에 0과 1이 표시되어있고, 1은 집이 있다는 의미이다. 전체 지도에서 1끼리 뭉쳐져 있는 구역이 몇개인지 세고, 각 구역별로 집 개수를 함께 알아내야한다.💡알고리즘 설계처음 생각한 건 인접한 애들끼리 쭉 따라가다가, 1인 애들끼리만 묶고 더이상 없다면 집 전체 개수 + 1 해준다. 인접한 애들이니까 BFS를 사용해야하는 게 아닌가 싶었다. 그렇게 풀다가, 사실은 모든 노드에 대해서 상하좌우를 체크하며 인접노드를 봐야하는 것을 알게 되었다. 결국 두 풀이 모두 가능했고, DFS가 조금 더 편하게 쓸 수 있으니까 DFS를 사용하였다.DFS를 이용해 모든 노드에 대해서 탐색한다.예전에 잠깐 공부했던 경험을 살려, 상하좌우를 dx, dy 리스트로 표현하는 약간의 팁도 살려.. 2024. 7. 16. 1260 DFS와 BFS 💡문제 분석 요약DFS, BFS 기본 문제이다.N개의 정점과 M개의 간선이 주어지고 V 노드에서 탐색을 시작한다.V를 시작으로 방문된 점을 순서대로 출력하면 된다.💡알고리즘 설계정점 탐색을 위한 그래프를 사용한다.DFS는 스택 or 재귀로 풀 수 있다.BFS는 큐를 이용하여 풀 수 있고, 큐는 웬만하면 deque를 선언하는 것이 좋다고 느낀다.💡코드from collections import dequen, m, v = map(int, input().split()) # 정점, 간선, 탐색 시작할 정점의 번호graph = [[False] * (n + 1) for _ in range(n + 1)] # 그래프 선언# 주어진 정보로 정점간 연결하기for _ in range(m): a, b = map(in.. 2024. 7. 15. 이전 1 2 3 4 5 다음 반응형
