컴굥일지

문제 https://www.acmicpc.net/problem/17298 문제 내용 수열이 주어지고, 수열의 각 원소의 오큰등수를 구하면 되는 문제이다. 오큰등수란 자신보다 오른쪽에 있으면서, 자신보다 커야 하며, 그중에서 가장 왼쪽에 있는 수이다. 즉, 자신보다 오른쪽에 있는 수들 중에 가장 가까운 큰 수를 찾으면 되는 문제이다. 문제 풀이 n의 범위가 10^6이기 때문에, 이중 for문으로 돌리면 시간초과가 나게 된다. 그래서 stack을 사용하여 문제를 풀었는데, 수열을 역순으로 탐색하며 문제를 풀면 된다. 기본적으로 모든 원소를 stack에 push하며 나가되, 자신보다 작은 수는 pop을 하고 자신을 push 하는 과정을 진행하면 된다. 아래 글에 풀이가 정말 잘 설명이 되어있다. https:/..

문제 https://www.acmicpc.net/problem/1874 문제 내용 스택에 1~n 숫자를 push와 pop을 할 수 있다. 단, 이때 반드시 오름차순으로 push를 해야만 한다. 우리는 입력으로 주어진 수열을 만들기 위해, 어떤 순서로 push와 pop을 하면 되는지를 구하면 된다. push/pop을 통해 수열을 만들 수 없으면 "NO"를 출력하면 된다. 문제 풀이 예제 1을 순서대로 표시해 보았다. 스택의 가장 위에 있는 값보다 input의 값이 더 작으면 "NO"를 출력하고 끝내야 한다는 점을 주의하면 된다. 코드 #include #include #include using namespace std; int main() { int n; cin >> n; stack st; vector re..

문제 https://www.acmicpc.net/problem/5648 문제 내용 숫자를 여러 개 입력받아, 각 숫자를 거꾸로 뒤집고, 이 숫자들을 정렬하여 출력하면 된다. 이때 주의해야 할 점은, 숫자는 10^12의 범위까지이므로 long long 자료형을 사용해야 하며, 뒤집었을 때 앞에 0이 오면 그 0은 생략해야 한다는 점이다. 문제 풀이 아래 과정을 거치면 된다. 1. 숫자를 "문자열"로 입력받는다. (숫자로 입력받아도 되지만, 어차피 문자열로 다시 바꿔야 한다.) 2. reverse()를 통해 문자열을 뒤집고, 그 문자열을 숫자로 바꾼다. 3. 배열에 집어넣는다. 각 원소별로 위의 과정을 거친 후, 배열에 모든 원소가 들어가면 정렬 후 출력하면 된다. 코드 #include #include #i..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42885 문제 내용 입력으로 사람들의 몸무게 정보를 담은 배열과 구명보트의 무게 제한을 받는다. 구명보트에는 최대 2명까지 탈 수 있으며, 이때 사람들의 몸무게 합이 구명보트의 무게 제한보다 같거나 작아야 한다. 우리는 필요한 구명보트의 최솟값을 구하면 된다. 문제 풀이 먼저 사람들의 몸무게 정보를 담은 배열을 정렬해야 한다. 그리고 양쪽 끝에서부터 차례로 몸무게를 더해서 limit보다 작으면 그 둘을 한 보트에 태운다. 만약 더한 몸무게가 limit보다 큰 경우, 몸무게가 큰 쪽은 혼자 타야 한다. 몸무게가 작은 사람은, 오른쪽-1 위치의 사람과 함께 탈 수도 있겠지만, 몸무게가 큰 큰 사람은..

서론 친구들과 코딩테스트를 대비하여 스터디를 하기로 했다. 코테 문제를 풀고 블로그에 글까지 쓰는 스터디인데, 매주 마감시간을 토요일 오전 10시로 하기로 했다. 슬랙에 과제를 제출하는 방식으로 진행하기로 했는데, 토요일 10시에 자동으로 과제 마감을 알리는 메시지가 뜨면 좋을 것 같아 기능을 찾아보았다. Slack Reminder 매주 원하는 시간에 "과제 제출 마감"이라는 메세지가 가면 되기 때문에, slack의 reminder 기능을 이용했다. https://slack.com/intl/ko-kr/help/articles/208423427-%EB%A6%AC%EB%A7%88%EC%9D%B8%EB%8D%94-%EC%84%A4%EC%A0%95 위의 Slack 공식 링크에 자세한 설명이 나와있다. 나에게 보..

문제 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개 하지만 위의 방법을 구현하다보니 인덱스 처리나 경우..