목록알고리즘/PS (6)

devlog

[PS] 백준 1941 : 소문난 칠공주

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 해설 조금 까다로운 백트래킹 문제 입니다. 문제를 살펴보면 문제에서 주어진 조건은 다음과 같습니다. 1. 총 7명의 학생들로 구성되어야 하며 2. S가 항상 4개 이상인 조합으로 구성되어야 한다, 반대로 Y는 항상 3개 이하여야 한다. 3. 강한 결속력을 위해 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 이렇게 보면 일반적인 DFS, 백 트래킹 문제라고 볼 수 있지만 이 문..
알고리즘/PS 2020. 5. 15. 15:28
[PS] 백준 2458 : 키 순서

문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 해설 이 문제를 처음 위상 정렬 문제로 생각하고 접근하였는데 단순한 위상 정렬의 개념으로는 풀 수 없는 문제 였습니다. 학생의 키가 몇 번째 인지 알 수있는 학생은 어떻게 구할 수 있을까요? 단순하게 생각해서 해당 학생의 키 순서를 알기 위해서는 그 학생보다 키가 작은학생들과 큰 학생들을 모두 알아야 합니다. 즉, 주어진 학생들 과의 관계를 모두 알 수있을 때 비로소 자신의 키가 몇 번째 인지..
알고리즘/PS 2020. 5. 14. 21:01
[PS] 백준 16236 : 아기상어

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 해설 일반적인 BFS 완전탐색을 이용한 시뮬레이션 문제 입니다. 이 문제를 해결하는 핵심 키워드는 바로 문제의 조건에 있습니다..
알고리즘/PS 2020. 5. 7. 23:41
[PS] 백준 10775 : 공항

문제 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 해설 처음 이 문제를 접했을 때 왜 Union-Find 문제인지 깨닫고 접근하기 까지 오랜 시간이 걸렸습니다. 일반적으로 Kruska..
알고리즘/PS 2020. 5. 7. 10:45
[PS] 백준 17472 : 다리 만들기 2

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해설 다리만들기 문제는 BFS와 MST 을 만드는 알고리즘을 이용해서 문제를 해결 할 수 있습니다. MST를 만드는 알고리즘에 대한 설명은 다음 블로그 링크를 참조해주세요. 문제는 크게 두 부분으로 나뉘어 집니다. 1. 바다를 제외한 연결된 영역을 같은 섬 영역으로 표시하고 각 섬마다 구분 지어 주기 2. 각 섬에서 다른 섬까지 이어지는 경로 찾기 1번의 경우 일반적인 ..
알고리즘/PS 2020. 5. 7. 09:58
[PS] 백준 15685 : 드래곤 커브

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 해설 단순 구현 시뮬레이션 문제이지만 패턴을 발..
알고리즘/PS 2020. 4. 10. 05:34
Prev 1 Next