Algorithm/DataStructure

BFS 미로탈출 문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 첫째 줄에 두 정수 N, M(4 = m: continue # 벽이 경우 무시 if graph[nx][ny] == 0: continue # 해당 노드를 처음 방문하는 경우에만 최단거리 기록 if graph[nx][ny] == 1: graph[nx][n..

문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

[Algorithm] 소수 판별 알고리즘 / 에라토스테네스의 체 소수란? 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수 약수가 1과 자기 자신인 수(약수 개수 2개) ex) 2, 3, 5, 7, 11, 13, 17 소수 찾기 코드 # 소수 판별 함수(2이상 자연수) def is_prime_number(x): for i in range(2, x): # 2부터 (x-1)까지의 모든 수를 확인하며 if x % i == 0: # x가 해당 수로 나누어 떨어진다면 return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) # False print(is_prime_number(97)) # True flag 변수 사용 ..

BFS란? Breadth-First Search로 너비 우선 탐색 알고리즘이라고도 한다. 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 그래프를 순회하는 알고리즘 즉, 그래프를 방문한다. 그래프의 모든 정점과 간선을 방문해야한다. 드라마로 예를 들었을 때, DFS는 한 드라마만 골라서 주구장창 본다고 하면, BFS는 여러 드라마를 한 번에 보는 느낌 DFS에는 Back edge, BFS에는 Cross edge가 있다. DFS에선 Stack, BFS에서는 Queue를 이용한다. Properties of BFS Notation Gs : s의 연결된 구성요소 Property 1 BFS(G, s)는 Gs의 모든 정점(vertex)과 간선(edge)을 방문한다. Property 2 BFS(..

DFS란? Depth-Find Search로 깊이 우선 탐색 알고리즘 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 그래프의 모든 Vertex와 Edge를 방문한다. Time Complexity는 O(n+m) => 모든 Vertex, Edge 통해 이동하고 노드와 인접한 노드가 visited인지 체크 * edge 개수에 비례 드라마로 예를 들었을 때, DFS는 한 드라마만 골라서 주구장창 본다고 하면, BFS는 여러 드라마를 한 번에 보는 느낌 DFS에는 Back edge, BFS에는 Cross edge가 있다. DFS에선 Stack(또는 재귀함수) BFS에서는 Queue를 이용한다. Properties of DFS Property 1 DFS(G, v)는 모든 Vertex, Edg..

유클리드 호제법이란? 두 자연수에 대한 최대공약수를 구하는 알고리즘 두 자연수 A, B(A>B)에 대하여 A를 B로 나눈 나머지를 R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. # 유클리드 호제법 # 꼭 a > b가 아니어도 됨 def GCD(a, b): if a % b == 0: # a와 b가 배수관계라면 return b else: return GCD(b, a%b) print(GCD(280, 100)) # 20 print(GCD(100, 280)) # 20

Queue 자료구조는 스택과는 다르게 FIFO(First In First Out) 먼저 들어간 것이 먼저 나오는 방식이다. C++에서 Stack, Queue를 사용할 때는 라이브러리를 이용하여 잘 사용했었다. Python에서 Stack을 구현할 때는 List에 삽입(append), 빼는(pop) append, pop 메서드를 사용한다. 다만, Python에서 Queue를 구현할 때는 Stack처럼 List로 구현해도 되지만, 특정 인덱스에 존재하는 원소를 꺼내기 위해 pop 메서드를 사용하게 되면 원소를 꺼낸 뒤, 원소의 위치를 조절하는 과정이 필요하기 때문에 원소를 꺼내는 과정 자체가 O(n)만큼의 시간 복잡도가 요구된다. 그래서 파이썬에서 Queue를 이용할 때는 List 자료형이 아닌 deque(덱..

그리디 알고리즘 현재 상황에서 가장 좋은 것만 고르는 방법(=탐욕 알고리즘) 순간 순간 가장 좋아 보이는 것을 선택한다. 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다. 매 선택이 그 순간에서는 최적이지만 종합적으로 봤을 땐 최적이 아닐 수도 있다. 예시 문제 1) 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N이 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실..

Vectors Vector or array list -> 보통 python에서는 Vector보다 Array list를 많이 사용하고 Array list가 좀 더 High-level ADT로 유저 친화적 ADT가 제공하는 함수 at(i) : index i에 있는 V의 원소를 리턴, 파라미터 i가 범위 밖으로 벗어나면 error set(i,e) : index i에 있는 원소를 e로 대체, 파라미터 i가 범위 밖으로 벗어나면 error 바꾸기 insert(i,e) : index i에 e를 넣는데, index i 이후 원소들은 모두 오른쪽으로 밀고 빈자리에 e를 삽입, 파라미터 i가 범위 밖으로 벗어나면 error 오른쪽으로 밀기 erase(i) : index i에 있는 원소를 지움, 파라미터 i가 범위 밖으로..

문제 정수를 저장하는 스택을 배열로 구현한 뒤, 입력으로 주어지는 size, empty, top, push, pop 명령어를 처리하는 프로그램을 작성하시오. 명령어는 다음과 같이 총 5가지이다. size : 스택에 저장된 정수의 개수를 출력. empty : 스택이 비어 있으면 1, 비어 있지 않으면 0을 출력. top : 스택의 가장 위에 저장된 정수를 출력. 만약 스택이 비어 있는 경우, -1을 출력. push X : 정수 X(단, 1 ≤ X ≤ 10,000)를 스택에 삽입. 수용할 수 있는 크기를 넘어 서면 FULL을 출력. pop : 스택의 가장 위에 저장된 정수를 출력하면서 삭제. 만약 스택이 비어 있는 경우, -1 을 출력. 입력 첫 번째 줄에 스택의 수용 가능한 크기 수 t (1 ≤ t ≤ 2..