빠르게 성장하는 개발자

문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게..

1. 완전 이진트리 (Complete Binary Tree)높이가 h이고, 노드 수가 n개 일 때, 포화 이진트리의 노드 번호 1번부터 n번까지 빈자리가 없는 트리 2. 이진 탐색 트리왼쪽 서브트리 < key (루트노드) < 오른쪽 서브트리왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.‘중위 순회’ 하면 오름차순으로 정렬된 값을 얻을 수 있다.def binary(node): global k # 왼쪽이 비어있으면 왼쪽으로 이동 if 2*node 부모이면, # 자리를 변경하고 갱신한다. # 그렇지 않다면, 반복문을 중단한다. Uploaded by N2T

문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하..

1. DFS vs BFSDFS : 탐색 시작점을 기준으로 갈 수 있는 곳까지 방문한 후에, 더이상 갈 수 없으면 마지막으로 방문했던 곳으로 되돌아가서 다시 탐색을 진행하는 방식 ⇒ ‘스택’ 을 활용한다.BFS : 탐색 시작점의 인접한 정점을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 ⇒ ‘큐’ 를 활용한다. 2. 코드로 구현해보기인접행렬을 구하는 것은 DFS 를 참고한다. (https://mummur.tistory.com/37)기본적인 흐름은 다음과 같다.참고로 백준에서는 그냥 list로 진행하면 타임에러가 났다. deque로 진행해야 time error가 나지 않는다.# 준비물 : 인접행렬, 방문했는지 기록할 visited, 방문할 곳을 담은 ..

스택 다음에 배울 자료구조는 큐! (이미지 출처: 위키백과) 1. 큐의 특징큐와 스택의 공통점 : 삽입과 삭제의 위치가 제한적인 자료구조이다.차이점 : 선입-선출 (FIFO). 가장 먼저 삽입된 원소는 가장 먼저 삭제된다. 2. 큐의 구현선형큐초기 공백 큐 생성 ( front와 rear을 모두 -1로 초기화)삽입 (enQueue) : rear += 1을 한 후, 배열원소를 저장한다.삭제 (deQueue) : front += 1을 하여 큐에 남아있게 될 첫번째 원소로 이동하고 값을 리턴한다.공백상태 검사(isEmpty()) : front == rear 일 경우에 공백상태이다포화상태 검사(isFull()) : rear ==n-1 (n:배열의 크기, n-1:마지막인덱스)검색(Qpeek()) : front +=..

비선형구조인 그래프 구조는 그래프로 표현된 자료를 빠짐 없이 검색하는 것이 중요하다.DFS (깊이 우선 탐색)BFS (너비 우선 탐색) 1. DFS란?시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 갈선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 반복하는 순회방법 → 가장 마지막에 만났던 갈림길의 정점으로 돌아가기 위해서 “스택” 을 사용한다. 2. DFS의 기본 구조(출처: 관광이 블로그)DFS를 구하기 위한 준비물은 다음과 같다… 현재 노드와 인접한 노드의 정보를 담은 인접리스트 혹은 인접 행렬방문했는지 여부를 체크할 수 있는 리스트마지막 방문 위치를 담을 수 있는 스택2-1..

1. 스택의 특징선형구조를 갖는다. (자료간의 관계가 1:1이다.)마지막에 삽입한 자료를 가장 먼저 꺼낸다. (LIFO:Last-In-First-Out)자료구조 : 자료를 선형으로 저장할 저장소배열을 사용할 수 있다.스택에서 마지막 삽입된 원소의 위치를 top이라고 부른다. 혹은 stack pointercf ) 1차원 배열을 사용하여 구현할 경우, 구현이 용이하지만 스택의 크기를 변경하기 어렵다는 단점이 있다. → 저장소를 동적으로 할당하여 구현하는 방법이 있다. (복잡하지만 메모리를 효율적으로 사용) 스택의 활용 : 괄호검사, function call 2. 재귀호출function call을 생각해보자. 예를 들어def f(n): if n > 5: return else: print(f"{n} in") f..

1. 최소공배수, 최대공약수, 소수최대공약수를 구하는 방법💡유클리드 호제법2개의 자연수 a, b(a>b)에 대해서 a % b = r 일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.이 과정을 반복해서 나머지가 0이 되었을 때, 이 때 나누는 수가 a 와 b의 최대 공약수 이다.# 공통인 약수 중 가장 큰 수 (GCD) # gcd : greatest common divisor # a > b def gcd(a,b) : r = 0 # 나머지 # a를 나누어 떨어질 때까지 나눈다. while b != 0: r = a % b a = b b = r return a 2. 최소공배수를 구하는 방법# 두 수에 서로 공통으로 존재하는 배수 중 제일 작은 수 # 최소 공배수의 성질 # 두 수 a,b의 최소공배수..