백준 문제풀이
[백준/C++] 18870 좌표압축
문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 이번 문제는 좌표압축이 뭔지 배우는것부터 시작했다. 좌표압축의 개념은 아래 포스팅에서 정리했고, 좌표 압축 알고리즘 이란? 백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알..
좌표 압축 알고리즘 이란?
백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알아야 할 것 같아서 정리해본다. 좌표 압축 알고리즘이란? : 모든 구간이 아니라, 중요한 구간이나, 숫자만 들고있는 기법. → 순위가 중요한 알고리즘에서 입력값의 개수 < 입력값의 범위일때 사용한다. 값보다 값의 순위가 중요하기 때문에, 값을 임의의 값으로 변경하되 순위만 유지하여도 문제를 풀 수 있도록 만드는 것이다. 예시로는 카카오 코드 페스티벌 5번 캠핑 문제가 있는데, 이 경우 좌표 x,y의 범위는 0 ~ 2^31-1 이지만, 입력받는 좌표의 개수는 최대 5000개이다. 만약 입력의 좌표를 그대로 반영하여 문제를 푼다고 하면 배열의 크기가 2^31-1 개가 되어야하며, 2차원이기 때문에 탐색에 너무 많은 시간이 들게 된다...
[C++/백준] 11724 연결요소의 개수
문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. DFS문제로, 방향없는 그래프인점을 고려해서 문제를 풀어야한다. 처음에 연결요소가 무슨 의미인지 알지 못해서 찾아봤었는데, 아래처럼 연결된 그래프들로 이루어진 요소들이 연결요소라고 할 수 있다. 아래의 연결요소는 2개로 이루어져있다. 즉, 연결되어있는 덩어리를 확인하면 되는 문..
[C++/백준] 11399 ATM
문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..
[C++/백준] 1931 회의실 배정
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..
[C++/백준] 백준 7576 토마토
문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들..
[C++/ 백준] 2606 바이러스
백준 2606 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 ..
[c++/백준] 1697 숨바꼭질
백준 1697 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. BFS를 사용해서 푸는 문제이다. 수빈이가 택..
연속합 _백준 1912
백준 1912 연속합 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 연속된 수 중, 가장 큰 합을 구하는 문제이다. 크게 어려운 문제는 아니라서, 꽤 빨리 풀기도 한 문제이다. d[i] 를 구할 때, d[i-1] + a[i](수열의 i번째 수) 와 a[i]를 비교하여 더 큰 값을 d[i]로 하고, 배열 d의 최댓값을 출력하면 되는 문제이다. #include using namespace std; int d[100001]; int nums[100001]; int main(void) { int num; scanf("%d", &num); for (int i = 0; i < n..
가장 긴 증가하는 부분 수열 4_ 백준 14002
백준 14002 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 앞에서 작성했던 가장 긴 증가하는 부분 수열의 심화버전의 문제이다. (이전문제는 아래 링크로 들어가면 된다) 2020/07/22 - [백준 문제풀이] - 가장 긴 증가하는 부분 수열_ 백준11053 위 문제에서 조금 더 어려워 진 점은, 가장 긴 증가하는 부분 수열을 출력해야하는 점이다. 즉, 수열의 순서를 저장할 필요가 있는 것인데, 나는 11053 문제의 코드에 더 덧붙이는 방식으로 풀었으므로 (두 문제의 연관성이 크므로, 이 순서로 푸는 것을 추천한다) 11053 문제에서 생각했던 점화식의 흐름에 초점을 맞추어 진행했다. 각각의 부분수열을 저장할 수는 없으므로, d[i]를 구하면서, 하나의 배열을 ..