에라토스테네스의 체란 수학에서 소수를 찾는 방법입니다. 대량의 소수를 찾아야할 때 효과적이며, 소수를 직접 찾는 것이 아니라 일정 범위를 정해놓고 소수가 아닌 수를 지워나가는 것에 가깝습니다. 구현 순서 소수를 판별할 범위 만큼 배열을 할당 2부터 시작해서 범위 최대값의 제곱근까지 루프를 돌면서 소수일 때, 현재 수를 제외한 그 수의 배수에 해당하는 수를 지움(이미 지운 수는 건너뜀) 남아있는 수는 전부 소수 제곱근까지만 확인해도 되는 이유는? 소수를 판별할 범위가 2 ~ n 까지라고 하면, n의 약수는 \(n^{0.5}\)이하이므로 \(n^{0.5}\)까지만 탐색합니다. 결론적으로 제곱근 이상 수들은 이미 한번 지운 것들을 재방문 하는게 됩니다. 코드 n = 1000 is_prime = [True] *..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 이 문제는 bfs를 이용해서 풉니다. 입력받은 2차원 matrix와 matrix에서 G을 R로 바꾼 fixed_matrix 두 개의 배열을 사용합니다. 매개변수로 입력받은 matrix의 RGB 구역의 수를 구하는 count_RGB 함수를 선언하여 답을 구합니다. 코드 import sys from collections import deque def count_RGB(graph): ..

32 bit CPU와 64 bit CPU의 차이는 한번에 다룰 수 있는 데이터의 최대 크기입니다. 32 bit CPU에서 한번에 다룰 수 있는 데이터의 최대 크기가 32 bit이고, 64 bit CPU에서 한번에 다룰 수 있는 데이터의 최대 크기가 64 bit입니다. 그렇다면 32 bit CPU의 물리 메모리의 크기는 얼마일까요? bit는 데이터의 최소 단위입니다. 하나의 비트는 0이나 1의 값을 가질 수 있으며 각각은 참 혹은 거짓을 의미합니다. 32bit는 1bit가 32개 있는 것과 같고 1 bit당 경우의 수는 2이며 첫 비트는 부호를 나타내므로, 32bit로 표현할 수 있는 수의 범위는 \(-2^{31}\)부터 \(2^{31}\)까지 입니다. 즉, 32bit로 표현할 수 있는 수의 갯수는 \( ..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 입력받은 간선들을 딕셔너리 타입의 edges 변수에 저장합니다. 재귀함수를 이용해서 전위순회, 중위순회, 후위순회 함수를 선언합니다. 전위 순회일 때, current 노드 출력 -> left_child 노드를 매개변수로 전위 순회 -> right_child 노드를 매개변수로 전위 순회 중위 순회일 때, left_child 노드를 매개변수로 중위 순회 -> current 노드 출력 ..

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP를 이용합니다. 입력받은 카드팩들의 가격을 card_prices 리스트에 저장합니다. 예제 4번을 예로 들면, dp 테이블은 아래와 같습니다. idx 0 1 2 3 4 5 6 7 8 9 10 card_prices 0 5 10 11 12 13 30 35 40 45 47 dp 0 5 10 15 20 25 30 35 40 45 50 dp[4]는 카드 4장을 가질때의 가능한 최대 금액을 의미합니다..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 해시 테이블 자료구조를 사용합니다. 의상의 종류를 key로 의상의 이름을 입력받을 때마다 value(의상의 갯수)값을 1씩 더합니다. 의상의 종류별로 의상을 착용하지 않는 경우까지 더해서 (value + 1)를 모두 곱하고, 최종 결과에 아무것도 안 입은 경우(1)를 빼서 answer를 구합니다..