연결 리스트란? 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 이곳저곳에 흩어져 있다. 파이썬에서는 배열과 연결 리스트의 장점을 합친 리스트를 사용한다. 연결 리스트의 성질 k 번째 원소를 확인/변경하기 위해 O(k)가 필요함 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 배열과 다르게 리스트에는 몇 개의 종류가 있다. 단일 연결 리스트(Singly Linked list) 각 원소가 자신의 다음 원소의 주소를 들고 있는 연결 리스트 [데이터1] -> [데이터2] -> [데이터3] -> None 이중 연결 리스트(Doubly Lin..
배열이란? 메모리 상에 원소를 연속하게 배치한 자료구조 배열에 저장되는 요소들은 모두 동일한 자료형을 가져야 한다. 배열은 생성될 때 크기가 정해진다. 파이썬에서는 리스트 타입이 배열의 기능을 한다. 배열의 성질 O(1)에서 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리 양(=overhead)가 거의 없음 Cache hut rate가 높음 배열의 인접한 요소들은 함께 캐시에 로드되어 캐시 라인 활용을 최대화하며, 이로 인해 데이터 접근 시간을 줄여 더 빠른 연산을 가능케 하는 것 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 기능과 구현 # 1차원 배열 = 리스트 arr = [1, 2, 3, 4] print(arr[3]) # 4 출력 # 2차원 배열 arr2 = [[1, 2, 3]..
문제 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 코드 import sys input = sys.stdin.readline n = int(input()) num = sorted(list(map(int, input().split()))) print(num[0]*num[-1]) 나의 생각 어떤 수의 약수는 대칭적인 특징을 가진다. 예를 들자면 12의 약수는 1, 2, 3, 4, 6, 12이다. 1 x 12 = 2 x 6 = 3 * 4 이것을 이용해서 첫 번째 약수와 마지막 약수를 곱하여 특정 수를 찾아낼 수 있다. min()과 max()..
문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 코드 while True: try: n = int(input()) except: break # 1로만 이루어진 수 num = 1 # 수의 자리수 cnt = 1 while num%n!=0: num = num * 10 + 1 cnt += 1 print(cnt) 나의 생각 try와 except 구문을 사용하여 입력을 받다가 오류가 발생하면(예를 들어, 입력이 더 이상 없거나 정수가 아닌 값이 들어올 경우) 루프 오류가 발생하지 않으면 num을 10을 곱한 뒤 1을 더해서 다음 수를 만들어 나간다. 그리고 해당 수를 n으로 나눈 나머지를 확인. 만약..
시간 복잡도(Time Complexity) 컴퓨터는 1초에 연산을 몇 번 할 수 있을까? 문제를 풀 때는 대략 1초에서 1억번 정도로 잡는다. 이렇듯 알고리즘 문제를 해결할 때, 코드의 실행 시간과 메모리 사용량은 중요한 요소이다. 효율적인 알고리즘을 작성하려면 어떻게 코드를 구성해야 할지 고민해야 한다. 이 때 중요한 개념 중 하나가 시간 복잡도와 공간 복잡도, Big-O 표기법이다. 시간 복잡도란 무엇인가? 알고리즘의 시간 복잡도는 입력값의 크기에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타내는 지표이다. 즉, 내 코드의 실행 시간이 얼마 걸리는지 알 수 있다. 시간 복잡도를 분석하여 입력값이 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 예측할 수 있다. 메모리는 시간이 흐를수록 효율적..
문제 nCm 의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) def count_number(n, k): count = 0 while n: n //= k count += n return count five_count = count_number(N, 5) - count_number(M, 5) - count_number(N - M, 5) two_count = count_number(N, 2) - count_number(M, 2) - count_number(N - M, 2) answer = min(five_count, two_count) print(answer) 나의 생각 ..
문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 코드 import sys, math input = sys.stdin.readline n = str(math.factorial(int(input())))[::-1] # 팩토리얼 계산 후 뒤집어주기 cnt = 0 for digit in n: if digit == '0': cnt += 1 else: break print(cnt) 나는 팩토리얼 값을 문자열로 만들어서 뒤집은 다음 '0'을 찾아줬다. 나의 생각 다른 풀이 방법을 찾아보았다. 1. 팩토리얼 값을 구한 다음에 n을 10으로 계속 나눠 주는 것 import sys,math input = sys.stdin.readline n = math.factori..
1. 알고리즘이란? 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법, 문제를 해결하는 방법 한 문제를 해결하는 방법은 한 가지만 있는 게 아니라 무수히 많을 수 있다. 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화하기. (BFS, DFS, DP, 다익스트라 등등) 각 상황에 적합한 알고리즘을 선택할 수 있어야 한다 2. 알고리즘 평가기준 1. 시간 복잡도: 적은 시간을 잡아먹는 알고리즘 2. 공간 복잡도(메모리): 최대한 적은 용량의 메모리를 사용 3. 구현 복잡도: 간단하게 구현 코테에서는 공간보다는 시간을 더 중요하게 생각한다. 코딩테스트 준비하기 1.시간 복잡도 알고리즘 선택의 기준이 되는 시간 복잡도 시간 복잡도를 정의하는 3가지 유형 빅-오메가: 최선일 때 연산 횟수 빅-세타: 보통일 ..
문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 코드 import sys input = sys.stdin.readline n = int(input()) res = 1 # 1은 곱해도 똑같으니까 제외 for i in range(2, n+1): res *= i print(res) 나의 생각 찾아보니 math 모듈의 factorial 함수를 사용하면 더 간결하게 작성할 수 있다 !! import sys, math input = sys.stdin.readline n = int(input()) print(math.factorial(n))
문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 코드 import sys input = sys.stdin.readline prime = [True] * 1_000_001 max_ = int(1_000_001 ** 0.5) for i in ra..
