본문 바로가기

백준680

[분할정복/DQ] 백준 1074 Z - Python [ Contents ] 1. 문제 (링크 참조) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 풀이 위와 같이 Z 모양으로 이동하는 규칙이 있습니다. 이 때, 2^N * 2^N크기의 r행 c열의 순서를 구하는 문제입니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 .. 2022. 2. 25.
[탐색/BFS] 백준 7576 토마토 - Python [ Contents ] 1. 문제 (링크 참조) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 문제 풀이 모든 토마토가 다 익는 데 걸리는 시간을 구하는 문제입니다. 익은 토마토의 상하좌우에 안 익은 토마토가 있으면, 하루 뒤에 익게 됩니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용.. 2022. 2. 24.
[탐색/BFS] 백준 1697 숨바꼭질 - Python [ Contents ] 1. 문제 (링크 참조) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 문제 풀이 출발 지점 N에서 도착 지점 K까지 가장 빠르게 가는 방법을 찾는 문제입니다. 1) X - 1 2) X + 1 3) 2 * X 3가지 방법으로 움직일 수 있고 최대한 적게 이동해서 도착해야 합니다. 1차원 그래프이기 때문에, 처음에는 DP문제인 줄 알았습니다. 하지만 DP처럼 모든 경우를 탐색할 순 없으며, 그럴 이유도 없습니다. 2022.02.23 - [Algorithm.. 2022. 2. 24.
[탐색/BFS] 백준 1012 유기농 배추 - Python [ Contents ] 1. 문제 (링크 참조) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 문제 풀이 인접한 유기농 배추의 연결 요소 개수를 세는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First Sea.. 2022. 2. 23.
[탐색/DFS] 백준 11724 연결 요소의 개수 - Python [ Contents ] 1. 문제 (링크 참조) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2. 문제 풀이 연결 요소의 개수를 구하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠.. 2022. 2. 23.
[탐색/BFS] 백준 2606 바이러스 - Python [ Contents ] 1. 문제 (링크 참조) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 문제 풀이 1번 컴퓨터와 연결되어 있는 컴퓨터의 수를 구하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath Fi.. 2022. 2. 23.
[정렬/탐색] 백준 18870 좌표 압축 - Python [ Contents ] 1. 문제 (링크 참조) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2. 문제 풀이 오름차순으로 정렬한 뒤 최솟값부터 0, 1, 2 ... 매칭하는 문제입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력.. 2022. 2. 22.
[구현/문자열] 백준 5525 IOIOI - Python [ Contents ] 1. 문제 (링크 참조) 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 2. 문제 풀이 IOIOI가 주어진 문자열에 몇 번 포함되는지 구하는 문제입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적.. 2022. 2. 22.
[동적계획법/DP] 백준 2579 계단 오르기 - Python [ Contents ] 1. 문제 (링크 참조) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 문제 풀이 1. 한 번에 1계단 또는 2계단씩 오를 수 있다. 2. 연속된 3계단을 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야 한다. 계단마다 획득 가능한 점수가 있고, 위 규칙을 따라 최대 점수를 획득해야 합니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ C.. 2022. 2. 22.

티스토리툴바