1. 기본 스택 구현 방문배열 visited 초기화 첫 시작정점 v를 방문 처리 그 후 탐색 반복문 수행 v에 인접한 정점 w중에서 아직 방문하지 않은 w를 찾으면, 이미 방문한 v를 스택에 넣고 v를 w로 교체한 후에, w를 방문처리하고 바로 break 그 후 다시 w에 인접한 정점중에서 방문하지 않은 정점을 찾으면, w를 스택에 넣고 새로운 정점으로 교체한 뒤에 방문처리하고 반복 수행 더 이상 방문할 곳이 존재하지 않는다면 스택이 비어있는지 검사한다 스택이 비어있다면, 전체 탐색을 종료 스택이 비어있지 않다면, 하나씩 pop하여 다시 인접한 정점중에서 방문하지 않은 정점이 존재하는지 탐색 수행 visited = [0] * n def dfs(v,visited): visited[v] = 1 stack =..
1. 가장 기본형태 방문배열 visited 생성 빈 큐에 방문 시작할 정점 v를 넣고 v에 대한 방문처리 큐가 빌때까지 반복문 - 큐에서 정점 v를 빼고 v에 대해 할일을 수행하면서 v에 인접한 정점 w중에 방문하지 않은 w라면 다시 큐에 넣고 w에 대해 방문처리 def bfs(v,N): #시작정점 v, 마지막 정점 N #visited 생성 visited = [0] * (N+1) #큐를 생성함 q = [] q.append(v) #시작점이 들어간 큐 ### q=[v] visited[v] = 1 while q: #큐가 비어있지 않다면 탐색 v = q.pop(0) #시작점 뽑아내기 #방문한 v를 이용해 할일 print(v) #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면... for w in..
1. 문제 N*N 배열에 숫자가 들어있는데, 각 행에서 하나씩 숫자를 골라 그들의 합이 최소가 되도록 만들고 싶다. 그런데 세로로 같은 줄에 2개 이상의 숫자를 고를 수는 없다. 어떻게하면 합이 최소가 되도록 숫자를 고를 수 있을까? 2. 나의 풀이 어떻게 풀어야할지 도저히 모르겠더라 그래서 천천히 pseudo code를 생각해보았다 2-1)한 행에 0부터 n-1까지에서 숫자를 하나 고른다 2-2)고른 숫자를 더해준다 2-3)행수에 1을 더해서 다음 행으로 이동한다 2-4)이전 행에 고른 열이 아닌 다른 열에서 숫자 하나를 고른다 2-5)고른 숫자를 재귀적으로 반복함 이런식으로 생각해보고 하나하나 천천히 짜보니까 길이 좀 보이긴 하더라 def pick_num(x,y,sum_value): sum_value..
1. 그래프의 기본 구조 그래프는 노드(node)와 간선(edge)으로 표현되고 이때 노드를 정점(vertex)이라고도 말한다 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'(adjacent)라고 말한다 노드를 도시, 간선을 도로라고 생각해보자. A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서 A와 B를 연결하는 도로(간선)를 거친다고 이해하면 쉬울 것이다 2. 프로그래밍에서 그래프를 표현하는 방식 인접행렬(adjacency matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접리스트(adjacency list) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접행렬 방식은 2차원 배열에 각 ..
1. 재귀함수 DFS/BFS를 구현하려면 재귀함수도 이해하고 있어야한다 재귀함수는 자기 자신을 다시 호출하는 함수 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 이 코드를 실행하면 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다 물론 어느정도 출력하다보면 오류 메시지를 출력한다 재귀의 최대 깊이를 초과했다는 애용으로 파이썬 인터프리터가 호출 횟수의 제한이 있기 때문이다 무한대로 재귀 호출을 할 수는 없으며 애초에 그런 문제 또한 출제될리는 없다 2. 재귀함수 예시 어느 한 컴퓨터공학과 학생..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begi..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
