분류 전체보기
[백준/C++] 2630 색종이 만들기
문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의..
[백준/C++] 1927 최소 힙
문제 널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시 배열에 자연수 x를 넣는다 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한..
[백준/C++] 11279 최대 힙
문제 널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 ..
[백준/C++] 11723 집합
문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 ..
비트마스크 란?
11723번 문제를 풀면서 나온 개념을 잠깐 정리해보고자 한다. Bitmask란 비트위에 마스크를 씌우는 방식을 통해서 어떤 위치에 집합의 원소가 존재하는지 아닌지, 추가하는 등의 행위를 말하며, 정수의 이진수 표현을 활용한 기법이다. 비트마스크에서 사용하는 비트의 특징은 다음과 같다. 이진수는 0, 1 만을 가지고, true/fasle 상태를 가진다. 이진수는 십진수로 표현 가능하다. 비트연산은 AND, OR, XOR, NOT, SHIFT를 사용한다 예시로 기존의 비트가 1010으로 표현중일때, 결과를 1110으로 바꾸기 위해서는 (2번째 비트를 1로 변경하기 위해서는) 1010 | 1
[백준/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차원이기 때문에 탐색에 너무 많은 시간이 들게 된다...
프로젝트 진행중..
프로젝트를 열심히 진행하다보니 블로그 포스팅을 계속 까먹는데... 프로젝트는 꽤 원활히 진행되고있다. 다음주쯤에 이제 마무리가 되어서 최종발표를 진행할 것 같은데, 마무리할 시기쯤에 진행한 내용들을 좀 차분히 정리해보려고 한다. 지금 정리하기에는 다른 일들이 바빠서 ㅠㅠ! 일단 지금은 프론트에서 활동하며 react를 활용해서 프로젝트를 진행하고 있고, 막바지 작업을 진행하고 있다.
[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분이 필요하게 된다..