BerryDevelop

BFS: 너비 우선 탐색 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용 탐색 시작 노드를 큐에 삽입하고 방문처리 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS 동작 예시 1부터 시작하면 1이랑 거리가 가까운 2, 3, 8이 먼저 탐색되고, 그다음 2랑 가까운 7 ••• 마지막으로 거리가 제일 먼 6이 탐색됨 BFS 코드 예제 from collections import deque #BFS 메서드 정의 def bfs(graph, start, visited): #큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]) #현재 노드..

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

더보기 그래프 탐색 알고리즘을 사용하기 위해 알아야할 자료구조를 알아보자 스택 자료구조 선입후출: 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.(ex: 박스 쌓기) 스택 동작 예시 스택 구현 예제(python) 리스트 자료형 사용 - append() :가장 오른쪽에 원소 삽입 - pop(): 가장 오른쪽 원소 삭제 stack = [] #삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack...

문제설명 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 형태 자물쇠와 M x M 크기인 정사각형태 열쇠가 주어짐 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않음 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 함 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 구현 https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그..

구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현 유형의 문제: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기는 어려운 문제 구현유형 예시 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 (언어별로 다를 수 있음) 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제 (문자열은 파이썬이 처리가 쉬운편) 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex 모든 순열, 모든 조합 찾기 등) 일반적으로 알고리즘 문제에서 2차원 공간은 행렬(Matrix)의 의미로 사용됨 시뮬레이션 및 완전 탐색 문제는 2차원 공간에서의 방향 벡터가 자주 활용된다. 시뮬레이션 BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진..

우선순위 큐 - 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐 구현 방법 1) 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도 우선순위 큐 구현방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 ..

삽입정렬 정렬되지 않은 첫 인덱스를 선택 후 하나씩 오른쪽으로 늘어간다. 앞쪽부터 정렬해가며 정렬되어있지 않은 새로운 값이 정렬되어있는 값과 비교하여 작다면 맞는 위치에 삽입하여 정렬한다. firstUnsortedIndex = this is the first index of the unsorted partion i = index used to traverse the sorted partiton from right to left newElement = the value we want to insert into the sorted partion - array[firstUnsortedIndex] java예제 int[] intArray = {20,13, -22,7,34,1,-20}; for(int firstUn..

선택정렬 - 버블정렬과 비슷한 알고리즘 - 배열 중 최댓값을 선택하여 정렬이 되어있지 않은 제일 마지막 자리(오른쪽)로 옮긴다. lastUnsortedIndex = this is the last index of the unsorted partition 비정렬된 마지막 인덱스를 구한다(처음에는 array length -1 ) i = index used to traverse the array from left to right i는 1부터 비정렬된 마지막 인덱스까지 1씩 늘어나며 비교한다 largest = index of largest element in unsorted partition largest 는 비정렬된 값중의 최댓값을 가지고 있는 배열의 인덱스 java 예제 public class Main { p..

버블정렬 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘 - 비교하여 왼쪽이 오른쪽 보다 크다면 둘이 바꿈.(왼쪽->오른쪽) unsortedPartitionIndex = the last index of the unsorted partition i = index used to traverse the array from left to right 특징 - 구현이 간단하다 - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. 시간복잡도 비교 횟수 최상, 평균, 최악 모두 일정 n-1, n-2, … , 2, 1 번 = n(n-1)/2 교환 횟수 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이..

복잡도 - 시간복잡도 : 중요 - 메모리복잡도 : 메모리가 싸서 요새는 큰 문제가 안됨. 티를 만들때 설탕을 얼마나 넣느냐에 따라 필요한 스텝이 늘어난다. Big-O 원하는 설탕 양 : n 필요한 총 단계 = 2n+2 시간복잡도는 O(n)이다. Big-O 종류 O(1) Constant O(logn) Logarithmic O(n) Linear O(nlogn) n log-star n O(n2) Quadratic (발음 법 O of n , O of nlogn ..) 시간복잡도 크기순서 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)