-
[Impl] BOJ 3190 뱀Algorithms in Python/baekjoon 2021. 2. 22. 13:38
🎈 백준 3190 뱀 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 사과가 있는 칸과 없는 칸, 그리고 몸이 있는 칸을 구분하여야 한다. => 사과가 있는 칸은 1, 사과가 없는 칸은 0, 자신의 몸이 있는 칸은 -1 로 설정한다. • 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. => 종료 조건: - 벽 : nx n or ny n - 자신의 몸 : graph[nx][ny] == -1 ..
-
[Dijkstra] BOJ 1261 알고스팟Algorithms in Python/baekjoon 2021. 2. 15. 01:55
🎈 백준 1261 알고스팟 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. • 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의..
-
[Union-Find] BOJ 10775 공항Algorithms in Python/baekjoon 2021. 2. 8. 01:31
🎈 백준 10775 공항 www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. • 공항에는 P개의 비행기가 순서대로 도착할 예정이며, i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. • 가장 많은 비행기를 공항에 도킹시켜야 한다. => 도킹하는 과정을 탑승구 간의 합집합..
-
[Stack] BOJ 17299 오등큰수Algorithms in Python/baekjoon 2021. 2. 3. 15:47
🎈 백준 17299 오등큰수 www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 오등큰수는 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. => 수열 A에서 등장한 횟수를 카운트해서 저장한다. => 스택을 이용하여 F[A[스택의 top]] 값과 F[A[i]]을 비교한다. F[A[i]]가 더 크면 A[i]가 A[스택의 top]의 오등큰수이다. ✅ 전체 코드 import sys input = sys.std..
-
[Prefix Sum] BOJ 20002 사과나무Algorithms in Python/baekjoon 2021. 2. 3. 14:52
🎈 백준 20002 사과나무 www.acmicpc.net/problem/20002 1~K 까지의 정사각형을 설정하고 과수원 범위만큼 완전탐색하여 최대 총이익을 구할 수 있다. => 또한, Prefix Sum을 이용하여 효율적으로 구현할 수 있다. pre[i][j]에 (0,0)~(i, j) 까지의 구간합을 구한다. arr[i][j]는 주어진 2차원 배열의 총이익이다. pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + arr[i][j] 과수원 범위 안에서 시작점(i, j), 끝점이(i+k, j+k)인 정사각형의 총이익 profit = pre[i+k][j+k] - pre[i-1][j+k] - pre[i+k][j-1] + pre[i-1][j-1] ✅ 전체 코드 ..
-
[Sliding Window] BOJ 10025 게으른 백곰Algorithms in Python/baekjoon 2021. 2. 3. 14:11
🎈 백준 10025 게으른 백곰 www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • x 좌표마다 양동이가 있고, 각 양동이 안에는 g씩의 얼음이 들어있다. => arr 배열을 초기화하고, arr[x] = g 으로 입력값을 받는다. • 앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다. => 엘버트의 닿을 수 있는 거리의 마지막 원소가 주어진 x 좌표의 최대값만큼 이동했을 때까지 고려해야한다. - 좌표의 최..
-
[DFS/BFS] BOJ 18405 경쟁적 전염Algorithms in Python/baekjoon 2021. 2. 1. 13:32
🎈 백준 18405 경쟁적 전염 www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 바이러스는 1초마다 상하좌우 방향으로 증식해 나간다. 또한 어떤 특정 칸에 어떠한 바이러스가 존재하면, 그 곳에는 바이러스가 들어갈 수 없다. => 전형적인 bfs 문제이다. 초기 graph를 0으로 설정하고 바이러스가 있거나 번진 경우 graph를 그 바이러스로 변경시킨다. • 매 초마다 번호가 낮은 종류의 바이러스..
-
[DFS/BFS] BOJ 16234 인구 이동Algorithms in Python/baekjoon 2021. 2. 1. 09:27
🎈 백준 16234 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ❗ 문제의 핵심, 풀이 과정 • 인구 이동은 더 이상 인구 이동이 없을 때까지 지속된다. => 인구 이동이 있는지 없는지 체크가 필요하다. • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다. • 조건을 만족하는 국경선이 모두 열렸다면, 인구 이동을 시작한다 => 조건이 만족하면 모두 열고 하루 동..