알고리즘/Python36

• 백준 알고리즘 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.

• 백준 알고리즘 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.

• 

  백준 알고리즘 2661번: 좋은 수열 (Python) 문제 정보 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 핵심 좋은 수열인지 검사할 때, 나는 처음에 예시로 나온 나쁜 수열의 모든 경우의 수를 계산하려고 코드를 짜고 있었다 하지만, 여기서 핵심은 수열을 만들어 나갈 때 나는 좋은 수열을 만들어 나가는 것이다 다시 말하면, 7이라는 N이 주어졌고 6개의 숫자로 이루어진 수열이 만들어졌으며 1개의 추가할 숫자가 남아있다고 한다면 내가 만들었던 길이 6을 가지는 수열은 이미 좋은 수열이기 때문에 그들 사이를 검사하려고 노력하지 않아도 된다는 것이다 예를 들어서 예제 입력처.. 알고리즘/Python 2023. 6. 26.