![]()
P (Polynomial time) Problem결정 문제 중에서, 결과를 다항 시간(polynomial time) 안에 항상 계산할 수 있는 문제들의 집합어떤 문제 L이 있고 입력 x (x∈L)에 대해 항상 다항식 시간 내에 "예/아니오"로 답할 수 있으면 그 문제는 P 클래스에 속함NP (Nondeterministic Polynomial time) Problem결정 문제 중에서, 정답이 ‘있다’는 증거가 주어졌을 때, 그것이 맞는지 다항 시간 안에 검증 가능한 문제들의 집합어떤 문제 L이 있고 입력 x에 대해, "예"라고 주장하는 증거 y가 주어지면 검증기 V(x,y) 가 다항 시간 안에 그걸 확인할 수 있으면 그 문제는 NP 클래스에 속함NP-hard Problem모든 NP 문제를 다항 시간에 환원..
![]()
Brute-Force Brute-Force은 가능한 모든 경우의 수를 탐색하여 원하는 결과를 찾는 방식이다. Baekjoon - Bruteforcing Bitmask 비트마스크(Bitmask)는 이진수의 비트를 사용하여 집합의 원소 여부를 표현하는 방식이다. Baekjoon - Bitmask Recursion 재귀(Recursion)는 함수가 자기 자신을 호출하는 것을 말한다. Baekjoon - Recursion Backtracking 백트래킹(Backtracking)은 일반적으로 재귀적인 구조로 구현된다. 재귀 함수는 상태 공간 트리의 각 단계를 탐색하며, 조건 검사를 통해 유망한 상태로만 진행한다. 만약 조건을 만족하지 않으면 해당 단계의 탐색을 중단하고 이전 단계로 되돌아가며 탐색을 진행한다. B..
![]()
트리(Tree)는 계층적인 구조를 나타내며, 노드(node)라고 불리는 요소들의 모음으로 구성된다. 각 노드는 하나의 부모(parent) 노드와 0개 이상의 자식(children) 노드를 가질 수 있다. Baekjoon - Tree 트리의 주요 주제 및 개념은 다음과 같다. Trie 트라이(Trie)는 트리 자료 구조의 일종으로, 키-값 쌍의 집합을 저장하고 검색하는 데 사용되는 효율적인 자료 구조이다. "Trie"라는 이름은 retrieval(검색)의 첫 글자를 딴 것으로, 주로 문자열 데이터를 저장하고 검색하는 데 사용된다. Baekjoon - Trie 트라이 알고리즘의 기본적인 작동 원리는 다음과 같다: 삽입 (Insertion): 문자열을 삽입할 때, 문자열의 각 글자를 트라이의 노드에 연결하면서..
![]()
그래프(Graph)는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 다양한 현실 세계의 관계를 모델링하는 데 사용된다. Baekjoon - Graph Theory Baekjoon - Graph Traversal 그래프의 주요 주제 및 개념은 다음과 같다. Union-Find 유니온 파인드(Union-Find)는 여러 개의 집합을 효율적으로 관리하고 조작하기 위한 자료구조이다. 주로 상호 배타적인(disjoint) 집합들을 다루는 데 사용되며, 서로 중복되지 않는 원소들로 구성된 집합들의 관계를 다루는 것을 목적으로 한다. 유니온 파인드는 또한 "디스조인트 셋(Disjoint Set)" 또는 "합집합 찾기(Union Find)" 자료구조로도 불린다. Baekjoon - Disjoint Set ..
![]()
정수론(Number Theory)은 수와 정수에 대한 속성과 구조를 연구하는 수학의 분야이다. 이론적으로 숫자와 관련된 다양한 패턴과 규칙을 이해하고, 숫자 간의 상호작용과 특성을 연구하는 분야이다. Baekjoon - Number Theory 정수론의 주요 주제 및 개념은 다음과 같다: Prime Numbers Prime Number Test 소수 판별(Prime Number Test)은 주어진 수가 소수인지 아닌지를 확인하는 문제이다. Baekjoon - Primality Test 알고리즘은 다음과 같다: 1의 처리: 먼저, n이 1인 경우를 확인한다. 1은 소수가 아니기 때문에, 함수는 False를 반환한다. 범위 설정: 그 다음, 2부터 n의 제곱근까지의 숫자 범위를 반복문을 통해 확인한다. 이 ..
![]()
순열(Permutation)은 주어진 집합에서 원소를 선택하여 순서에 맞게 나열하는 방법이며, 조합(Combination)은 주어진 집합에서 원소를 선택하여 순서에 상관없이 나열하는 방법이다. Baekjoon - Combinatorics 다음은 순열과 조합 문제에 사용될 수 있는 코드이다: Permutation 순열 (Permutation) 순열은 주어진 집합의 원소들을 모두 이용하여 가능한 모든 순서대로 배열하는 방법을 의미한다. ex. 집합 {A, B, C}에서 2개의 원소를 선택하여 만들 수 있는 순열은 AB, AC, BA, BC, CA, CB 총 6가지이다. 중복 순열 (Repetition Permutation) 중복 순열은 주어진 집합에서 원소를 중복을 허용하여 r번 선택하여 나열하는 방법을 의..
![]()
탐욕 알고리즘 또는 그리디 알고리즘(Greedy Algorithm)은 각 단계에서 지금까지의 선택이 최적이라고 가정하고 진행하여 최종적으로 최적해에 도달하는 것을 목표로 한다. 이는 현재 상황에서 가장 좋아보이는 선택을 수행함으로써 지역 최적해를 찾아 전역 최적해를 구하는 것을 말한다. Baekjoon - Greedy 다음은 일반적으로 코딩 테스트에서 자주 출제되는 몇 가지 자료 구조와 관련된 문제 유형이다. Fractional knapsack problem 분할 가능한 배낭 문제(Fractional knapsack problem)은 한 가방(또는 컨테이너)에 담을 수 있는 무게 제한이 있는 경우, 주어진 물건들의 가치와 무게를 고려하여 가장 큰 가치를 가진 물건들을 선택하는 문제이다. 이 문제에서는 물..
![]()
동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 분할하여 해결하는 알고리즘 설계 기법이다. 이러한 기법은 하위 문제의 해결 방법을 저장하고 재활용하여 중복 계산을 피하며 효율적인 해결책을 찾아낸다. 동적 프로그래밍은 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems)라는 두 가지 특성을 갖고 있다. 최적 부분 구조는 주어진 문제의 최적 해결책이 하위 문제의 최적 해결책들로부터 구성될 수 있다는 것을 의미하며, 중복 부분 문제는 작은 하위 문제들 사이에 중복되는 계산이 존재한다는 것을 의미한다. Baekjoon - Dynamic Programming 동적 프로그래밍은 다음과 같이 두가지 방법이 있다...
![]()
탐색(Search)은 주어진 데이터 집합에서 특정 값을 찾거나 조건을 만족하는 값을 찾는 과정을 다룬다. 탐색 문제의 유형은 이진 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)로 나눌 수 있다. Binary Search 이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 탐색 알고리즘이다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀가는 방식으로 동작한다. Baekjoon - Binary Search 이진 탐색 알고리즘은 다음과 같이 동작한다: 시작과 끝을 초기화한다. 일반적으로 배열의 처음과 끝 인덱스를 사용한다. 이를 시작(start)와 끝(end)라고 부른다. 시작과 끝을 이용하여 중간 인덱스를 계산한다. 중간 인덱스(mid) = (start + end) ..
![]()
정렬(Sort)은 데이터를 특정 기준에 따라 순서대로 정렬하는 것을 의미한다. 정렬은 다양한 알고리즘과 기법을 사용하여 구현할 수 있으며, 프로그래밍 언어에서도 정렬을 위한 내장 함수나 라이브러리를 제공한다. Baekjoon - Sorting Algorithms Visualized - Sorting from functools import cmp_to_key arr = [(3, 6), (2, 4), (4, 5)] # arr 요소의 순서를 바꾸지 않음 sorted_arr = sorted(arr, key = lambda x: x[1], reverse = False) # arr 요소의 순서를 바꿈 arr.sort(key = lambda x: x[1], reverse = False) # 정렬 방식 선언 def s..
![]()
자료 구조(Data Structures)는 프로그래밍에서 데이터를 구성하고 조직하는 방법을 말한다. 코딩 테스트에서 자료 구조 문제는 주어진 문제를 해결하기 위해 효율적인 데이터 구조를 사용하는 방법을 확인하는데 사용된다. Baekjoon - Data Structures 다음은 일반적으로 코딩 테스트에서 자주 출제되는 몇 가지 자료 구조와 관련된 문제 유형이다. Array & List 배열(Array)은 정적 크기의 동일한 데이터 유형의 항목들을 인덱스로 접근하는 자료 구조이고, 리스트(List)는 동적 크기의 데이터 요소들의 시퀀스로 삽입, 삭제, 검색이 가능한 자료 구조이다. Priority Queue 우선순위 큐(Priority Queue)는 데이터를 저장하고 관리하는 자료구조로, 각 원소는 우선순..
![]()
문자열(String)은 컴퓨터 과학과 프로그래밍에서 사용되는 데이터 타입 중 하나로, 일련의 문자들의 시퀀스(sequence)를 나타낸다. 쉽게 말해, 문자열은 문자들이 순서대로 나열된 문자의 집합이다. Baekjoon - String String Method string = string1 + string2 string = string * integer string = string[index1:index2] string = "Hello %s!" %string """ %s 문자열 (String) %c 문자 1개( character) %d 정수 (Integer) %f 부동소수 (floating-point) %o 8진수 %x 16진수 %% Literal % (문자 % 자체) """ string = "{0}, ..
