본문 바로가기

분류 전체보기548

백준 7570 c++ "줄 세우기" -PlusUltraCode- https://www.acmicpc.net/problem/7570[필자 사고]재미난 문제다. 처음에 LIS로 접근해서 N-size형태로 문제를 해결하려 했지만 놓친 부분이 있다.원하는 위치에 넣는게 아닌 앞 혹은 뒤로만 넣을 수 있다는 조건이다.이 조건으로 인해 LIS는 불가능하다. 우리가 찾아야 할 것은 연속된 가장 킨 숫자들의 갯수다. 해당 갯수를 찾은 뒤 N-size형태로 하면 답을 구할 수 있다.처음 best 값을 1로 초기화 해야한다. 실수하지 말자. 아래는 자세한 코드 해설이다.[코드 해설]줄 세우기 실패 (백준 2631) 풀이 및 코드 해설이 문제는 **“제일 앞이나 제일 뒤로만 이동시켜 번호 순서대로 정렬하는 최소 횟수”**를 구하는 문제입니다.입력은 1부터 N까지의 번호가 섞여 있으며, .. 2025. 10. 31.
백준 2211 c++ "네트워크 복구" -PlusUltraCode- https://www.acmicpc.net/problem/2211[필자 사고]최단거리 루트.. 뭐다?? 다익스트라 알고리즘이다. 다만 이 문제에서 요구하는 거는 역추적즉 해당 회선 경로까지 추출해야 된다는 점이다.그래서 필자는 parent를 이용하여 부모노드 까지 기록을 해주었다. 아래는 자세한 코드 해설이다.[코드 해설]문제 핵심 요약1번 컴퓨터가 슈퍼컴퓨터.네트워크를 “최소 개수의 회선”으로 복구하되, 1번에서 각 컴퓨터까지의 최단 통신 시간은 기존과 동일해야 함.즉, 1번을 루트로 하는 최단경로 트리(Shortest Path Tree, SPT) 를 복구하면 두 조건을 동시에 만족:트리는 간선 수가 정확히 N-1 → “최소 회선”다익스트라로 얻은 최단거리 기반 트리 → “최단 시간 유지”아이디어 한 .. 2025. 10. 30.
백준 13334 c++ "철로" -PlusUltraCode- https://www.acmicpc.net/problem/13334[필자 사고]WellKnown 문제라고 할까? 대표적으로 시작점 혹은 끝점을 정렬한뒤 큐에 넣고 큐의 size를 이용하여 갯수를 갱신하는 문제다.조심해야 될 부분은 queue의 값을 빼는 타이밍이다. 이번 문제는 end값을 기준으로 정렬한 뒤 start를 pq에 넣어논다. pq의 정렬 기준은 오름차순이다.만약 end-D 가 pq.top()보다 크다면 갱신해야 될 타이밍이다.pq.top()를 빼주는 형태로 아래는 자세한 코드 해설이다.[코드 해설]문제 요약집과 사무실이 각각 수평선상의 한 점으로 주어진다.각 사람은 [집, 사무실]이라는 구간을 가진다고 볼 수 있다.이제 길이 D의 철로를 선분 형태로 설치했을 때,집과 사무실이 모두 철로 안에.. 2025. 10. 29.
백준 1103 c++ "게임" -PlusUltraCode- https://www.acmicpc.net/problem/1103[필자 사고]재미난 문제다. 처음에는 BFS를 이용하여 문제를 해결하려 했찌만 순환을 어떻게 판별해야 될지 문제가 생겼다.순환.. 보통 DFS에서 dp로 해결하지 않았는가.. ?? 먼저 한경로로 탐색을 한뒤 visited를 true -> false로 바꾸는 전략좋다 메모이제이션을 이용하자. 끝가지 가서 탐색이 불가능한 지점을 만나면 dp[][] 값은 0이된다. 이렇게 하나하나 쌓아 가는 방식으로 문제를 해결했다.[코드 해설]문제 요약형택이는 숫자(1~9)와 구멍(H)이 있는 보드 위에서 동전을 움직이는 게임을 한다.처음에는 항상 (0, 0)에서 시작하며, 다음 규칙에 따라 이동한다.현재 칸의 숫자 X를 확인한다.위, 아래, 왼쪽, 오른쪽 중.. 2025. 10. 29.

티스토리툴바