컴굥일지

문제 https://www.acmicpc.net/problem/7795 문제 내용 A의 원소 a와 B의 원소 b가 있을 때 a>b가 될 수 있는 모든 쌍의 개수를 구하는 문제이다. 문제 풀이 정렬 없이 완전탐색을 할 경우 시간초과가 나게 되는 문제이다. (n, m이 20000까지 될 수 있다) 나는 A와 B를 정렬한 후, b보다 a가 크면 A의 원소 중 a보다 큰 값을 계산 없이 카운트하는 방법을 선택했다. 코드 #include #include #include using namespace std; void solution() { int n, m; cin >> n >> m; vector a(n, 0); vector b(m, 0); for (int i = 0; i > a[i]; f..

문제 https://www.acmicpc.net/problem/3986 문제 내용 입력받은 문자열들 중에 "좋은 단어"의 개수를 출력하면 되는 문제이다. "좋은 단어"란 A or B 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 지었을 때, 선이 교차하지 않게 되는 단어이다. 쌍을 지어야 하기 때문에 AAA와 같이 한 글자가 남게 되는 경우도 좋은 단어가 아니다. 문제 풀이 stack을 사용하면 쉽게 해결할 수 있다. 스택이 비어있거나 집어넣으려는 문자와 다른 글자가 제일 위에 있으면, 문자를 집어넣으면 된다. 제일 위의 문자가 현재 문자와 일치하면 pop을 시키면 된다. 문자열을 전부 읽고 나서, 스택이 비어있다면 모두 쌍을 이루었다는 뜻이므로 좋은 단어에 해당한다. 코드 #include #include..

문제 https://www.acmicpc.net/problem/2630 문제 내용 주어진 입력에서 색종이 개수를 구하는 문제이다. 색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반으로 나누어 다시 확인을 해야 한다. 문제 풀이 문제에서 나와있는 대로, n/2를 해나가면 되기 때문에 분할정복 개념이 쓰였다. 만약 범위 내의 칸이 모두 같은 색이 아니라면, 범위를 4 분할하여 다시 탐색하면 된다. 같은 행동을 범위만 다르게 해서 반복하기 때문에, 재귀 함수로 구현하면 된다. 코드 #include #include using namespace std; int arr[128][128]; int n, white, blue; // 범위 내의 칸들이 모두 같은 색인지 ..

문제 https://www.acmicpc.net/problem/2217 문제 내용 입력으로 각각의 로프가 들 수 있는 최대 중량이 주어진다. 이때, 로프를 병렬로 연결하면 각 로프에 걸리는 최대 중량을 나눌 수 있는데, k개의 로프를 사용하면 w인 물체를 들어올릴 때 각각의 로프에 w/k 만큼의 중량이 걸리게 된다. 로프가 여러 개 있고, 로프를 사용하여 물체를 들어올릴 수 있는 최대 중량을 구하는 문제이다. 문제 풀이 병렬로 들어올릴 수 있는 상황을 생각해보자. 예제 1에서는 각각의 로프가 10과 15의 중량을 버틸 수 있는 것으로 주어졌다. 두 로프를 병렬로 연결하여 30짜리 물건을 들 수 있을까? 30/2=15로 각각의 로프에 15의 중량이 걸리기 때문에 최대 중량이 10인 로프는 끊어지게 될 것이..

문제 https://www.acmicpc.net/problem/1439 문제 내용 입력으로 주어진 문자열의 숫자를 전부 같게 만들기 위해 몇 번을 뒤집어야 하는지를 구하면 된다. 110001의 경우 가운데에 있는 000을 111로 한 번만 바꾸면 111111이 되기 때문에 답은 1이다. 1111111의 경우 뒤집지 않아도 숫자가 전부 같으므로 답은 0이 된다. 문제 풀이 처음에는 1로 이루어진 문자열의 개수와, 0으로 이루어진 문자열의 개수를 구한 다음 더 작은 것의 개수를 출력하는 풀이를 떠올렸다. ex) 1100010011111 1로 이뤄진 문자열 : 11, 1, 11111 => 3개 0으로 이뤄진 문자열: 000, 00 => 2개 따라서 답은 2개 하지만 위의 방법을 구현하다보니 인덱스 처리나 경우..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12981 문제 내용 n명의 사람이 번갈아가며 끝말잇기를 한다. 우리가 구해야 하는 것은 가장 먼저 탈락한 사람의 번호와 몇 번째 차례에 탈락했는지이다. (몇 번째 라운드였는지) 만약 탈락자가 없다면 [0,0]을 반환하면 되고, 탈락의 기준은 아래와 같다. 1. 앞 사람이 말한 단어의 마지막 글자로 시작하지 않는 경우 2. 이미 앞에 나온 단어를 말한 경우 문제 풀이 단순히 반복문을 돌며 탈락 조건에 해당하는지 파악하면 되는 구현 문제이다. 반복문이 끝날 때까지 탈락 조건에 걸리는 경우가 없으면, 탈락자가 없다는 뜻이므로 [0,0]을 반환하면 된다. 탈락 조건 중 2번(이미 앞에 나온 단어를 말한..

vector vector container란? C++의 vector는 C++ 표준 라이브러리(Standard Template Library)에 있는 container이다. vector는 원소를 순서대로 보관하는 Sequence Container에 해당하는데, 배열과 달리 동적이기 때문에 자동으로 메모리가 할당되는 배열이라고 생각하면 된다. vector를 생성하면 heap 영역에 생성된다. 기본적으로 맨 뒤에서 원소의 삽입/삭제가 이루어진다. 중간에 값을 삽입하거나 삭제할 수도 있지만, 배열 기반이기 때문에 삽입/삭제가 일어난다면 비효율적이다.(이 경우 linked list를 쓰는게 낫다.) 헤더 아래의 헤더를 추가하면 vector를 사용할 수 있다. #include 선언 & 초기화 //int형 벡터 생성..

문제 https://www.acmicpc.net/problem/2865 문제 내용 참가자 n명의 m개 장르에 대한 능력치가 주어진다. 본선 진출 인원은 k명이고, 본선에서는 단 하나의 장르만 부를 수 있다. 상근이가 참가자별로 장르를 선택해주는데, 이때 본선 진출자들이 본선에서 고른 장르의 능력의 합을 구하면 된다. 문제 풀이 greedy문제이다. 일단 참가자별로 가장 높은 능력을 저장한다. (vector이용) 그리고 능력치를 내림차순으로 정렬한 뒤, 앞에서부터 k개를 더하여 출력하면 된다. 출력 시, 소수점 첫째 자리까지 반올림하여 출력하는 것에 유의하면 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_..

문제 https://www.acmicpc.net/problem/9184 문제 내용 문제에서 주어진 재귀 함수 의사 코드를 코드로 구현하면 되는 문제이다. 문제 풀이 문제에서 주어지는 코드를 보면, w(a, b, c)가 호출되는 수가 많다. 따라서, 재귀 문제이지만 dp(동적계획법)을 이용해서 문제를 풀어야 한다. 문제에서 주어진 재귀 코드 안의 조건을 위에서부터 1,2,3,4로 하자. 1번과 2번 조건은 그대로 재귀 함수로 구현하면 된다. 3번과 4번 조건은 재귀 함수가 많이 호출되기 때문에, dp를 사용해야 한다. 따라서 dp[a][b][c]의 값이 0이 아니라면 이미 계산이 된 것이기 때문에 값을 바로 return 하면 된다. dp[a][b][c]의 값이 0이라면 3번과 4번의 방식으로 계산을 하게 ..

문제 https://www.acmicpc.net/problem/11651 문제 내용 (x, y) 좌표를 입력받아, y좌표를 증가하는 순으로 정렬한다. 만약, y좌표가 같을 경우, x좌표가 증가하는 순으로 정렬하면 된다. 문제 풀이 pair로 입력받아서 sort로 정렬한다. sort로 정렬을 할 때에, 3번째 인자로 compare 함수를 구현하여 넣어준다. 코드 #include #include #include using namespace std; bool compare(paira, pairb) { if (a.second == b.second) { return a.first < b.first; } else { return a.second < b.second; } } int main() { ios_base::..