1. 위상정렬(Topological Sort)이란? 방향 그래프에서 선후관계에 따라 적절한 순서를 찾는 알고리즘 전체 순서가 아닌 일부 순서가 주어진 경우 여러가지 경우로 줄을 세울 수 있다 -문제 유형 어떤 작업ㄷ르에 대한 순서가 주어졌을 때 자신보다 선행되어야 할 일을 다 끝내야 작업에 들어갈 수 있게 주어졌을 때 2. 동작 원리 방향은 존재하지만 사이클은 존재해선 안 된다. (순서를 명확히 정할 수 없기 때문) -bfs 방식 위상정렬 indegree가 0인 노드를 큐에 넣어준다 큐의 front(현재 정점)을 방문한다 front()에 연결되어있는 다음 정점들을 방문하고 indegree[next]를 1씩 감소시킨다 감소시켰을 때 indegree가 0이라면 큐에 넣어준다 -dfs 방식 위상정렬 방문하지 ..

❗함수 1. 함수를 사용하는 이유? 코딩을 하다보면 같은 내용을 반복해서 작성할 때가 생기는데 이런 때에 조금 더 편리하게 코딩하기 위해 반복되는 내용을 함수로 정의해서 사용하게 된다. 2. 파이썬 함수의 구조 def 함수이름(매개변수): 수행할 문장1 수행할 문장2 3. 함수의 종류 -매개변수O, 리턴값O def add(a, b): return a+b print(add(1, 2)) -매개변수O, 리턴값X def add(a, b): print(a+b) -매개변수X, 리턴값O def sayHi(): return "Hi!" print(sayHi()) -매개변수X, 리턴값X def sayHi(): print("Hi!") 4. 함수 호출하기 -리턴값이 있는 경우 #1 result = add(1, 2) print..

❗리스트 1. 리스트 리스트 안에는 어떠한 자료형도 포함시킬 수 있고 그 요소들을 한 묶음으로 사용할 수 있다 #빈 리스트 생성하기 a = [] b = list() 2. 리스트의 인덱싱과 슬라이싱 문자열처럼 리스트도 인덱싱과 슬라이싱을 할 수 있다 각 요소를 0번째부터 리스트 전체 길이 - 1번째까지 가리킬 수 있다 -인덱싱 a = [1, 2, 3] a[0] -> 1 => 리스트 a의 0번째 자리에 있는 요소 a[-1] -> 3 => 리스트 a의 -1번째 자리에 있는 요소 -슬라이싱 시작범위 [1, 2] a[2:] -> [3, 4, 5] 3. 리스트 안에 리스트 a=['a', 'b', ['c', 'd', 'e']] a[0] = a a[2][0] = c a[2][1] = d a[2][2] = e 4. 리스..

1. 자료구조란? 자료를 효율적으로 표현하고 저장, 처리할 수 있도록 정리하는 것 삽입, 삭제, 탐색 세 가지 연산을 빨리 하기 위해 각 상황에 맞는 다양하고 효율적인 자료구조들이 많이 개발되었다. -스택 후입선출 구조로 마지막 삽입한 원소는 맨 위에 있고, 제일 먼저 삭제된다 웹 브라우저 방문기록(뒤로가기) 역순 문자열 만들기 실행 취소(undo) 후위 표기법 계산 수식의 괄호 검사(연산자 우선 순위 표현을 위한 괄호 검사) -큐 선입선출 구조로 뒤에서만 원소를 삽입하고 앞에서만 원소를 삭제할 수 있다 우선순위가 같은 작업 예약(프린터의 인쇄 대기열) 프로세스 관리 너비우선탐색 캐시 구현 -덱 큐의 양쪽 끝에서 삽입과 삭제 연산을 둘 다 수행할 수 있는 자료 구조 2. 동작 원리 -스택 push(삽입할..

1. 이분탐색(Binary Search)이란? 탐색 범위를 절반씩(두 부분으로 나누어서) 줄여 가며 원하는 값을 찾는 방식 이분 탐색을 실시하기 위해선 정렬된 배열이나 벡터가 필요하다 시간복잡도 또한 탐색 범위가 절반씩 줄어든다. -> O(logN) 2. 동작 원리 -이분 탐색 배열이나 벡터를 정렬한다 left, right값(범위의 최소, 최대)으로 mid값을 설정한다 mid값과 구하고자 하는 값(ans)를 비교한다 mid mid+1 mid > ans --> mid-1 ans를 찾을 때까지 반복 -결과값 구하고자하는 값을 찾았을 때 값을 리턴한다 최적의 해를 찾는 경우 left right이 되므로 종료된다 3. 코드 int arr[100005]; int binarySearch(int l..

1. DP(Dynamic Programming)이란? 하나의 큰 문제를 여러개의 작은 문제로 분할하여 푸는 방법 이미 계산된 작은 문제의 결과값을 별도의 메모리 영억에 저장해두고 활용한다 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킬 수 있다 방법: top-down(재귀), bottom-up(반복문) 대표예: 피보나치 수열 2. 동작 원리 -사용 조건 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 값은 그것을 포함하는 큰 문제에서도 동일한 값으로 사용된다. -사용 방법 완전 탐색으로 접근한다. 반복되는 부분 문제를 찾는다. 기저단계를 설정한다. (점화식으로 더이상 계산하지 못하는 부분) 점화식을 설정한다 중복된 문제를 한번만 계산하기 위해 메모이제이션을 이용한다(이전에 계산한..

1. 재귀란? 재귀(recursion)은 자신을 정의할 때 자기 자신을 재참조하는 방법 2. 동작 원리 재귀함수: 어떤 알고리즘이나 함수가 자기 자신을 호출하여 작업을 수행하는 방식의 함수 함수에서 자기 자신 함수를 또 호출해서 스택에 저장하기 때문에 탈출 조건이 없다면 스택 오버플로우 발생 재귀함수를 쓰는 대표적 예: 피보나치 수열, 팩토리얼, 순열, 분할정복 ※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!

1. 완전탐색(브루트포스 알고리즘)이란? 모든 경우의 수를 다 탐색하는 방법으로 '무식하게 푼다'라고도 한다 가능한 모든 경우의 수를 계산하고, 주어진 문제를 선형 구조로 구조화 한다. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색 후 구성된 해를 정리 2. 동작 원리 단순 for문: for문, if문 등으로 모든 케이스를 만들어서 탐색하는 방식 비트마스크: 2진수를 이용하는 컴퓨터 연산을 이용하는 방식 재귀 함수: 부분 문제로 쪼갤 수 있는 경우에 적합한 방식 순열: 주어진 입력에서 순서가 중요할 때 이용하는 방식 -> 경우의 수 N!, next_permutation, prev_permutation BFS/DFS: 그래프의 모든 정점을 탐색하는 완전 탐색 알고리즘 ※공부 중 작성한 내용이..

1. 정의 -벡터란? 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경할 수 있는 시퀀스 컨테이너 -페어란? 어떤 자료형을 쌍으로 묶어서 한 쌍으로 표현 -정렬이란? 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 것 -에라토스테네스의 체란? 소수판별법: 입력 받은 숫자보다 작은 모든 숫자로 나누어본다 입력 받은 숫자의 제곱근(루트 씌우기)보다 작은 모든 숫자로 나누어본다 에라토스테네스의 체 2. 동작 원리 -일차원 벡터 vector 객체이름(초기크기); push_back( ): 현재 벡터의 마지막 위치에 새로운 원소 삽입, 백터의 크기 1 증가 pop_back( ): 벡터의 마지막 원소 제거, 벡터가 비어있을 경우 오류 발생 size( ): 벡터의 원소 ..

1. 정의 -문자열이란? string이나 char[ ] 배열 초기화 함수: memset(배열이름, 초기화값, sizeof(배열이름)); -GCD란? Greatest Common Divisor: 최대공약수 -LCM이란? Least Common Multiple: 최소공배수 두 자연수의 공통된 배수 중 가장 작은 수 -> 최대공약수를 통해 구할 수 있음 2. 동작 원리 -GCD 방식1: 두 수 m, n를 입력받고 2부터 n까지 두 자연수를 모두 나누어보면 최대공약수를 구할 수 있음 방식2: 유클리드 호제법 m을 n으로 나눈 나머지를 r이라고 하면, m과 n의 최대공약수는 n과 r의 최대공약수와 같은 것을 이용 -LCM 두 수의 곱을 두 수의 최대공약수로 나누어주면 최소공배수를 알 수 있음 3. 코드 //GCD..