본문 바로가기

코딩 테스트/do it! 알고리즘 코딩테스트100

027 미로 탐색 첫번째 코드 어...DFS보다는 익숙하지 않아도 재귀가 덜 들어가서 할 수 있겠... 네? 행렬이요?! 도와줘요 책님;;; 상하좌우를 살피면서 방문 리스트도 행렬로 만들어 확인하면 된다... 어... 문제를 이해하고 코드를 확인하면 이해가 된다... 근데 과연 나 혼자서 할 수 있을까...? import sys input = sys.stdin.readline from collections import deque dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] n, m = map(int, input().split()) A = [[0] * m for _ in range(n)] visited = [[False] * m for _ in range(n)] for i in range(n): nu.. 2024. 5. 16.
028 트리의 지름 첫번째 코드 BFS에서 평소에 이용하던 visited만이 아닌 distance를 고려해서 구해야 한다. 그렇기 때문에 tuple로 노드와 가중치를 함께 저장해서 하나씩 풀어가는 형식으로 문제를 풀어야 한다! 책의 도움을...ㅎㅎ; 많이 받았지만 그래도 그만큼 BFS에 익숙해지는 거라고 생각하자! import sys input = sys.stdin.readline from collections import deque n = int(input()) A = [[] for _ in range(n+1)] for _ in range(n): data = list(map(int, input().split())) index = 0 s = data[index] index += 1 while True: e = data[in.. 2024. 5. 16.
025 ABCDE 첫번째 코드 먼저 문제 이해를 잘못했었다... 꼭 ABCDE가 아니여도 5개가 얽힐 수 있으면 되는 것이다!! DFS는 뭔가 그림으로 그리거나 하면 이해가 될 듯 하다 하지만 코드로 재귀로 들어가면 작성이 어려운 것 같다... 그래서 이번 코드도 책을 참고했다... 다음에는 꼭 혼자 풀어보고 싶다....... 기출문제에 많이 나오는 유형인데... 그래도 조금은 익숙해지고 있지 않을까..?ㅎㅎ;; import sys input = sys.stdin.readline sys.setrecursionlimit(10000) n, m = map(int, input().split()) arrive = False A = [[] for _ in range(n+1)] visited = [False] * (n+1) def D.. 2024. 5. 14.
026 DFS와 BFS 첫번째 코드 먼저 이번에는 DFS는 꼭 답안을 참고할일을 없애보자...! 라는 목표! BFS는 처음 접하는거니까 기억하면서 풀어보자! 였는데 그래도 DFS는 차근차근 다른 문제 참고하면서 작성한 것 같다! 그리고 느껴지는 건 BFS가 좀 더 코드는 쉬운 느낌이다! (앞으로 혼자 뚝딱할 정도라고는 안했다 ㅎㅎㅎ;;) import sys from collections import deque input = sys.stdin.readline sys.setrecursionlimit(10000) n, m, v = map(int, input().split()) A = [[] for _ in range(n+1)] visited = [False] * (n+1) def DFS(x): print(x, end = ' ') v.. 2024. 5. 14.
024 신기한 소수 첫번째 코드 사실 DFS...아직 어렵다... 책은 정말 똑똑한 친구구나... 023번 문제는 그래도 해당하는 곳에 가서 F를 T로 바꾸고 모두 T가 되면 그만 하는 그런 시스템이라면 024번 문제는 앞의 개념으로 이해하면 소수인 경우에 진행하고 아니면 버리는 식의 재귀 시스템을 돌아가는 코드이다. DFS는 한번 방문하면 다시 방문하지 않는 시스템인데...그러면 여기서는.... 한 자리 수 일때 소수이면 자리수를 추가해서 소수이면 자리수를 추가하고...이런 식으로 다시 한자리 수 일때로 돌아가지 않아서 DFS의 "한번 방문하면 다시 방문하지 않는 시스템"에 포함되는 것인가? import sys input = sys.stdin.readline n = int(input()) def prime(x): for .. 2024. 5. 9.
023 연결 요소의 개수 첫번째 코드 DFS를 처음 접해 관련된 함수 코드를 어떻게 작성해야 할 지 몰라 책을 참고했다 - DFS 함수로 v의 위치가 False이면 지났다고 가정하므로 True로 바꾸고 v를 통해서 갈 수 있는 값들 모두 DFS 함수를 돌리는 과정을 통해 True로 바꾸는 함수를 생성한다 - A라는 리스트 안에 0, 1, 2, ..., n의 값에서 어디로 갈 수 있는 지를 적어넣는다 (양방향의 문제이므로 양방향으로 적어 넣는다) - 마지막으로 해당 함수를 돌리는 코드를 작성한다. 이때 n의 개수만큼 돌려 뺴먹지 않는 수가 없도록 한다 각 수에 대해 DFS를 돌리면 된다! import sys input = sys.stdin.readline n, m = map(int, input().split()) A =[[] fo.. 2024. 5. 9.
728x90

티스토리툴바