취업 준비 및 일상

https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 풀이 dp[i][j][k][n]을 '처음 주사위를 3번 던져 나온 눈이 i, j, k이고, 던질 수 있는 기회가 n번 남았을 때의 기댓값'이라고 정의합니다. 그러면 dp[i][j][k][n] = max((주사위를 한 번 더 던지고, 기회가 n-1번 남았을 때의 기댓값), (i, j, k일 때의 점수))가 됩니다. 자세한 풀이는 에디토리얼를 참고하세요 코드 1 2 3 4 5 6 7 8 9 10 11 1..

https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 그 유명한 '습격자 초라기' 문제입니다. DP 문제라는건 예전에 들어서 알았는데도 풀이 접근조차 못하겠더라고요. 그래서 casterian님의 풀이를 봤습니다. 이 분 글 퀄리티가 좋습니다. cf) 안 되는 풀이 처음에 풀이 아이디어를 대충 본 후, '1~N열에서 최솟값, 2~N열 + 1열에서 최솟값을 구하여 두 값의 최솟값이 정답이 되지 않나?' 라고 ..

https://www.acmicpc.net/contest/view/843 2022 ICPC Sinchon Summer Algorithm Camp Contest Open www.acmicpc.net 해설 총 6문제 (A~E, H)를 풀었습니다. A 머리 좀 굴려보면 'a, b, c중 최솟값'이 정답이 됨을 알 수 있습니다. H 테스트케이스 T에 대해 O(T) 알고리즘이라 A랑 똑같이 풀었습니다. 다만, T 해설 보니 BFS 요구한 게 맞더라고요. 못 푼 문제 복기 F 한 쪽 구석으로 몰아제껴도 영향 없는건 제껴놓고 / 나머지는 비교하기 이런 식인거 같은데, 구현이 좀 어려워보입니다. -> 그리디 느낌으로 정리하면 될 거 같았는데, case-work 빡센 DP 문제였네요. G 다익스트라같긴 한데, edge가..

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그렇게 어려운 문제는 아닌데, 독해력 문제로 많이 헤맸습니다. 헤맨 부분 '입출력 예 #2'에서 왜 "AB"는 정답이 아닐까? -> 길이가 같은 course에 대해서는 등장횟수가 가장 많은 메뉴만 코스메뉴 요리 후보군에 넣기 때문입니다. 아마 "... 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다."가 저 logic이지 않나 싶은데, 알고 읽..

링크: 설명 / 문제집 처음 KMP 알고리즘을 접했을 땐, 이해하는데 1시간 반이 걸렸습니다. 그래도 한번 공부해서 그런지, 오랜만에 봐도 이해하는데 30분밖에(?) 걸리지 않았네요. 되돌아서면 헷갈리는 알고리즘입니다. 문제 풀이 백준 16916번 부분 문자열, 백준 16172번 나는 친구가 적다 (Large) - 기본적인 KMP 활용 문제입니다. Python에서 in 연산이 O(N)이라, 코테에서 이런 유형의 문제가 나오면 python 및 C++의 library를 활용하는 것이 낫습니다. 백준 1786번 찾기 - 기본 KMP 문제인데, 위 두 문제와 다르게 '부분 문자열이 몇 번 나왔으며, 시작 위치가 어디인지'를 구해야 합니다. KMP 알고리즘을 활용해서 풀었다면 위 문제에서 '부분 문자열을 찾은 순..

https://www.acmicpc.net/problem/16455 16455번: K번째 수 찾는 함수 C++17, Java 8, C11, PyPy3, C99, C++98, C++11, C++14, Java 8 (OpenJDK), Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 풀이 N = pivot} 으로 나누어, |L| + |C| K이면 L에서 새로운 pivot을 찾고, |L| = K이면 적당히 L or C에서 K번째 원소를 찾는 방법입니다. quicksort랑 다르게 amortized O(N) 시간복잡도를 가지지만, worst case..

https://www.acmicpc.net/problem/24025 24025번: 돌의 정령 줄세우기 $4$, $1$, $5$, $2$, $3$으로 배치한다면 돌의 정령 무리들의 시야점수는 각각 $2$, $1$, $10^9$, $1$, $10^9$로 조건을 만족한다. www.acmicpc.net 풀이 전형적인 코드포스 스타일의 구성적/그리디 문제입니다. 쌩 브루트포스는 O(N!)일테니 절대 안되며, 적당히 가지치기한다고 해도 O(N^2) 이하로 줄이기가 쉽지 않아보입니다. 그러다 보면, '최적의 배치가 존재하지 않을까?'와 같은 생각에 도달하게 됩니다(그리디 말고는 생각나는게 없으니...). 그리디하게 찾아보도록 합니다. 1-based를 기준으로, 1 = 1이므로, 언제나 조건을 만족합니다. 그리고, N..

현대모비스 알고리즘 경진대회를 본 이후, 1) CP에 관심이 생겨서 2) 언젠가 한 번은 해보고 싶어서 3) 백준 아이디를 파랗게 칠하고 싶어서 코드포스를 좀 했습니다. 총 6번의 round를 치루면 소위 '배치고사'가 완료되어 본인의 rating이 결정됩니다. 배치고사 이내 블루를 찍어서 다행입니다. 코드포스 문제 스타일 (DIv.2 기준) A~D 공통 구현이 그렇게 중요하진 않습니다. 삼성 SW 테스트는 툭하면 한 문제당 코드 100줄이 넘어가는데, 그런 문제는 별로 없어요. 디버깅도 그렇게 중요하진 않습니다. 어차피 채점(실시간으로 작은 샘플인 pretest로 채점을 해 주는데, pretest 통과하면 왠만하면 system testing도 통과합니다.)도 해주고, A, B는 많이 틀릴 일이 없고, ..

백준 13459번: 구슬 탈출 백준 13460번: 구슬 탈출 2 백준 15644번: 구슬 탈출 3 백준 15653번: 구슬 탈출 4 3달 전 즈음에 구슬 탈출 2를 풀었습니다. 당시 구현에 급급하여 간신히 풀었고, 풀고 나서 '어휴 이런 문제는 꼴도 보기 싫다~' 하고 눈 앞에서 치워버린 기억이 납니다. 다시 풀어보니, 구현이 적당히 많고 까다로우며, 시간 커팅할 부분이 많은 흥미로운 문제라 느껴집니다. 풀이 '백준 13459번: 구슬 탈출'을 기준으로 설명합니다. 기본 구현 0) 기울일 때마다 움직이는 건 구슬 2개뿐이므로, 각 구슬의 좌표를 따로 저장하여 관리합시다. 그리고 구멍 좌표도 따로 저장해둡니다. 1) 방향과 빨간 구슬, 파란 구슬 위치에 따라 어느 구슬을 먼저 움직일 지 결정합니다. 2) ..

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 한 번에 시행동안 1) 가장 적은 물고기를 가지고 있는 어항에 물고기 넣어주기 - putFish() 2) 첫 번째 마법 - magic1() 3) 물고기 수 조절 - spread() 4) 다시 일자로 펴주기 - badak() 5) 두 번째 마법 - magic2() 6) 물고기 수 조절 - spread() 7) 다시 일자로 펴주기 - badak() 8) 최대 물고기 수 어항 - 최소 물고기 수 어항