O'bin and the Chocolate Factory

~ 목차 ~ 정렬 알고리즘 버블 정렬 버블 정렬 버블 정렬 개선 1 - 교환 발생하지 않는 경우 정렬 중단 버블 정렬 개선 2 - 이미 정렬된 원소는 비교/교환 범위에서 제외 버블 정렬 개선 3 - shaker sort 단순 선택 정렬 단순 삽입 정렬 정렬 알고리즘 - 안정적인 정렬 알고리즘 vs 안정적이지 않은 정렬 알고리즘 값이 같은 원소의 순서가 정렬 후에도 유지되는지 여부에 따라 결정 -> 유지 : 안정적 -> 유지 보장 x : 안정적 x - 내부 정렬 vs 외부 정렬 정렬할 데이터를 하나의 배열에 저장할 수 있는지 여부에 따라 결정 -> 가능 : 내부 정렬 -> 불가능 : 외부 정렬 - 버블, 단순 선택, 단순 삽입 정렬 시간복잡도 모두 O(n^2)로 프로그램 효율 좋지 X 버블 정렬(bubbl..

~ 목차 ~ 해시법 해시 충돌 체인법 오픈 주소법 정렬된 배열에서 원소 추가/삭제 시, 추가/삭제 위치 뒤/앞의 원소들 한칸씩 뒤/앞으로 밀어야 한다 = 복잡도 O(n) 해시법 검색과 데이터 추가/삭제도 효율적으로 수행할 수 있는 방법 해시 값(hash value) : 배열의 키(= 원소의 값) %원소의 개수 해시 함수(hash function) : 키->해시값 과정 해시 테이블(hash table) : 해시값을 인덱스로 하여 원소를 새로 저장한 배열 버킷(bucket) : 해시 테이블에서 만들어진 원소 해시 충돌 키와 해시값은 일반적으로 n:1 관계 해시 충돌 : 저장할 버킷이 중복되는 현상 해시 충돌 대처법 체인법 : 해시값이 같은 원소 연결리스트로 관리 오픈 주소법 : 빈 버킷을 찾을때까지 해시 반..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sys from collections import Counter # input()으로 입력 받으면 시간초과 발생 input = sys.stdin.readline n = int(input()) nums = [int(input()) for _ in range(n)]..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net sol1) m부터 n 사이의 숫자들이 약수인지 여부를 특정 숫자의 제곱근까지만 확인하여 판별 1 2 3 4 5 6 7 8 9 10 11 m, n = map(int, input().split()) for i in range(m, n+1): if i == 1: continue # i의 제곱근까지만 검사 for j in range(2, int(i ** 0.5) + 1): if i % j == 0: break else: print(i)..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net sol1) stack 배열에 열린 괄호는 추가, 닫힌 괄호는 열린 괄호 있으면 pop으로 제거 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 while True: stack = [] line = input() if line == '.': # 종료조건 break for i in line: i..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 n = int(input()) # 5kg 봉지 최대 가능 수 부터 시작 for i in range(n//5, -1, -1): # 만약 5kg 봉지 최대 가능 수의 나머지가 3으로 나누어떨어지면 if (n - (i * 5)) % 3 == 0: # 5kg 봉지 수 + 3kg 봉지 수의 합 출력 print(i + (n - (i * 5)) // 3) break # 루..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1234567891011121314import sys n = int(sys.stdin.readline()) # input()으로 입력 시 시간초과 nums = [0] * 10001 for _ in range(n): nums[int(sys.stdin.readline())] += 1 # 입력 값을 인덱스로 하는 위치에 1 더하기 for i in range(10001): if nums[i] != 0: # 입력 값이 있으면..

이진 검색 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘, 선형 검색보다 빠름 배열의 중앙을 기준으로 검색값과 비교해서 대소에 따라 검색 범위를 절반씩 줄이는 알고리즘 시간복잡도 O(log n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 # 이진 검색 알고리즘 from typing import Any, Sequence """시퀀스 a에서 key와 일치하는 원소 이진 검색""" def bin_search(a: Sequence, key: Any) -> int: high = 0 # 검색 범위 맨 앞 원소 index lo..

- 배열 검색방법 중 가장 기본 - 직선 배열에서 검색하는 경우에 원하는 데이터를 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘 목차 선형 검색의 종료 조건 보초법 1. 선형 검색의 종료 조건 2. 보초법(sentinel method) 선형검색의 종료 조건 검사 비용 감소 방법 원본 데이터 맨 끝에 검색할 값(보초)를 추가 종료 조건 1번이 필요 없으므로 판단 횟수 반으로 감소 스캔 종료 시 찾은 데이터가 원본 데이터인지 보초인지 구별 필요 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 from typing import Any, Sequence import copy """ 시퀀스 seq에서 key와 ..

탐욕법(Greedy Algorithm) 매 순간 최선의 경우만 선택 -> 모든 경우 확인하지 않아 완전탐색보다 빠름 다른 경우는 고려하지 않음 -> 그리디로 풀면 반드시 틀리는 문제 존재 반례가 없는지 신중히 고민해야함 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 ..