분류 전체보기105 15681_트리와 쿼리 ▶ 골드5 (DFS)문제간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 입력트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)입력으로 주어지는 트리는 항상 올바른 트리임이 .. 2025. 3. 12. 20922_겹치는 건 싫어 ▶ 실버 1 (투포인터)풀이N은 200,000 이하이기 때문에 시간 복잡도가 O(N^2)이 넘어가면 시간 초과가 발생합니다.따라서 투포인터를 활용하여 O(N)의 시간 복잡도가 될 수 있도록 하였습니다. 투포인터 활용해서 start, end로 인덱스를 구간 관리하였습니다.또한, 숫자 별 카운트는 Counter 라이브러리를 사용하였습니다. 구간 내에 k 초과한 개수를 가진 값이 있으면 안되기 때문에,현재 값(end 인덱스의 값)의 개수과 k 값을 비교하여 두 가지 경우에 대한 처리를 합니다. 1) k보다 작다면, 해당 값을 구간에 추가해도 된다는 의미이기에counter 값을 증가시키고구간의 개수와 최댓값을 비교하여 ans을 갱신하고end 인덱스를 증가시킵니다.2) k보다 크거나 같으면, 해당 값을 구간에 추.. 2025. 3. 9. 14502_연구소 ▶ 골드4 (BFS + 브루트포스)풀이n, m의 크기가 10 이하고 벽의 개수가 무조건 3개이기 때문에 브루트포스임을 알게 되었습니다. 처음에는 백트래킹을 이용해서 벽 3개를 세우고, BFS를 이용해서 바리어스 확산 칸의 개수를 세서 최댓값을 구하는 방법으로 구현했는데, 시간 초과가 발생하였습니다. 그래서 백트래킹 대신 파이썬의 combinations를 이용해서 완탐으로 벽 3개의 조합을 구하는 방식으로 수정하였습니다.코드# 14502_연구소from collections import dequefrom itertools import combinationsfrom copy import deepcopyimport sysinput = sys.stdin.readlinen, m = map(int, input().s.. 2025. 3. 7. 11123_양 한마리... 양 두마리... ▶ 실버 2 (DFS)풀이DFS나 BFS를 이용하여 덩어리 개수를 세면 되는 간단한 문제입니다. 2차원 DFS를 구현하고, 2중 for 문을 이용하여 방문하지 않았고, #이라면 DFS를 실행하여 visited 배열을 갱신해줍니다. 이런 방식으로 덩어리 개수를 세면 됩니다. 그리고 python에서 DFS를 구현할 때는 sys.setrecursionlimit(10**6) 코드를 추가해야한다.코드# 11123_양 한마리... 양 두마리...import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinet = int(input())for _ in range(t): h, w = map(int, input().split()) garden = [input.. 2025. 3. 7. 15558_점프 게임 ▶ 골드 5 (BFS)풀이길을 이동하는 방법은 1) 뒤로 가기 2) 앞으로 가기 3) 옆으로 가기BFS를 통해서 갈 수 있는 모든 경로를 방문한 후, N칸이 넘어가면 성공으로 간주하고 1을 출력한 뒤 종료합니다.갈 수 있는 경로의 조건은현재 시간 번째 칸 이상이고 (뒤로가는 경우만 해당)방문하지 않았고이동할 수 있는 칸인 경우현재 칸이 N번 째 이상인 경우 종료.고민한 점 현재 칸에서 이동할 수 있는 3가지 칸에서는 동일한 시간을 가져야하는데,처음에 visited를 숫자로 저장하여 time을 관리하려고 하니 칸을 이동할 때마다 시간이 증가했습니다.그래서 queue에 [줄, 인덱스, 방문 시간] 형태로 방문 시간을 추가했습니다.코드# 15558 점프 게임from collections import deque.. 2025. 2. 26. 16719_ZOAC ▶ 골드 5 (재귀)풀이처음에는 사전 순 알파벳을 순차적으로 출력하면 되는 문제인 줄 알았습니다. 하지만 무작정 순서대로 출력하는 것이 아니라, 사전 순에서 가장 빠른 알파벳을 찾고 출력한 후, 해당 인덱스 뒤의 범위의 문자열이 모두 출력될 때까지 동일한 과정을 진행합니다.뒤 알파벳을 모두 출력하고 나면, 앞 범위의 문자열에 동일한 과정을 진행합니다. 이렇게 범위를 좁혀가면서 동일한 과정을 수행하는 것이기 때문에, 선택한 알파벳에 대해 뒷 범위, 앞 범위를 재귀로 진행합니다. 중요한 점은, 가장 빠른 알파벳을 찾을 때, 동일한 알파벳이 여러 개 있을 수 있기 때문에현재 범위 내에서 for문을 통해 인덱스를 찾아줍니다.또한, 뽑힌 알파벳의 인덱스는 따로 보관하여 출력할 때 써줍니다.코드# 16719 ZOA.. 2025. 2. 25. 이전 1 2 3 4 ··· 18 다음
