kth990303의 코딩 블로그

인터랙티브 문제는 어떻게 푸는걸까? 물론 백준 대부분에선 인터랙티브 문제를 어떻게 풀어야 하는지 하단에 힌트를 통해 친절하게 알려주는 편이긴 하다. 이번엔 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일 기준, 에디토리얼이 없다는 점은 아쉬웠다. 에디토리얼도 없으니 포스팅에 코드 및 풀이를 간..

대회 오픈컨 당일에 사정상 참여할 수 없어 뒤늦게 시간재고 풀어보는 시간을 가졌다. 오픈컨은 7시간동안 15문제였던 것으로 기억하는데, 7시간 내내 ps에 시간투자하긴 어려울 듯하여, 14~17시동안 Master 8문제를 해결해보는 시간을 가졌다. 진행 방식: 그룹 연습 / 티어: 성공한 문제에만 표시 / 알고리즘 분류: 보지 않음. / 그 전에 해결한 문제: 없음. 오픈컨 참가한 사람들에게는 solvedac 캐릭터가 판교역 옆에 서있는 배경을 주던데, 나는 오픈컨 참여는 하지 못했기 때문에 받지 못했다. 간단하게 후기를 작성해보겠다. 23738. A - Ресторан 대문자로 이루어진 문자열을 입력받으면 소문자로 바꿔주되, 특정 문자는 별도로 replace해주어야 하는 문제였다. 크게 어렵지 않은데,..

재밌는 문제가 뭐있을까 둘러보다가 발견한 문제. 마침 우리 학교에서 푼 사람이 아무도 없기도 해서 랭작용으로도 좋을 듯 해서 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/11877 11877번: 홍수 용량이 정확히 X인 히스토그램을 만들 수 없다면 첫째 줄에 -1을 출력해라. 그렇지 않다면 용량이 X가 되는 히스토그램의 열 h1, h2, …, hN를 출력해라. 그러한 방법이 여러 개가 있다면 아무 것이 www.acmicpc.net 문제 해석이 조금 껄끄러울 수 있는데, 쉽게 말해서 1~N까지의 높이로 이루어진 기둥들만으로 히스토그램을 만들되, 양옆 높이가 자신 높이보다 낮을 경우 물이 새므로 불가능하며, 맨 끝쪽에는 물이 없어야 한다는 소리다. 의식의 흐름 ..

본 대회에 직접 참여한 것이 아닌, 문제만 풀어본 것임을 미리 밝힙니다. 코포를 시작하게 된 이유? 최근 ICPC 2021 Seoul 문제들을 보면서 영어문제들을 빠르게 푸는 중요성을 느끼게 됐다. codeforce처럼 주어진 시간 내에 다양한 알고리즘을 요구하는 문제들을 빠르고 정확하게 해결하기 위해 시작하게 됐으며, 코포에 굉장히 자주 나오는 주제인 greedy, adhoc, constructive를 보는 눈이 ps 전반적으로 큰 도움이 될 것이라는 생각이 들어 codeforce에 많은 관심을 가지게 됐다. 군복무중이 아니라면 직접 라운드에 참여해 내 백준 아이디에 초록색, 민트색이라도 띄워보고 싶은데 아쉽다. 그래서 전역 전까지는 코드포스 문제에 익숙해지는 시간을 가져보려고 한다. 그리하여 시작한 ..

이번에도 UCPC 문제 포스팅이다. 트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17365 17365번: 별다줄 먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문 www.acmicpc.net 의식의 흐름 및 해설 예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다. 해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*..

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다. 기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 의식의 흐름 및 해설 먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다. 마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 ..

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다. (아래 포스팅 참고) https://kth990303.tistory.com/207 [Knapsack] 냅색은 웬만해선 바텀업으로 짜자 knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. kth990303.tistory.com 이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다. knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다. 이 ..

학교랭킹 랭작을 위해 풀은 문제인데, 꽤나 아이디어 면에서 얻어갈 게 많았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17038 17038번: The Great Revegetation (Silver) A lengthy drought has left Farmer John's $N$ pastures devoid of grass. However, with the rainy season arriving soon, the time has come to "revegetate". In Farmer John's shed, he has two buckets, each with a different type of grass seed. He wants to plant g www.acm..

재밌어보이는 그래프 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/2311 2311번: 왕복 여행 첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 www.acmicpc.net 의식의 흐름 및 해설 1->N->1로 돌아가는데, 이미 방문했던 길은 방문할 수 없다. 일단 가중치가 존재하기 때문에 dijkstra나 binary_search를 적절히 이용해볼까 생각이 들었다. 그러나, dijkstra로 1->N까지의 최소 시간은 구한다 치나, N->1로 다시 돌아갈 때, 중복방문을 허용하지 ..