![]()
문제 (링크) https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 나의 풀이 첫 번째 풀이 import sys import math data = [] while True: n = int(sys.stdin.readline()) # 입력값이 0이 아닐때까지 입력값을 data배열에 저장 if n == 0: break else: data.append(n) def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리..
문제 (링크) https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 나의 풀이 import math m, n = map(int, input().split()) arr = [True for _ in range(n+1)] for i in range(2, int(math.sqrt(n)) + 1): if arr[i] == True: j = 2 while i * j 1: if arr[i] == True: print(i) 접근 방법 및 코드 설명 낮에 공부했었던 에라토스테네스의 체를 사용하는..
알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다. 아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다. 소수는 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 특정 수 N이 소수인지 아닌지 구하는 법은 바로 이 특징을 활용하여 2부터 N-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다. 나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다. 이를 코드로 표현하면 다음과 같다. def is_prime_num(n): for i in range(2, n): if n % i ..
![]()
힙이란? 힙은 트리 형태로 만들어진 자료구조 중 하나이다. 힙은 트리 중에서도 두 가지 조건을 만족해야 하는데, 첫 번째는 완전이진트리여야 한다는 것 두 번째는 부모 노드의 값이 항상 자신의 자식노드들보다 커야한다는 것이다. (힙의 예시) 위 트리는 트리의 높이 - 1 까지 모두 빈 노드 없이 차 있으며 마지막 높이의 데이터들 역시 왼쪽부터 오른쪽으로 차례대로 채워져있으므로 완전이진트리의 속성을 만족시킨다고 할 수 있다. 또한, 모든 노드들이 자신의 자식노드들보다 큰 값을 가지기 때문에 힙의 성질 역시 만족시킨다고 할 수 있겠다. 힙 자료구조의 구현 힙 자료구조는 기본적으로 완전이진트리이기 때문에, 특정 노드의 위치를 알면 그 노드의 부모 노드의 위치와 두 자식 노드의 위치를 알 수 있다. 이를 활용하면..
![]()
1) 이진트리 이진트리는 부모 하나 당 최대 2개까지의 자식노드를 가질 수 있는 트리를 말한다. 따라서 이진트리의 각 노드 인스턴스는 자신의 부모 노드에 대한 레퍼런스와 두 자식노드에 대한 레퍼런스를 가지게 된다. 이진트리의 노드 클래스를 구현하면 다음과 같다. # 이진트리의 노드 class Node: def __init__(self, data): # 파라미터로 받은 데이터를 삽입 self.data = data # None으로 초기값을 지정 후, 노드 생성 후에 지정 self.left_child = None self.right_child = None 이후, 각 데이터를 담은 노드 클래스를 만들어주고 자식 관계를 설정해주고 나면 노드를 통해 그 노드의 부모노드와 자식노드를 모두 호출할 수 있게 된다. 2)..
문제 (링크) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 n = int(input()) d = [0] * 1000001 for i in range(2, n+1): d[i] = d[i-1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) print(d[n]) 나동빈님의 유튜브 이.코.테 다이나믹 프로그래밍 강의를 들은 후 연습 문제로 풀어보았다. 사실 유튜브에서 제공한 연습문제랑 연산 조건만 다를 뿐 아예 같은 문제라고 봐도 ..
문제 (링크) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) count = 0 for x in data: for i in range(2, x+1): if x % i == 0: if x == i: count += 1 break print(count) 백준에서 틀린 문제를 살펴보다가 발견한 문제다. 왜 그랬는지는 모르겠는데 꽤 많이 틀려놨었고, 발견하자마자 풀어봤는데 바로 풀렸다. 알고리즘 문제 중 소수와..
문제 (링크) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 나의 풀이 from sys import stdin n = stdin.readline() # 이진탐색을 진행해야하므로 탐색을 할 리스트를 sorted 처리 해준다 group_n = sorted(list(map(int, stdin.readline().split()))) m = stdin.readline() group_m = list(map..
