ProblemSolving

풀이 dfs로 구현 dfs는 stack , bfs는 queue! 입력 중복된 값을 입력하지 못하므로 visited 리스트 생성 dfs for문을 돌며, 만약 방문을 안한 number라면 방문처리를 해주고, stack에 append()해준 뒤 dfs()재귀함수를 호출한다. 또 dfs()안에서는 만약 stack의 값이 M과 같다면 stack 값을 프린트 해주고 return된다. (len(stack) == M)되었다고 가정했을 때 dfs함수가 return되므로 끝난다. visited[number] = False구간으로 이동된다. stack이 빠지고 난 뒤 정상적으로 stack에 쌓이기 위해 false처리가 되고 stack.pop()이 실행된다. import sys input = sys.stdin.readlin..

풀이 bfs로 구현했다. bfs를 구현할때 그냥 외울 것: 넣기 전에 방문 처리하기 입력 문제에서 graph는 무향 그래프이므로, x값에 y, y값에 x를 append bfs 매개변수로 받은 a를 queue에 넣고 while queue:를 통해 반복문을 돈다. 만약 queue에서 나온 값이 b와 같으면 종료return 0 for문을 통해 graphx[x]리스트값을 돌며 아직 방문을 하지 않은 값이라면(visited == 0:) visited 값에 이전 visited값 +1(방문처리)을 해주고 queue.append() 만약 사촌관계가 없다면 visited[b]=0이므로 -1이 출력된다. from collections import deque import sys input = sys.stdin.readlin..

풀이 bfs로 구현 box = []를 하나의 판(?)이라고 생각하자. 이후 for문을 통해 box 안에 토마토의 가로 세로 배열이 들어간다. 만약 box[j][k] == 1 배열 안에 익은 토마토가 있다면 queue에 (i,j,k)값을 저장해준다. 이후, graph.append(box)를 통해 박스가 graph에 append되어 3차원 배열이 만들어진다. dx, dy, dz로 3차원 방향벡터를 만들어준다. bfs()에서 반복문으로 방향벡터를 통해 방문하여 방문한 값(xx,yy,zz)이 graph 안에 있고, 해당 값이 0(익지 않은 토마토)라면 해당 값에 이전값+1(날짜)를 해준 뒤 queue에 append해준다. 이후 반복문을 통해 graph의 값을 꺼내보자. if k == 0:만약 k 값이 0, 즉 ..

DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not vis..

이진 탐색(binary search)이란, 정렬된 자료를 반으로 나누어 탐색하는 방법을 말한다. 자료는 오름차 순으로 정렬되어있어야 하는 전재가 깔려야 한다. 시간 복잡도는 O(logN)으로 순차 탐색과 비교했을때 퍼포먼스가 좋다. (순차탐색(linear search): 순서대로 찾는 방법. 순차탐색의 시간복잡도는 O(N))

정렬 (sorting)이란 , 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 데이터의 개수가 적을 때, 많을 때, 데이터의 범위가 특정 범위로 한정되어 있을때, 거의 정렬되어 있을 때,,, 등 과 같은 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다. 1-1. 선택 정렬(Selection Sort) 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 1-2. 선택 정렬 시간복잡도 구현 방식에 따라 사소한 오차는 있지만, 전체 연산 횟수는 다음과 같다. N +(N-1)+(N-2)+...+2 이는 (N^2+ N-2)/2로 표현 할 수 있는데, 빅오 표기법에 따라서..