본문 바로가기

백준98

백준 14567번 : 선수과목 (Prerequisite) (Java) 문제 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 구현 방법 위상 정렬의 대표적인 문제입니다🥶 위상 정렬 (Topology Sort) 이란 방향 그래프에 존재하는 각 정점들의 선행 순서를 배신하지 않으면서 모든 정점을 나열하는 것 입니다. bfs를 이용한 위상정렬의 기본적인 해결 방법 입니다. 1. 진입 차수가 0인 정점을 큐에 저장 2. 선택된 정점과 부속된 간선 삭제 3. 모든 정점이 선택되거나 삭제 될 때까지 위 과정 반복 여기에 이수 학기를 계산해야 했기 때문.. 2022. 2. 9.
백준 2887번 : 행성 터널 (Java) 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 구현 방법 최소 스패닝 문제 이지만!!!!! 주어진 행성의 개수가 100,000개, 모든 행성 간의 거리를 구하면 100,000 * 99,999/2 = 약 500억개 이므로 사용하는 메모리가 메모리 제한인 128MB를 훨씬 초과하게 됩니다. 따라서 다른 방법을 찾아야 했지만 전 찾지 못했고^^ 질문 검색을 참고하여 풀었습니다. 행성을 터널로 연결할 때 드는 비.. 2022. 2. 7.
백준 1113번 : 수영장 만들기 문제 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 구현 방법 한 번에 물의 양을 구하지 않고 한 층씩 해당 높이에서의 고일 수 있는 물을 구하여 더해주었습니다. 값이 입력될 때 수영장의 최대 높이를 구해준다. 높이를 1부터 수영장의 최대 높이만큼 탐색한다. h층의 행, 열을 전부 훑어보며 h보다 낮은 층수가 있다면 방문처리 후 큐에 넣어준다. 4방을 탐색하며 범위안에 들고 방문하지 않고 현재 층수보다 낮은 층수면 큐에.. 2021. 7. 23.
백준 20057번 : 마법사 상어와 토네이도 문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 구현 방법 방향 전환 위 그림을 보면 depth가 1부터 2번씩 좌, 하, 우, 상 순으로 방향 전환 후 depth가 1씩 늘어가는 걸 확인할 수 있습니다. 모래가 흩날리는 과정 상, 하, 좌, 우가 각자 다르지만 상하, 좌우로 묶어서 구분할 수 있습니다. 구현 코드 package BOJ.Gold; import java.io.*; import java.util.. 2021. 7. 21.

티스토리툴바