FOSCAR-(Autonomous Driving) (146) 썸네일형 리스트형 [2023 알고리즘 스터디] 5조 #4주차 - DFS & BFS 알고리즘 FOSCAR 알고리즘 스터디 4주차 5조 블로깅 - 이승찬 13913 숨바꼭질 4 - 코드 리뷰 박병규 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 풀었습니다 queue에 position과 cost값을 저장해두고 방문하지 않은 position에 대해 다음 풀이를 진행할 수 있도록 하였습니다. x-1, x+1, x.. [2023 알고리즘 스터디] 4조 변준형 4주차 - 백준 7562 BFS(Breadth First Search, 너비우선탐색) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 탐색을 할 때 너비를 우선으로 탐색. 즉 가까운 것 위주로 탐색한다. 이러한 특징때문에 최단경로를 찾는 문제에서 주로 사용. 자료구조 큐(Queue)를 사용함. 문제링크 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제설명 나이트가 이동 가능한 좌표를 dx, dy의 형태로 만들어줍니다. 이동할 때 마다 방문 횟수에 1을 더합니.. [2023 알고리즘 스터디] 1조 김동훈 4주차 - 백준 1388 2606 1260 2644 https://www.youtube.com/watch?v=1vLqC1rItM8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=18 # DFS(Depth-First Search) 깊이 우선 탐색: 그래프에서 깊은 부분을 우선적으로 탐 # 스택(혹은 재귀함수) 이용 ''' 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 ''' def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v,.. [2023 알고리즘 스터디] 2조 이현규 3주차 - 백준 25501, 11866, 17478, 17608 FOSCAR 알고리즘 스터디 3주차 2조 블로깅 스택과 큐 자료구조 그래프 탐색 알고리즘 : DFS/BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘에는 DFS와 BFS가 있음 DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 함 스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있음 큐 자료구조 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 할 수 있음 재귀 함수 재귀함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미 단.. [2023 알고리즘 스터디] 4조 안수빈 3주차 - 백준 10994, 6603, 10799, 13335 스택 & 큐 그래프 탐색 알고리즘 탐색이란? - 많은 양의 데이터 중 원하는 데이터를 찾는 과정 대표적 그래프 탐색 알고리즘 : DFS / BFS 자료구조 - 스택 자료구조 : 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화 가능 삽입과 삭제, 두 연산으로 구성됨 - 큐 자료구조 : 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조 입구와 출구가 모두 뚫혀 있는 터널과 같은 형태로 시각화 가능 (python의 경우) deque 라이브러리 사용 - 효율적인 방법 재귀함수 재귀함수란? - 자기 자신을 다시 호출하는 함수 ※ dfs를 구현할 때 자주 사용되는 방법 중 하나 ★ 재귀함수의 종료 조건을 반드시 명시해야함. 종료 조건을 제대로 명시.. [2023 알고리즘 스터디] 3조 성동현 3주차 - 백준 2161, 11866, 10994, 6603 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다. 그 중 예시를 들 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 얘기하는데 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다. 깊이 우선 탐색이라고 불리우는 DFS와 너비 우선 탐색이라고 불리우는 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 숙지하여야 합니다. 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입니다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있습니다. 큐 자료구조 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있습니다. 재.. [2023 알고리즘 스터디] 1조 김예진 3주차 - 백준 25501, 17608, 2161, 17478 3주차 알고리즘 스터디 스택 & 큐 https://www.youtube.com/watch?v=7iLoLcna7Hw&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=16 재귀 함수 https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17 그래프 탐색 알고리즘 : DFS/BFS -탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 -대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있음 -두 가지는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야한다. 스택 자료구조 -저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 -입구와 출구.. [2023 알고리즘 스터디] 5조 #3주차 - 스택, 큐 FOSCAR 알고리즘 스터디 2주차 5조 블로깅 뱀 - 코드 리뷰 이진호 문제 링크 https://www.acmicpc.net/problem/3190 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 구현에 이용된 자료구조는 큐입니다. 맵을 탐색할 때는 뱀이 현재 진행하는 방향으로 탐색하는것이 중요합니다. 큐에서 머리의 좌표를 꺼낼 때마다 시간을 비교하여 방향을 변환하고 자신의 몸이나 벽을 만나면 시간을 반환합니다. import sys from collections import.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 19 다음
