분류 전체보기16 [파이썬, 자바] 백준 - 1300 (이분 탐색) https://www.acmicpc.net/problem/1300 두 번째 푸는 문제지만, 오랜만에 봐서 풀이법을 생각하지 못 했다. 이 분의 글을 보고 다시 떠올릴 수 있었다.https://kbw1101.tistory.com/29 [백준/1300] K번째 수 (이분 탐색)1. 문제 2. 접근 방법 이분 탐색으로 해결할 수 있는 적당한 난이도의 문제... 라고는 하나 접근 방법이 잘 떠오르지 않아 애를 먹었던 문제이다. 이 문제는 브루트 포스적인 방법으로 접근하면, O(kbw1101.tistory.com 사고의 전환이 필요한 문제이다. k 번째 수가 무엇인지 물어봤으니, 자연스레 k 번째 자리에 무슨 수가 있는지 탐색하려고 했다.그러나 이렇게 생각을 하면 풀 수 없다. 생각을 바꿔 임의의 수(T)가 있을.. 2024. 11. 30. [파이썬, 자바] 백준 - 2343 (이분 탐색) https://www.acmicpc.net/problem/2343 해당 문제는 이진 탐색을 활용하는 문제다. 먼저 이진 탐색이 무엇인지 부터 알아보자. 이분 탐색- 정렬된 데이터에서 원하는 값을 탐색할 때 사용하는 알고리즘- 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이변서 대상을 찾는다.- 한 번의 연산에 탐색할 데이터의 크기가 절반씩 줄기 때문에 O(logN)의 시간복잡도를 가진다.ex) 데이터의 수가 16개라면, 4(log16)번의 연산으로 원하는 값을 찾을 수 있다. 1. 현재 데이터 셋의 중앙값을 선택한다.2. 중앙값 > 타깃값 : 중앙값 기준으로 오른쪽 데이터셋은 버린다. (중앙값 기준 오른쪽에는 타깃값이 존재하지 않기 때문)3. 중앙값 4. 과정 1~3을 반복하.. 2024. 11. 28. [파이썬, 자바] 백준 - 1167 (BFS) https://www.acmicpc.net/problem/1167 처음 이 문제를 풀 때는 트리의 지름을 구하는 원리를 몰라서 모든 정점에서 탐색을 하여 가장 길이가 긴 것을 찾도록 하였으나 당연히 시간 초과.. 트리의 지름을 구하는 원리는 이 분의 글을 보고 이해했다.https://blogshine.tistory.com/111 HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함" data-og-host="blogshine.tistory.com" data-og-source-url="https://blogshine.tistory.com/111" data-og-url="https://blog.. 2024. 11. 27. [파이썬, 자바] 백준 - 13023 (DFS, 백트래킹) https://www.acmicpc.net/problem/13023 처음에는 그냥 0번부터 탐색을 시작해서 5명이 채워지면 1을 출력하면 된다고 생각했다. 그러나 2번 예제를 보면,5 5 # N, M0 11 22 33 01 40부터 탐색을 시작하면, 0 -> 1 -> 2 -> 3으로 최대 4명밖에 탐색할 수 없다. 그러나 2부터 탐색을 시작한다면, 2 -> 3 -> 0 -> 1 -> 4로 5명을 탐색할 수 있다. 때문에 메인 함수에서 탐색을 할 때, 0번만 탐색하고 끝날 것이 아니라 0번부터 N - 1번까지 모두 탐색을 해줘야 한다. (물론 위의 예제의 경우, 양방향 그래프로 값들을 저장한다면 0만 탐색해도 5명을 탐색할 수 있다. 하지만 그렇지 않은 경우도 있다는 거..) 라고 생각을 했는데.. 문제에.. 2024. 11. 25. [Alogorithm - Python, Java] 백준 2023 - 신기한 소수 (DFS, 백트래킹, 에라토스테네스의 체) https://www.acmicpc.net/problem/2023 이전에 틀렸던 문제를 다시 한 번 풀어봤다. 두 번째라 그런지 풀이법은 금방 생각났다. 1. 첫 번째 자릿수부터 시작해서 다음 자릿수가 추가될 때마다 소수 판별을 한다. -> DFS 사용2. 소수 판별이 끝난 숫자의 자릿수가 N이 되면, 문제 조건을 만족했기 때문에 더 이상 탐색을 진행할 필요가 없으므로 return -> 백트래킹 사용 Code(Python)import sysinput = sys.stdin.readlinedef erato(n): # 소수 판별 함수(소수이면 True, 아니면 False) for i in range(2, int(n**0.5) + 1): # 에라토스테네스의 체를 사용하여 소수 판별 if n %.. 2024. 11. 21. [Alogorithm - Python(파이썬)] 백준 1644 - 소수의 연속합 (투 포인터, 구간 합, 에라토스테네스의 체) https://www.acmicpc.net/problem/1644 이 문제는 다른 구간 합 문제와 동일하지만, 연속된 수가 아닌 연속된 소수의 구간 합을 구하는 문제이다. 때문에 연속된 소수를 구해야 했고, 이전에 풀었던 에라토스테네스의 체 개념을 적용해서 통과할 수 있었다. 에라토스테네스의 체란 무엇인가? 개념부터 잡고 가자. - 에라토스테네스가 만든 소수를 찾는 방법- 마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다. ex) 100 이하의 자연수 중에서 소수를 찾아라. 1. 1부터 100까지 숫자를 쓴다. 2. 소수도 합성수도 아닌 1을 제거한다. 3. 2를 제외한 2의 배수를 제거한다. 4. 3을 제외한 3의 배수를 제거한다. * 4는 제거할 필요 없다. (2의 배수에서 이미 .. 2024. 8. 19. 이전 1 2 3 다음
