min's devlog min's devlog

🎈 백준 3190 뱀 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 사과가 있는 칸과 없는 칸, 그리고 몸이 있는 칸을 구분하여야 한다. => 사과가 있는 칸은 1, 사과가 없는 칸은 0, 자신의 몸이 있는 칸은 -1 로 설정한다. • 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. => 종료 조건: - 벽 : nx n or ny n - 자신의 몸 : graph[nx][ny] == -1 ..

🎈 kakao 60057 문자열 압축 programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr ❗ 문제의 핵심, 풀이 과정 • 1개 이상 단위로 문자열을 잘라 압축한다. => 앞에서부터 차례대로 1~len(s) 단위로 잘라서 판단한다. • 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 한다. => min을 이용하여 가장 짧은 문자열의 길이 업데이트한다. ✅ 전체 코드 def solution(s): n = len..

벨만 포드(Bellman Ford) 알고리즘 특정 노드에서 나머지 노드까지의 최단 거리를 찾아주는 알고리즘 • 다익스트라 알고리즘과 비슷하지만 음의 간선이 포함된 상황에서 사용할 수 있다. • 음수 간선의 순환을 감지할 수 있다. • 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다. 다음의 모든 상황에 적용 가능하다. • 모든 간선이 양수 인 경우 • 음수 간선이 있는 경우 - 음수 간선 순환은 없는 경우 - 음수 간선 순환이 있는 경우 벨만 포드 알고리즘 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화 한다. 3. 다음의 과정을 N -1 번 반복한다. - 전체 간선 E개를 하나씩 확인한다. - 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다...

🎈 백준 1261 알고스팟 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. • 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의..

플로이드 워셜(Floyd-Warshall) 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘 • 노드의 개수를 N이라고 할 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신한다. • 각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다. ex) 1번노드를 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려한다. - A -> 1번 노드 -> B 의 비용 확인 후 최단거리 갱신 => 현재 확인하고 있는 노드를 제외하고, N - 1개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한다. 이후에 A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 다시말해 N-1P2개의 쌍을 단계마다 반복해서..

다익스트라(Dijkstra) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 다익스트라 최단 경로 알고리즘 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3번과 4번을 반복한다. * 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘이다. * 각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 계속 갱신해나간다. * 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는..

🎈 백준 10775 공항 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. • 공항에는 P개의 비행기가 순서대로 도착할 예정이며, i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. • 가장 많은 비행기를 공항에 도킹시켜야 한다. => 도킹하는 과정을 탑승구 간의 합집합..

위상 정렬(Topology Sort) 위상 정렬은 순서가 정해져 잇는 일련의 작업을 차례때로 수행해야 할 때 사용할 수 있는 알고리즘이다. 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것이다. 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐가 빌 때까지 다음의 과정을 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. * 진입차수가 0인 것이 없으면(큐가 빈 경우) 사이클을 포함한 것으로 해가 존재하지 않는다. * 한 특정 지접에서 2개 이상의 노드가 큐에 한꺼번에 들어갈 때는, 정렬 결과가 여러가지라는 의미이다. • 위상 정렬 소스코드 from collections im..