728x90 이분탐색17 [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] 백준 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. [python] 백준 1939 중량제한 문제 해결 처음에 BFS를 이용해서 문제를 풀려했지만 메모리 초과가 났다. 그러면 que안에 적게 넣어서 통과하는지를 확인해야한다. 방법이 잘 안떠올라서 다른 풀이를 참고했고 이분 탐색을 이용해서 통과할 수 있는 최댓값이 나올때까지 계속 돌려보는 방법이 있었다. 처음에 최솟값 1 최댓값 1000000000을 잡은 후 mid = (low+high)//2를 잡고 mid가 통과하면 low를 한칸 올려주고 통과하지 못하면 high를 한칸 내려주며 계속 시도하는 방식이다. 이를 low 2024. 1. 29. [python] 백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해결 (1,1)에서 (n,n)까지 가는데 거쳐간 수들 중 최솟값과 최댓값 차이를 구하는 문제 이동하면서 최솟값과 최댓값을 변경해가며 저장하고 갈 수도 있을 것 같은데 그러면 que안에 너무 많은 데이터가 저장이 되어 메모리 제한에 걸린다. 따라서 최솟값과 최댓값을 고정값으로 가져가며 그 안에 수들이 통과하여 이동할 수 있는지 확인해가는 식으로 bfs를 이용할 수 있다는.. 2023. 12. 4. 이전 1 2 3 4 5 다음 728x90
