백준71 백준 알고리즘 6588번: 골드바흐의 추측 문제 정보 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 핵심 에라토스테네스의 체 활용하여 소수 구하기 두 소수의 합으로 target number를 만들어내는 알고리즘 생각하기 풀이 from sys import stdin case = list(map(int, stdin.readlines()[:-1])) maxnum = max(case) # 에라토스테네스의 체 활용 소수 구하기 prime = [True for _ in range(maxnum + 1)] prime[0], prime[1] .. 알고리즘/Python 2023. 7. 2. 투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기 투 포인터 알고리즘이란? 주로 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법 이 알고리즘을 사용하면 선형 시간 복잡도 O(N)으로 동작하며, 정렬된 배열 또는 리스트에서 특정한 합이나 패턴을 찾는 문제에 효과적으로 사용된다 예시? 예시는 이전에 백준 알고리즘 1644번: 소수의 연속합 문제에 사용되었던 투 포인터 알고리즘을 사용한 풀이에서 예시를 들어 설명하도록 하겠다 문제에 대한 설명은 아래 참고 링크에 올라온 글을 참고하면 좋을 것 같다 이 문제의 경우, 소수들의 연속적인 합이 몇개가 있는지 출력하는 문제이다 target number가 41인 경우를 예를 들어 설명하자면, 먼저 에라토스테네스의 체 알고리즘을 사용하여 41까지의 소수를 primes 배열에 저장할 것이다 그 후 현재.. 알고리즘/개념 2023. 7. 2. 백준 알고리즘 1644번: 소수의 연속합 문제 정보 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 핵심 일반 풀이와 투 포인터를 활용한 풀이가 두가지가 있다 무조건 에라토스테네스의 체 알고리즘을 활용하여 문제를 풀이하여야 하며 해당 개념은 이전에 올렸던 글에서 참고할 수 있다 (아래 참고 링크 확인) 위 두가지 풀이 모두 파이썬 기준 백준 제출시 통과되지만, 효율성은 투 포인터가 훨씬 좋다 풀이 일반 풀이 import sys N = int(sys.stdin.readline()) prime = [True for _ in range(N+1)] prime[0], prime[1] = False, False for i in range(2, int(N**0.5) + 1): if.. 알고리즘/Python 2023. 7. 2. 백준 알고리즘 2485번: 가로수 (Python) 문제 정보 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 핵심 최대공약수 문제다! 라는 것을 빠르게 캐치하여야 함 일일히 최대공약수를 구하는것은 정말 비효율적이니, 유클리드 호제법을 통해서 구하는 것이 올바른 풀이이다 각 가로수의 간격들의 전체 최대공약수를 구하고 이 간격에서 비어있는 가로수의 개수를 찾아서 출력해주면 된다 풀이 from sys import stdin N = int(stdin.readline()) tree = list(map(int, stdin.readlines())) def GCD(.. 알고리즘/Python 2023. 6. 29. 백준 알고리즘 2580번: 스도쿠 (Python) 문제 정보 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 핵심 경우의 수가 엄청나게 많기 때문에, 파이썬의 경우 특히 시간초과에 대한 고민을 하면서 푸는것이 좋음 또한, 어떤식으로 풀어갈지 잡고 가는것이 가장 중요한 것 같다 풀이 문자열을 입력받아 2차원 정수형 배열을 만든다. 배열의 이름은 Pane 이를 뒤집은 배열(행-열) rPane을 만들어 준다 (열에 같은 수가 존재하는지 확인) 배열의 원소 중 0을 가진 좌표(빈 공간)을 blank 배열에 좌표 형태로 저장한다 해당 좌표에 올 수 있는 수를 계산하.. 알고리즘/Python 2023. 6. 27. 이전 1 ··· 6 7 8 9 10 11 12 ··· 15 다음
