kth990303의 코딩 블로그

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제. 문제는 아래와 같다. 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값을 어떻게 비교할지조..

스터디그룹에서 연습 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년 전에 비해 많이 성장했음을 느끼는 계기가 된 대회였다 ㅎㅎ 간단하게 문제 별 느낀 점 ..

인터랙티브 문제는 어떻게 푸는걸까? 물론 백준 대부분에선 인터랙티브 문제를 어떻게 풀어야 하는지 하단에 힌트를 통해 친절하게 알려주는 편이긴 하다. 이번엔 https://www.acmicpc.net/problem/18649 문제와 https://www.acmicpc.net/problem/23306 문제 풀이를 보면서 인터랙티브를 어떻게 푸는지 살펴보려 한다. 참고로 인터랙티브 태그에 '함수구현' 문제도 좀 있는 편인데, 이건 프로그래머스 스타일을 한번이라도 봤으면 쉽게 접근할 수 있고, 인터랙티브와 함수구현은 엄연히 다르다고 생각해 '함수구현'문제는 여기서 풀지 않을 것이다. 23306. binary는 호남선 https://www.acmicpc.net/problem/23306 23306번: binary는..

세종과학예술영재학교(세과영)에서 4시간 반동안 열리는 SASA 프로그래밍 오픈컨에 참여해보았다. 시간도 마침 괜찮았고, 오랜만에 대회 참여하면서 실력 점검 및 유지해보면 좋을 듯했기 때문이다. 그리고 2솔 이상하면 프로필 뱃지를 준다길래 참여해보았다 ㅎㅎ 대회 내에 풀 수 있는 문제들은 잘 푼 것 같다. 큰 실수로 인하여 풀 수 있는 문제를 놓치는 경우는 존재하지 않은 듯하고, C2번과 H번이 풀릴 듯 말 듯했다. (다행히 다음날에 업솔빙 성공) 문제들이 상당히 재밌었다. 오랜만에 대회를 참여해서 그런진 모르겠는데 정말 재밌게 푼 듯하다. 다만, B번 지문이 이해하기 꽤 어렵게 되어있었고, 2021년 12월 13일 기준, 에디토리얼이 없다는 점은 아쉬웠다. 에디토리얼도 없으니 포스팅에 코드 및 풀이를 간..