분류 전체보기
-
BOJ) 키 순서 (2458 번)알고리즘/백준 2021. 2. 10. 16:39
키 순서 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net Floyd Warshall 아래는 위키에 설명된 내용을 가져왔다. 플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다.[3] 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘[4]과, 스티븐 워셜이 1962년에 발표한 알고리즘[5]과 그래프의 추이적 폐포를 찾는다는 점,[6]그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과..
-
BOJ) 치즈알고리즘/백준 2021. 2. 5. 18:24
치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음에는, 4면을 검사하면서 공기와 접촉하지 않은 치즈들의 지워지는 시간을 1시간씩 증가 시켰었다. 하지만, 문제의 조건에서 모든 공기가 치즈를 녹이는 것이 아니라, 가장 외부에 있는 공기들만 치즈를 녹인다는 조건이 있었다. 또한, 맵의 테두리는 공기로만 주어진다는 조건이 있어서 BFS를 이용했다. 외부 공기의 위치와 가장 외부에 노출된 치즈의 위치를 저장할 큐 두 개를 선언해주었다. 0,0을 시작으로 외부 공기를 큐에 저장하면서, 가장 외부에 닿은 치즈들의 좌표 또한 다른 ..
-
BOJ) 보석알고리즘/백준 2021. 2. 5. 00:16
보석 2492번: 보석 첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다(1 ≤ N, M ≤ 1,000,000). T는 금강석의 개수를 나타내고, K는 정사각형의 크 www.acmicpc.net 정말 어려운 문제였다. M by N 크기의 map이 주어지는데, 이 맵에 금강석이 묻혀있는 정보가 주어진다. n과 m은 1 ~ 1,000,000의 숫자로 주어지고, 금강석은 최대 100개 까지 주어진다. 또한, 정사각형의 한 변의 길이가 되는 k가 주어지는데, 이 정사각형을 임의로 맵에 그렸을 때, 가장 많은 금강석을 갖게되는 정사각형의 왼쪽 위 꼭짓점의 위치와 금강석의 개수를 출력하는 문제다. 우선, 이 문제가 슬라이딩 윈도우로..
-
BOJ) 멀티탭 스케줄링알고리즘/백준 2021. 2. 5. 00:02
멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net N개의 구멍이 있는 멀티탭이 주어지고, 멀티탭 사용을 해야하는 전자제품의 순서가 K 개 주어진다. 전자제품은 1 ~ K 번의 고유 숫자를 가지고 있다. 코드는 O(k^2*n)의 시간 복잡도를 보이지만, N과 K의 최댓값이 100이기 때문에 크게 적당히 빠른 속도를 보여준다. 우선 멀티탭에 꽂혀있는 전자제품을 파악하기 위해 list를 선언해주었다. k개의 대기 열을 돌면서, 멀티탭에 구멍이 있는지 확인했다.남은 구멍이 없는 경우, 현재 멀티탭에 꽂..
-
BOJ) 캐슬 디펜스 (17135 번)알고리즘/백준 2021. 2. 3. 18:03
캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각보다 많이 어려웠던 문제였다. 적을 제거하는 규칙을 찾아 글로는 정리가 됐지만, 어떻게 코드로 구현해야할지 감이 오질 않았다. 그래서, 다른 블로그 글을 찾았고, 여기글을 많이 참고했다. 궁수가 적을 죽이는 순서는 삼각형을 그렸을 때, 좌측, 상단, 우측의 꼭지점 순서라고 생각하면 편하다. 공격 범위에 따라 위와 같은 순서로 적을 죽이게 된다. 범위 : 1 => y-1 범위 : 2 => (x-1,y-1) ~> (x, y-2) ~> (x+1, y-1) 이런 식..
-
BOJ) 조합 (2407 번)알고리즘/백준 2021. 2. 3. 17:43
조합 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 수학의 조합(Combination)을 구현하는 문제다. 조합 자체는 여러 방법으로 구할 수 있지만, 반복문을 통해 풀기로 했다. 그래서 combination을 직접 몇 개 써보면서 규칙을 찾았다. nCm => n! / ((n - m)! * m!) 이라는 공식이 있는데, 이를 약분하면 nCm => (n*n-1*... *n-m+1) / (m*m-1*...*1) 라는 식이 나온다. n =10인 경우를 살펴보자 N M 식 값 10 0 10! / ( (10 -0)! * 0! ) => 10! / 10! 1 10 1 10! / ( (10-1)! * 1! ) => 10! / 9! => ..
-
BOJ) 스택 수열 (1874 번)알고리즘/백준 2021. 2. 3. 17:26
스택 수열 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 ~ n의 수를 스택에 넣었다가 뽑아 늘어놓아서 하나의 수열을 만든다. 이때, 스택에 push하는 순서가 반드시 오름차순을 지켜야한다. 조건에 맞으면 push와 pop하는 행위에 대한 문자열을, 충족하지 못하면 NO를 출력하는 문제다. 문제는 간단했다. 배열을 돌면서 현재 스택의 top과 같은지, 혹은 대소인지 비교해주어 문제를 풀었다. 스택의 top보다 순회중인 배열..