본문 바로가기
728x90

전체 글408

[python] 백준 14426 접두사 찾기 https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 문제 해결 하나씩 비교를 하면 시간복잡도가 매우 크다. 따라서 정렬을 한 후에 사전식 배열 비교를 한다. S에 포함되어있는 문자열과 검사해야하는 문자열을 비교해서 포함하면 정답+1과 다음 검사해야하는 문자열을 비교를 한다. 만약 포함여부에 해당하지 않고 S에 포함되어있는 문자열의 사전식 배열이 더 뒤이면 검사해야.. 2024. 3. 10.
[python] 백준 16724 피리 부는 사나이 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 해결 safe존을 어떻게 해야 최소로 만들 수 있는지 생각을 해봐야한다. 우선 순환하는 사이클이 있으면 하나를 무조건 만들어야한다는 생각을 가져야한다. 하지만 만약 다른 그룹으로 연결이 될 수 있는 경우도 있다. 예로들면 D L L R D Y U R U 다음과 같은 경우 사이클이 존재하면서 가장 왼쪽 아래있는 'U'는 사이클에 연결이 되므로 safe존은 하.. 2024. 3. 8.
[python] 백준 4386 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 전형적인 유니온 파인드 문제 단 리스트 안에 두 별자리 간의 거리를 오름차순으로 정렬하고 연결 되어있는지 아닌지 유니온 파인드를 통해 확인하고 해결한다. CODE import sys input = sys.stdin.readline import math def find(x): if x != parents[x]: return find(parents[x]) return parents[x] de.. 2024. 3. 7.
[python] 백준 16566 카드 게임 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해결 이진 분류로 bisect_right를 사용할 수 있는가의 문제 가장 최소의 값을 구할 때 만약 사용했다면 그 다음 수를 찾아야 하는데 여기서도 union-find를 사용하는가에 따라서 시간 단축이 될 수 있다. 만약 이전에 어떤 수를 사용했으면 그 수에 접근 했을 때 다음수로 넘어가도록 union-find를 설계할 수 있기 때문이다... 2024. 3. 5.
728x90