최단경로 알고리즘 플로이드 워셜 그래프 내에서 최단경로를 찾는 알고리즘 일반적으로, 모든 정점으로부터 다른 모든 정점으로의 최단경로를 구하는데 사용된다 음수인 가중치를 가진 경로가 존재하더라도 사용할 수 있다 3중 반복문을 이용하여 구현 구현 원리 : 임의의 노드 s에...

이진 탐색 / 이분 탐색 이분 탐색이란? 이진 탐색 알고리즘은 정렬되어있는 리스트로부터 원하는 값이 존재하는지 탐색하는 알고리즘이다. 리스트에 있는 원소들은 오름차순 (혹은 내림차순) 으로 정렬되어있으므로, 우리는 리스트에서 찾으려는 값이 특정 index로부터 ‘왼쪽에 있을지’ 혹은 ‘오른쪽에 있을지’ 알아낼 수 있다. 만약 알아냈다면, ...

문제 링크 : https://www.acmicpc.net/problem/25556 25556 - 포스택 본문 포닉스는 길이가 $N$인 순열 $A$와 네 개의 비어 있는 스택을 가지고 있다. 길이가 $N$인 순열이란, $1$ 이상 $N$ 이하의 서로 다른 정수 $N$개가 임의로 나열된 수열을 말한다. 스택이란 자료구조의 한 종류로...

문제 링크 : https://www.acmicpc.net/problem/1253 1253 - 좋다 본문 $N$개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. $N$개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다....

문제 링크 : https://www.acmicpc.net/problem/1062 1062 - 가르침 본문 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 $K$개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후...

문제 링크 : https://www.acmicpc.net/problem/2230 2230 - 수 고르기 본문 $N$개의 정수로 이루어진 수열 $A[1], A[2], …, A[N]$이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 $M$ 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열...

문제 링크 : https://www.acmicpc.net/problem/11758 11758 - CCW 본문 2차원 좌표 평면 위에 있는 점 3개 $P_1, P_2, P_3$가 주어진다. $P_1, P_2, P_3$를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 $P_1$의 ($x_1,...

문제 링크 : https://www.acmicpc.net/problem/1407 1407 - 2로 몇 번 나누어질까 본문 자연수 $N$이 주어지면, 자연수를 유지하면서 $N$을 $2$로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, $N$의 모든 약수 중 $2$의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 $1...

문제 링크 : https://www.acmicpc.net/problem/2437 2437 - 저울 본문 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건...

문제 링크 : https://www.acmicpc.net/problem/1715 1715 - 카드 정렬하기 본문 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 $A$, $B$라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 $A+B$ 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드...