kth990303의 코딩 블로그

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

solvedac 빼빼로 이벤트 중, 막대과자가 부족해서 골드 문제 아무거나 랜덤으로 뽑아서 풀게 된 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22863 22863번: 원상 복구 (large) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 의식의 흐름 및 해설 문제가 정말 permutation_cycle(순열사이클)처럼 생겼다. 근데 K가 최대 1e15니까 K번 순열 사이클을 돌리는 단순한 풀이는 안되겠다. 순열..

정말 기가막히도록 대단한 문제라 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 대충 생각나는 건 수학, 그래프 알고리즘이 생각나지 않는가? 좀 더 생각해보면 MST와 dfs로 연결지을 수 있다. 의식의 흐름 및 해설 이긴 사람은 천국으로 떠나고, 진 사람이 경기를 계속해서 이어갈 수 있는 특이한 룰이다. 즉, 사람 수가 N명일 때, 경기는 N-1번 진행된다. 시청률의 합이 최대가 되도록 해야 하며..

요즘 웹개발 공부를 하느라 백준을 많이 풀지 못해서 풀어본 문제. https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 생긴게 트리dp, DFS처럼 생겨서 해결해보려 한 문제이다. 의식의 흐름 및 해설 사실 맨 처음에 생각난 것은 '인접행렬과 그래프' 이다. 즉, 아래 문제가 먼저 떠오른 것이다. https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,0..

그래프 탐색 유형을 연습하기 위해 찾던 중 발견한 문제이다. KOI 2019 2차대회 초등부 3번 문제이다. 진짜 초등학생들 대단한 것 같다.. https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 처음에는 위상정렬 + 유니온파인드로 접근하다가, 연결된 컴포넌트들 중 X가 포함이 안된 컴포넌트쪽과 등수비교가 불가능함을 깨닫고 dfs로 바꿔 생각하여 해결한 문제이다. 시행착오 처음에는 위..

프로그래머스 월간 코드 챌린지 3번 문제를 풀지 못해 tree + dfs 연습을 좀 더 빡세게 해야겠다 싶어서 선정한 문제들 중 하나이다. 역시나...플레티넘 난이도 답게 굉장히 어려웠다. www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net KOI 2020 2차대회 초등부 3번, 중등부 2번 문제이기도 한데, 이거 보면서 진짜 요즘 초등학생, 중학생들은... 정말 대단하다는 생각도 들고, 똑똑한 친구들은 다르구나 생각이 많이 들었다. 개인적으로 친구들이나 ..