kth990303의 코딩 블로그

오랜만에 BOJ 대회에 참여해보았다! 신촌 지역 연합대학들은 ps/알고리즘 스터디들 서로 진행하고 매 해 겨울, 여름마다 대회를 연다. 나는 신촌 연합대학에 속하지 않기 때문에 open contest 참여자로 응시해보았다. 요즘 우테코를 하느라 백준을 많이 못해서 내 감이 얼마나 잘 유지되고 있는지 중간체크도 할 겸, 대회시작 40분 쯤 후부터 뒤늦게 참여해보았다. 꽤 만족스러운 결과였다 :) 물론, 등수가 높다고 꼭 잘하는건 아니긴 하지만, 풀 만한 문제들은 만족스럽게 잘 푼 듯하다. 참여 후기 / 느낀점 수학적인 능력을 많이 요구하는 느낌이었다. 운영진분들께서 다들 수학을 잘하시다보니 ㅎㅎ 초보자 입장에선 꽤 헤맬 듯한 문제들이 많았다고 생각한다. C번부터 초보자에게는 굉장히 어려웠을 것 같다고 생각..

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net N N >> K; memset(d, -1, sizeof(d)); if (!K) { for (int i = 0; i < N; i++) { cout

백준 잔디 채우려고 G4..G2 티어 중 랜덤하게 뽑아본 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14452 14452번: Cow Dance Show After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia". The only aspect of the show that remains to be determined is the size of the stage www.acmicpc.net 여기서 제일 중요한 점! 소 ..

오랜만에 가벼운 문제로 백준 포스팅을 들고와보았다~! 문제는 아래와 같다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호 관련 문제는 언제나 재밌다 재미는 개뿔...ㅠㅠ 의식의 흐름 및 해설 1. O(N^2) dp 괄호를 보면 보통 나는 stack을 떠올리는데, 이 문제는 경우의 수를 묻기 때문에 바로 dp를 떠올릴 수 있었다. 괄호 개수에 따라 충분히 메모이제이션이 가능하다는 사실은 한눈에 보이기 때문. 일단 N이 상당히 작은 데다가..

제목이 뭐 이리 길어 문제는 아래와 같다. https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 이걸 A번으로 생각하시다니... wookje님이 워낙 god이시긴 하지만 이럴 땐 진짜... 말잇못 나만 모르는 웰노운 소재가 있어서 기록해두는 문제. 의식의 흐름 및 해설 대체 직사각형을 어떻게 할 지 한참 고민했다. 일단 일렬로 나열된 트리노드들의 x값, y값을 어떻게 비교할지조..

이 문제도 어떻게 보면 쉬운데, 어떻게 보면 어려운 문제. 스터디그룹 연습 D번으로 진행된 문제다. https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 의식의 흐름 및 해설 이 문제를 보고 TSP가 떠올라 바로 TSP로 접근하려 했으나, 이미 방문한 행성을 다시 방문할 수 있다는 말에 다시 한 번 곰곰이 고민해보게 됐다. 이상하게 바로 아이디어가 떠오르지 않았으며, 꽤나 고생을 했는데, 생각해보니까 floyd 알고리즘이 어떤 행성을 방문하든 ..

스터디그룹에서 연습 C번으로 진행된 문제. 어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 의식의 흐름 및 해설 물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제. 이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난..

*주의* 정해와 다르게 해결하였으며, 정해 풀이는 올리지 않습니다. 스터디그룹 연습에서 B번으로 나온 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 의식의 흐름 및 해설 문제 이해가 조금 힘든데, 쉽게 풀이하자면 모든 포지션에 한 명 이상의 선수가 위치해야 된다. 모든 포지션에 선수가 위치해야 되므로 TSP와 똑같다. 그러므로 이 문제와 거의 유사하다. https://kth990303.tistory.com/61 [BOJ] 백준 1311. 할 ..

스터디그룹에서 진행한 연습 중 A번으로 나왔던 문제. 문제가 굉장히 긴데, 실생활에서 흔히 마주칠만한 좋은 문제였다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 의식의 흐름 및 해설 스키를 못타는 날이 중간에 껴 있더라도 이용권을 사용할 수 있어 문제 난이도가 낮아진 느낌. 만약 이런 조건이 없었다면 case_work가 좀 더 빡세졌을 것 같다. N이 100이기 때문에 시간복잡도가 상당히 널널하다. 현재 날짜에 스키를 탈 수 있다면 1일권, 3일권..

작년에는 사정 상 GoodBye, BOJ 2020! 을 참여하지 못했고, 나중에 연습삼아 풀어본 결과 1솔밖에 못하는 결과를 얻었다. 그래서 이번 GoodBye, BOJ 2021!에선 몇솔을 하든 상관없이, G3~2 까지의 문제들은 전부 해결해보는 것을 목표로 응시하였다. 프로징 전에 A~D 4솔, 프로징 후에 E를 시도했으나, 구현미스가 나서 5솔하지 못한 채 4솔로 마무리하였다. 결론적으론, 총 4솔로 마무리했다. 패널티가 좀 있기도 하고, E번을 해결하지 못했기 때문에 최종등수는 90등대이지 않을까 싶다. +) 22.01.01. 추가 확실히 E가 어려웠던 것 같다. 84등의 좋은 성적을 거두었다 ㅎㅎ 확실히 1년 전에 비해 많이 성장했음을 느끼는 계기가 된 대회였다 ㅎㅎ 간단하게 문제 별 느낀 점 ..