https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 조건 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임 계단을 밟으면 해당 계단에 쓰여 있는 점수를 얻게 된다. 아래 규칙을 지켜서 얻을 수 있는 점수의 최댓값을 구하라 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net # 조건 NxM 크기의 배열로 표현되는 미로 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸 (1,1) 에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 출력 # 접근 방법 BFS를 통하여 탐색을 진행한다. Queue에 넣어주며 방문기록을 현재 좌표+1로 해준다. 간선의 가중치가 모두 같은 그래프로 생각할 수 있기 때문에 bfs를 이용한다면 최단 경로를 바로 구할 수 있다. import sys sys.s..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net # 조건 흑백 영상을 압축하여 표현하는 데이터 구조 쿼드 트리 흰 점을 0, 검은 점을 1로 표현하는 2차원 배열 모두 0으로만 되어 있으면 압축 결과 '0' 모두 1로만 되어 있으면 압축 결과 '1' 섞여 있다면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 -> 4개의 영상으로 나누어 압축 압축한 결과를 차례대로 괄호 안에 묶어서 표현 2^i 개를 하나로 압축 가능하며 하나로 ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net # 조건 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료구조 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제 데이터를 삽입하는 연산과 데이터를 삭제하는 연산 사용 데이터를 삭제하는 연산은 우선순위가 가장 높은 것을 삭제하는 것과 우선순위가 가장 낮은 것을 삭제하는 것으로 나뉜다...

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net # 조건 수직선 위에 N개의 좌표 X1, X2, ... Xn Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. 1

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net # 조건 2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램 작성 방법의 수를 10,007로 나눈 나머지를 출력하라. # 접근 방법 규칙을 찾는 것이 좋을 것 같다. n = 1 인 경우 1가지 n = 2 인 경우 2가지 n = 3 인 경우 3가지 n = 4 인 경우 5가지 n = 5 인 경우 8가지 f(n) = f(n-2) * 2 + f(n-3) 으로 구할 수 있다. 또는 f(n) = ..

https://www.acmicpc.net/problem/11724 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 # 조건 방향 없는 그래프가 주어질 때, 연결 요소의 개수를 구하라 1

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net # 조건 여러 개의 정사각형 칸들은 하얀색이나 파란색으로 칠해져있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들자. 전체 종이 크기 NxN(N = 2^k) 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 크기가 똑같은 N/2 x N/2 크기의 색종이로 나눈다. 파란색이..

이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개 변수 탐색 문제가 있다. 앞에서 많이 살펴 봤지만 이분 탐색에 대해 간단히 복습해보자. 목차 이분 탐색 LOWER, UPPER BOUND 매개변수 탐색 1. 이분 탐색 정렬된 배열에서 사용 가능한 알고리즘 시작, 끝, 중간점을 이용해 탐색 범위를 절반씩 좁혀가며 탐색한다. target data와 middle data 값을 반복적으로 비교하여 원하는 데이터를 찾는다. 예 - 4를 찾는 과정 # 참고 https://velog.io/@guswns3371/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%A7%A4%EA%B0%9C-%EB%B3%80%EC%88%98-%ED%83%90%EC%83%8..