넘치게 채우기

https://www.acmicpc.net/problem/2042BOJ - 구간 합 구하기문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 ..

https://www.acmicpc.net/problem/2263BOJ - 트리의 순회문제 유형: 트리, dfs, 분할 정복문제 난이도: Gold I시간 제한: 5초메모리 제한: 128MB 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력첫째 줄에 프리오더를 출력한다. 풀이중위순회의 정보는 노드들간의 좌우관계를 알려준다.후위순회에서의 마지막원소는 항상 루트노드의 값이다.즉, 루트노드를 중위순회..

https://www.acmicpc.net/problem/16566BOJ - 카드 게임문제 유형: 분리 집합, 이진 탐색, 유니온-파인드문제 난이도: Platinum V시간 제한: 1.2초메모리 제한: 512MB 문제철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번..

https://www.acmicpc.net/problem/17143BOJ - 낚시왕문제 유형: 구현, 시뮬레이션문제 난이도: Gold I시간 제한: 1초메모리 제한: 512MB 문제낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.낚시왕이 오른쪽으로 한 칸 이동한다.낚시왕이 있는 열에 있..

https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal/description/leetcode - Check if One String Swap Can Make Strings Equal문제 유형: 투 포인터문제 난이도: Easy 문제You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.Return true if it is possible ..

https://www.acmicpc.net/problem/2162BOJ - 선분 그룹문제 유형: CCW, 선형대수, 기하학, 유니온-파인드, 분리 집합문제 난이도: Platinum V시간 제한: 2초메모리 제한: 128MB 문제N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해..

https://www.acmicpc.net/problem/15649BOJ - N과 M (1)문제 유형: 백트래킹문제 난이도: Silver III시간 제한: 1초메모리 제한: 512MB 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이만약 현재 수를 수열에 포함하지 않았다면, 포함시키고 재귀호출한다. 재귀호출이 끝났다면..

https://www.acmicpc.net/problem/2583BOJ - 영역 구하기문제 유형: dfs, bfs, 그래프문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머..

https://www.acmicpc.net/problem/7562BOJ - 나이트의 이동문제 유형: bfs, 그래프, 최단 경로문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘..

https://www.acmicpc.net/problem/2098BOJ - 외판원 순회문제 유형: TSP(외판원 순회), 비트마스킹, 다이나믹 프로그래밍, dfs문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 ..