[CS기초] 스택(Stack), 큐(Queue)
·
크래프톤 정글/CS기초(키워드, 개념정리)
스택(Stack)스택 개요스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다.   스택의 특징먼저 들어온 데이터가 가장 늦게 나갈 수 있는 FILO(선입후출) 구조이다무조건 최상단(맨 뒤)에 요소를 넣고 빼야 하기 때문에 요소를 추가하거나 제거하는 데 O(1)의 시간이 걸린다최상단(맨 뒤)의 요소를 확인하는 데 O(1)의 시간이 걸린다.원칙적으로는 최상단(맨 뒤)의 요소만 확인이 가능하다다만, 배열로 스택을 구현하면 스택 중간의 원소도 확인 가능하게 구현이 가능하다 파이썬에서 스택의 구현파이썬에서는 단순 배열로 스택을 구현해 사용한다.# 배열로 스택 자료구조를 구현해 사용stack = []# push: 스택 최상단에 요소 추가stack.append(28)# pop: 스택 최상단에서 ..
[중간정리] 2주차 - 해시 충돌과 체이닝, 병합 정렬, 큐, 캐시 메모리, 프로세스/스레드
·
크래프톤 정글/CS기초(키워드, 개념정리)
해시 충돌과 체이닝해시 충돌(Hash Collision)은 해시 테이블에서 두 개 이상의 서로 다른 키가 동일한 저장공간(인덱스)에 할당되는 현상이다. 해시 테이블에서는 주어진 키를 해시 함수를 통해 테이블의 인덱스로 변환하는데, 해시 함수의 특성상 입력 값의 범위를 제한된 인덱스 범위로 축소시키므로 서로 다른 키 값이 같은 해시 값을 가질 수 있게 된다. 그리고 이로 인해 충돌이 발생하게 된다. 체이닝(Chaining)은 해시 충돌 문제를 해결하기 위한 대표적인 방법 중 하나로, 해시 테이블의 각 인덱스에 연결 리스트(Linked List)를 두어 충돌이 발생한 여러 키-값 쌍을 함께 저장하는 방법이다. 체이닝을 사용하면 충돌이 발생하더라도 데이터의 손실 없이 여러 데이터를 동일한 인덱스에 저장할 수 ..
[CS기초] 분할 정복(Divide and Conquer)
·
크래프톤 정글/CS기초(키워드, 개념정리)
분할 정복 (Divide and Conquer) 개요분할 정복은 문제를 더 작은 하위 문제로 나누고 각각을 해결한 뒤 결과를 합쳐 원래 문제를 해결하는 알고리즘인데요. 문제를 자연스럽게 나눌 수 있거나, 하위 문제 간의 중복 계산이 없는 복잡한 문제를 효율적으로 해결하는 데 자주 사용됩니다.  분할 정복의 3단계분할 (Divide)해결할 문제를 동일하거나 유사한 형태의 더 작은 하위 문제(Subproblem)로 나누는 과정하위 문제는 원래 문제보다 크기가 작아야 하며, 더 이상 나눌 수 없을 때까지 분할해야 한다정복 (Conquer)나눠진 하위 문제를 개별적으로 해결하는 과정하위 문제의 크기가 충분히 작으면 직접 계산과 같은 직관적인 방식으로 해결한다결합 (Combine)하위 문제의 해결 결과를 합쳐 원..
[CS기초] 이분 탐색(Binary Search)
·
크래프톤 정글/CS기초(키워드, 개념정리)
이분 탐색 (Binary Search) 개요이분 탐색은 정렬된 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법인데요. 이분 탐색을 수행하기 위해서는 다음 두 가지 조건을 만족해야 합니다.주어진 배열이 반드시 정렬되어 있어야 한다.무한 루프에 빠지지 않게 중간값을 잘 정해야 한다. 이분 탐색의 활용이분 탐색을 진행하게 되면, 시작값과 끝값이 엇갈릴 때까지 배열의 중간값이 찾는 값과 맞는지 확인하게 됩니다. 이때 배열의 중간값이 찾는 값이라면 그 위치를 반환해줍니다. 그런데 같지 않고 배열의 중간값이 찾는 값보다 작다면 배열을 중간으로 나눴을 때의 오른쪽에 있다는 뜻이므로 시작값을 갱신해주고, 반대의 경우라면 끝값을 갱신해줍니다.# 특정..
[중간정리] 1주차 - 재귀 함수, 피보나치 수열, 퀵 정렬, CPU의 PC/ALU
·
크래프톤 정글/CS기초(키워드, 개념정리)
재귀 함수재귀 함수의 장단점장점코드가 직관적이고 간결해 이해하기 쉽다.단점호출 시 추가적으로 메모리를 사용해 메모리 소비가 많고, 과도한 호출 시 스택 오버플로우가 발생할 수 있다.반복문에 비해 실행 속도가 느리다. 피보나치 수열 반환 함수1항부터 n항까지의 피보나치 수열 반환 함수를 반복문/재귀문으로 각각 만들어보기. n이 0~2에 대한 처리는 두 방식 모두 같았다. 다만 n이 3이상일 때 원래 수열을 가지고 계속 덧붙여가느냐(반복문), 직전 n-1에 대한 피보나치 수열을 새롭게 불러와 덧붙여 반환하느냐(재귀문)의 차이가 있었다.반복문으로 구현한 피보나치 수열 반환 함수def pivo(n): if n == 0: return [] elif n == 1: return [..
[알고리즘] 백트래킹 기본 예제 코드(순열, 조합)
·
크래프톤 정글/CS기초(키워드, 개념정리)
백트래킹으로 순열, 조합 구하기백트래킹은 탐색 과정에서 불필요한 경로를 미리 차단하여 효율적으로 해를 찾는 기법인데요. 이를 활용하면 순열과 조합을 생성할 때, 가능한 모든 경우를 탐색하면서도 불필요한 연산을 줄일 수 있습니다.  순열 (같은 수 중복 X)n, m = map(int, input().split())arr = [x for x in range(1, n+1)]result = [0] * mvisited = [False] * ndef func(k): if k == m: print(*result) return for i in range(n): if not visited[i]: visited[i] = True res..
[CS기초] 정수론(Number Theory)
·
크래프톤 정글/CS기초(키워드, 개념정리)
정수론 개요정수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문으로, 수학 체계에서 원점이자 정점 그 자체라고 할 수 있는데요. 기초 수준에서는 정수 그 자체보다는 자연수, 그 중에서도 소수를 중점적으로 다룹니다. 소수 (Prime Number)1과 자기 자신으로만 나눠지는 수. 즉, 약수가 2개이며 2부터 N-1까지의 수로 나눠지지 않는 수를 말합니다.소수 판정법합성수(소수가 아닌 수)  N에서 1을 제외한 가장 작은 약수는 √N 이하라는. 그렇기 때문에 2부터 √N 이하의 자연수로 해당 수를 나눠보면 됩니다. 만약 도중에 나누어 떨어지게 되면 합성수, 아니라면 소수가 됩니다.# 소수 판별 함수def is_prime(number): if number == 1: return..
[CS기초] 완전 탐색(Brute Force)
·
크래프톤 정글/CS기초(키워드, 개념정리)
완전 탐색 (Brute Force) 개요완전 탐색은 가능한 모든 경우의 수를 탐색하여 정답을 찾아내는 알고리즘인데요. 직관적이고 단순하지만, 경우의 수가 많아지면 시간 효율이 나빠질 수 있습니다. 완전 탐색의 종류단순 브루트 포스 (Brute Force)가능한 모든 방법을 단순하게 시도하는 기법반복문과 조건문을 활용해 모든 경우를 하나씩 검사ex) 비밀번호를 0000~9999까지 하나씩 대입하여 찾는 방식백트래킹 (Backtracking)되돌아가면서 모든 경로를 탐색하는 기법.탐색 중 해당 경로가 조건에 맞지 않으면 탐색을 중단하고 되돌아가 다른 경로를 탐색한다.불필요한 탐색을 줄이기 때문에 단순 브루트 포스보다 효율적ex) N-Queen 문제, 미로 찾기순열 (Permutation)서로 다른 n개의 원..