코테35 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. 시간복잡도 요약 시간복잡도란 ?한마디로 알고리즘의 성능이다. 정확히 몇초라는 시간을 의미하는 것이 아니고, 이정도의 입력값과 이런 코드라면 이정도의 시간이 걸릴 것이라는 일종의 예측지표이다. 시간복잡도는 최상, 평균, 최악 3가지 지표가 있지만 보통 코드를 짤 땐 항상 최악의 경우를 상정하고 짜는 것이 일반적이므로 최악의 경우인 Big O notation을 사용한다.왜 시간복잡도를 사용하는가 ?한마디로, 환경에 따라 실행 시간은 다를 수 있기 때문이다. 컴퓨터 HW, 와이파이, 틀어놓은 탭 수 ... 등등 어떤 알고리즘이 실행될 때 사람마다 환경이 모두 다르다. 따라서 이 알고리즘이 나에게는 효과적인데 팀원에게는 안좋을 수 있다. 따라서 더 일반적인 설명을 위해서 시간복잡도를 사용할 수 있고, 이는 환경에 상관없이 알고.. 2024. 7. 15. Programmers 주식가격 💡문제 분석 요약주식가격이 담긴 배열 prices가 주어진다.각 원소별로 몇초간 떨어지지 않았는지 구한다. 1 2 3이라고 하면 순서대로 2초, 1초, 0초간 가격이 떨어지지 않은 것으로 본다.💡알고리즘 설계이중 for문을 사용해서 첫번째 원소를 나머지 원소와 쭉 비교하는데, 만약 가격이 떨어지는 순간이 나오면 break하고 그때까지의 time을 기록하면 된다고 생각했다. 그런데 이중 for문을 쓰면 시간이 초과될 것 같아서 해보고 오버되면 다르게 하려 했는데 오버되지 않았다.생각해보면, 일단 prices 길이가 10만이었기 때문에 이중for문이면 100억번 계산되는 건가 싶었다.그런데 중간에 자기보다 큰 수가 나오면 바로 break되기 때문에 저정도로 큰 계산이 되지는 않을 것으로 생각했다.💡코드.. 2024. 7. 14. 9093 단어 뒤집기 💡문제 분석 요약문장이 주어졌을 때 띄어쓰기를 기준으로, 단어별로 거꾸로 출력해본다.💡알고리즘 설계각 단어별로 reverse 함수같은 것이 있다면 쓸 수 있어보인다.그게 아니라면 어제 했던 것 처럼, deque을 사용하고 해당 단어의 길이만큼 첫번째원소 pop 후 맨 뒤에 append를 반복해도 될 듯 하다.💡코드for _ in range(int(input())): lst = input().split() for i in range(len(lst)): lst[i] = lst[i][::-1] # 각 원소별 순서 뒤집기 print(lst[i], end=' ')💡시간복잡도 문장의 길이만큼만 반복되므로 O(N)이고, 최대 문장 길이가 1000이므로 문제가 없을 것으로 보.. 2024. 7. 13. 이전 1 2 3 4 다음 반응형
