본문 바로가기

Algorithm

 (25)
[백준] 14499번_주사위 굴리기 (Python/파이썬) https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고..
[백준] 13460번_구슬 탈출2 (Python/파이썬) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 ..
[알고리즘] 코딩 테스트에서 자주 출제되는 기타 알고리즘 소수(Prime Number) 소수랑 1보다 큰 자연주 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 ( ex. 7 ) def is_prime_number(x): # 2부터 (x-1) 까지의 모든 수를 확인하며 for i in range(2, x-1): if x % i == 0: return False return True print(is_prime_number(4)) print(is_prime_number(13)) # False # True 소수(Prime Number) 성능 분석 2부터 X-1까지의 모든 자연수에 대하여 확인을 하며 연산을 수행 -> O(X) 개선된 소수 판별 알고리즘 약수의 성질 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸 특정한 자연수..
[백준] 2252번_줄 세우기 (Python/파이썬) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력..
[알고리즘] 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall) 플로이드 워셜 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 - 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 - 다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정 X - 2차원 테이블에 최단 거리 정보 저장 - 다이나믹 프로그래밍 유형에 속함 - 각 단계마다 특정한 노드 K를 거쳐 가는 경우 확인 - a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 플로이드 워셜 동작 과정 [초기단계] 그래프 준비하고 최단 거리 테이블 초기화 [1단계] 1번 노드를 거쳐 가는 경우를 고려하여 테이블 갱신 [2단계] 2번 노드를 거쳐 가는 경우를 고려하여 테이블 갱신 [3-4단계] 마지막으로 4번 노드를 거쳐 ..
[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra) 최단경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘 - 다양한 문제 상황들 1 ) 한 지점에서 다른 한 지점까지의 최단경로 2 ) 한 지점에서 다른 모든 지점까지의 최단경로 3 ) 모든 지점에서 다른 모든 지점까지의 최단경로 - 각 지점은 그래프에서 노드로 표현 - 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 - 현실 세계의 도로(간선)은 음의 간선으로 표현 X - 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류(다이나믹 프로그래밍 원리도 이용됨) - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 다익스트라 최단 경로 ..
[알고리즘] 위상 정렬 알고리즘 위상 정렬 - 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 - 예시 ) 선수과목을 고려한 학습 순서 설정 진입차수(Indegree) - 특정 노드로 들어오는 간선의 개수 진출차수(Outdegree) - 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 [큐를 이용한 위상 정렬 알고리즘 동작 과정] 1. 진입차수가 0인 모든 노드를 큐에 넣음 2. 큐가 빌 때까지 다음의 과정을 반복 1 ) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2 ) 새롭게 진입차수가 0이 된 노드를 큐에 넣음 -> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과 위상정렬 그래프 준비 -> 사이클 없는 방향 그래프(DAG) [초기단계] 진입차수가 0인 모든..
[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘 신장 트리 - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함 최소 신장 트리 - 최소한의 비용으로 구성되는 신장 트리를 찾아야 하는 경우 [최소 신장 트리 문제 예시] - N개의 도시가 존재하는 상황 -> 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 - 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로 설치 크루스칼 알고리즘 - 대표적인 최소 신장 트리 알고리즘 - 그리디 알고리즘으로 분류 [크루스칼 알고리즘 동작과정] 1. 간선 데이터를 비용에 따라 오름차순으로 정렬 2. 간선을 하나씩 확인하며 현재의 간..

티스토리툴바