DFS27 [ 자바스크립트(JavaScript) ] section08 - 1 - 재귀함수 📍 section08 - 1 - 재귀함수 이번 섹션은 재귀 함수와 완전 탐색(깊이 우선 탐색: DFS)을 배운다. 이전부터 재귀 파트는 어려움을 많이 호소했는데, 이번 섹션을 통해 감을 되찾았으면 좋겠다. 첫 번째 문제는 자연수 N이 입력됐을 때 재귀 함수를 이용하여 1부터 N까지 출력하는 문제다. 이전에 코드업에서 python으로 한번 풀어봤다. 예전에 재귀 문제를 풀었을 때는 하단 before 방법처럼 호출된 재귀 함수를 적고 return이 나오면 다시 올라가는 방법을 사용했는데, 이것의 단점은 재귀가 깊어지면 어떤 코드에서부터 다시 진행해야 하는지 헷갈려서 많은 어려움을 겪었다. 하지만 강의 선생님께서 after 방법처럼 현재 호출된 재귀 함수와 호출된 코드라인을 적어두면 다시 돌아왔을 때 어디서부.. 2021. 9. 15. [ 파이썬(python) ] 백준 4963 - 섬의 개수(DFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 2번을 사용하면 쉽게 해결 할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20. [ 파이썬(python) ] 백준 2606 - 바이러스(DFS) 📌 백준 2606 - 바이러스(DFS) 문제 설명 💡 나의 풀이 코드 업에서 풀었던 문제인데, 다시 풀어봤다. DFS를 이용해서 방문하지 않은 노드가 있을 때 cnt를 누적하는 방법으로 구현했다. 중요한 점은 cnt를 전역변수로 사용했기 때문에 파라미터로 전달하지 않았다. import sys input = sys.stdin.readline def dfs(graph, v, visited): global cnt visited[v] = True for i in graph[v]: if not visited[i]: cnt += 1 dfs(graph, i, visited) PC = int(input()) network = int(input()) graph = [[] for _ in range(PC + 1)] vis.. 2021. 4. 19. [ 파이썬(python) ] 백준 2331 - 반복수열 📌 백준 2331 - 반복수열 문제 설명 💡 나의 풀이 지금까지 2차원 그래프나 리스트를 이용한 문제만 풀었었는데, 1차원의 수 반복을 이용하는 계산은 새로운 접근이 필요했다. 그래서 어떤 탐색을 사용할까 고민하다 BFS를 사용했는데, 감이 잘 잡히지 않았다. 찾아보니까 DFS를 이용하고, 어떤 코드는 아예 DFS를 사용하지도 않았다. 또, DFS를 이용할 때 Flag 방식을 사용하려고 했는데, 오답 판정을 받았다. 현재 값을 파라미터로 전해주지 않아 그런건지.. 도통 이유를 모르겠다. 제일 하단의 fail코드를 보고 왜 안되는지 아시는 고수님들 댓글 부탁드립니다. ㅠㅠ 😂 😂 DFS - 반복 수열을 진행하며 현재 값을 기준으로 다음 원소를 탐색하고, 이전에 나왔던 원소(중복 원소)가 나올 때까지 다음 .. 2021. 4. 17. [ 파이썬(python) ] 백준 1260 - DFS와 BFS 📌 백준 1260 - DFS와 BFS 문제 설명 💡 나의 풀이 BFS와 DFS를 둘 다 사용해야 하는 문제인데 풀이 방법은 다음과 같다. 문제에서 정점 번호가 작은 것을 먼저 방문한다.를 통해 입력값을 인접리스트(adjacent list)으로 넣을 때 sort를 붙여 작은 값부터 들어가게끔 설정했다. dfs의 구현 순서는 다음과 같다. 처음 들어온 값 index의 flag를 True로 바꾼다. 만약, 인접 노드를 방문하지 않았다면(flag = False), 해당 인접노드로 들어가서 방문하지 않은 인접 노드가 없을 때까지 들어간다.(recursive) 재귀문을 탈출하면서 해당 값을 하나씩 출력한다. bfs의 구현순서는 다음과 같다. 처음 들어온 값을 queue에 넣는다. 처음 들어온 값 index의 fla.. 2021. 4. 16. 이전 1 2 3 4 5 6 다음 more
