넘치게 채우기

https://www.acmicpc.net/problem/12755BOJ - 수면 장애문제 유형: 수학, 브루트 포스, 구현문제 난이도: Silver IV시간 제한: 1초메모리 제한: 128MB 문제수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다.한계를 느낀 강민이는 새로운 방법으로 수를 세기로 했다.1부터 숫자를 쭉 이어 붙이면 다음과 같은 숫자열이 생성된다.12345678910111213...강민이는 이 숫자열을 한 숫자씩 떼어서 읽기 시작했다. 수면에 성공한 강민이는 다음날 일어나자마자 "N번째 숫자까지 읽었어!" 라고 기분 좋게 외쳤다.과연 N번째 숫자는 무엇일까..

https://www.acmicpc.net/problem/13021BOJ - 13021 - 공 색칠하기문제 유형: 애드 혹, 수학, 조합론문제 난이도: Silver I시간 제한: 1초메모리 제한: 512MB 문제공 N개가 한 줄로 놓여져 있다. 공은 검정색 또는 흰색으로 칠할 수 있으며, 처음에 모든 공의 색은 흰색이다. 공은 가장 왼쪽이 1번이고, 순서대로 번호가 매겨져 있다.오늘은 공을 칠해보려고 한다. 공은 기계를 이용해서 칠할 수 있는데, 기계는 두 정수 L과 R을 입력으로 받는다. 기계는 L번째 공부터 R번째 공까지를 흰색이나 검정색으로 모두 칠한다.기계를 총 M번 사용했고, 이때 입력한 L과 R을 모두 알고있다. 하지만, 어떤 색으로 칠했는지는 까먹고 말았다. 기계를 모두 M번 사용했을 때, ..

https://www.acmicpc.net/problem/19832BOJ - 19832 - Configuration file문제 유형: 문자열 처리, 파싱, 스택, 해시문제 난이도: Gold IV시간 제한: 2초메모리 제한: 512MB 문제Vadim develops a parser for configuration files of his project. A configuration file consists of blocks delimited with braces: "{" marks the beginning of the block, and "}" marks the end of the block. Blocks can be nested. One block can contains several other bloc..

https://www.acmicpc.net/problem/5052BOJ - Phone List문제 유형: 문자열 처리, 트라이, 정렬문제 난이도: Gold IV 문제전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자긴급전화: 911상근: 97 625 999선영: 91 12 54 26이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력첫째 줄에 테스트 케이스의 개수 t가 주..

https://riveroverflow.hashnode.dev/series/dsa-and-cp

https://www.acmicpc.net/problem/10868BOJ - 최솟값문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 1초메모리 제한: 256MB 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 입력첫째 줄에 N, M이 ..

https://www.acmicpc.net/problem/3353BOJ - Printed Circuit Board문제 유형: 가장 긴 증가하는 부분 수열(LIS)문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제In a printed circuit board, conductive wires are laid on a non-conductive board. Because the conductors in the same layer cannot cross without creating short-circuits, boards with conductors divided into several layers separated by non-conductive board material are u..

https://www.acmicpc.net/problem/1520BOJ - 내리막 길문제 유형: 다이나믹 프로그래밍, dfs문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 ..

BOJ - 케빈 베이컨의 6단계 법칙문제 유형: 플로이드-워셜문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교..

https://www.acmicpc.net/problem/28703BOJ - 28703 - Double It문제 유형: 정렬, 우선순위 큐, 슬라이딩 윈도우, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제양의 정수로 이루어진 길이가 N$N$인 배열 A1,⋯,AN이 주어집니다. 당신은 원하는 만큼 다음 조작을 할 수 있습니다.배열에서 원하는 수 하나를 골라서 2를 곱합니다.조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요. 입력첫 줄에 배열의 길이 N이 주어집니다. (1≤N≤200000)둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤10^9) 출력조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하..