취업 준비 및 일상

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 '뭔 LCA여' 할 수 있겠지만, 질문 게시판의 글에서 알 수 있듯이 naive한 구현으로도 풀릴 수 있도록 설계한 문제입니다. M번의 쿼리마다 최소 공통 조상을 찾는데 순회해야하는 횟수는 최대 O(N)이므로, O(MN)으로 가능합니다. 다만 저는 각 정점 별 parent만 기록한 후, 처음 정점에서 위로 쭉 올라가면서 방문한 정점을 Set에 넣어주고, 두 번째 정점에서 올라가다 Set..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 나의 접근 방법 숫자도 작고, 케이스도 얼마 안 많을 거 같아서 경우 나눠주면 될 거라고 생각했습니다. 그런데 경우 나누는게 꽤 빡세더라고요. 못 하겠어서 알고리즘 분류를 보고 풀었습니다. 풀이 A, B, C A ret[2][0] = Math.min(a+b, A); ret[2][1] = Math.max(b-(A-a), 0); ret[2][2] = c; // B -> C ret[..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 나의 접근 방법 N = 10000, M = 100000이므로 O(N^2)보다 작은 시간복잡도를 갖는 풀이가 있을 거라 생각했습니다. 시작점을 기준으로 특정 점까지 가는 거리를 구하는 문제이기에, 다익스트라에서 로직을 살짝 바꿔주면 될 거라고 생각했습니다. 한 번 틀렸는데, min을 써야할 곳에 max를 쓰는 실수를 고치니 정답을 얻었습니다..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 나의 (실패한) 접근 방법 1. 플로이드는 O(N^3)이라 일단 제외했습니다. 다만, 풀고 다른 사람의 코드를 보니 플로이드도 아슬아슬하게 제한 시간 내에 도는 거 같습니다. 2. 이후 '음수 사이클이 존재하나 확인하면 된다'는 생각에(아이디어는 맞았죠.), 양수간선은 N번의 다익스트라, 음수 간선은 벨만 포드를 돌려 각자 따로 처리한 후 반복문으로 음수 사이클이 있나 확인해보려고 했..

https://www.chosun.com/national/national_general/2022/08/29/SDF3H4EQWZAHLPH2BLEZJPKTAE/ ‘필즈상’ 허준이 “취업·결혼 준비에만 정신 팔리지 말길” 필즈상 허준이 취업·결혼 준비에만 정신 팔리지 말길 서울대 학위수여식 축사...서로에게, 자신에게 친절하시길 www.chosun.com 글이 담백해서 올립니다.

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열에서 최솟값을 구하여 두 값의 최솟값이 정답이 되지 않나?' 라고 ..

예전에 만들었었는데, 많이들 봐주길 바라는 마음에 다시 한 번 글을 올립니다. 틈틈히 업데이트하고 있어요! 문제집 링크(Github) / 문제집 링크(백준) 문제 난이도별 정리 실버, 골드 하위 코테를 준비하는 입장이다보니 코테에 나올만한 유형 내에서 추천합니다 문제를 풀고 배울 점이 있었던 문제를 정리해두었습니다. 매일 랜덤하게 하나 잡고 풀어보면 좋지 않을까요? 골드 상위 다익스트라, 위상 정렬, MST 등의 (상대적으로) 어려운 알고리즘의 응용 문제 및 어려운 삼성 구현 문제들이 있습니다. 문제가 재미있고 개념에 insight를 제공하긴 합니다만. 사실 코테 대비로는 좀 오버킬이긴 합니다.

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가..

반효경 교수님의 강의 및 '운영체제와 정보기술의 원리'를 바탕으로 정리하였습니다.