공대생 도전 일지

자료구조와 알고리즘은 컴퓨터 과학에서 가장 핵심적인 주제 중 하나로, 데이터를 효율적으로 저장하고 처리하며 문제를 해결하는 방법을 다룹니다. 아래에 이를 체계적으로 정리했습니다.1. 자료구조 (Data Structures)자료구조는 데이터를 체계적으로 저장하고 관리하는 방법입니다. 자료구조는 사용 목적과 데이터의 특성에 따라 선택되며, 주요 자료구조와 그 특징은 다음과 같습니다.선형 자료구조 (Linear Data Structures)배열 (Array)특징: 고정된 크기의 연속된 메모리 공간에 데이터를 저장.장점: 인덱스를 이용한 빠른 접근 (O(1)).단점: 크기 고정, 삽입/삭제가 비효율적 (O(n)).연결 리스트 (Linked List)특징: 노드(Node)가 데이터와 다음 노드의 주소를 포함.장점..

최소 동전의 수를 구할 때는 그리디 알고리즘으로 해결 가능하다!만약 나누어 떨어지지않을 때 그리디 알고리즘으로 해결이 불가능하다.동적 계획법 = DP - 이전 계산한 값을 재사용하여 하나의 문제를 한 번만 풀게 하는 알고리즘!탑 다운 - 큰 문제부터 풀기 시작하여 작은 문제들을 재귀적으로 호출하여 답을 구하는 방식바텀 업 - 작은 문제들을 먼저 풀기 시작하여 최종적으로 가장 큰 문제들을 해결하는 방식이다.배열에 저장하여 반복 작업을 줄이는 기법이 핵심이다.조건!겹치는 부분(작은) 문제 - 어떠한 문제가 여러 개의 부분(하위) 문제로 쪼갤 수 있을 때 사용한다.최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용한다.피보나치를 재귀로 구하면 구했던 값을 여러번 구하게 된다.Dp를 ..

재귀 - 자신을 정의할 때 자기 자신을 참조하는 것 함수에서 자기 자신을 호출한다!def fibo(n): if n항상 무한 루프에 빠지지 않도록 잘 설정해야 한다! 정렬 - 데이터를 오름차순 및 내림차순 등 특정한 기준으로 정렬하는 것삽입 - 앞에서부터 차례대로 비교하여 자신의 위치를 찾는다 = 구현 간단, n^2버블 - 두 수를 바꾸는 swap를 많이 사용한다. = 느리지(n^2)만 간단합병 - 퀵 - 피벗을 사용하여 기준으로 정렬한다.힙 - 최대 힙(부모 노드가 자식 노드보다 큰 트리)C++ - intro SortPython - Tim SortJAVA - 병합, 팀 정렬  트리 위의 게임시간 제한: 1 초정점 N개의 트리에서 두 사람이 게임을 진행하려 한다.각 정점은 1번부터 N번 까지 번호가 매겨져..

회문 - 앞뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열ex ) "1234321", "level"def is_palindrime(s): for i in range(len(s)): if s[i]!=s[len(s) -i -1]: return False return Truedef is_palindrome(s): return s == s[::-1]올바른 괄호 문자열 (VPS)스택을 사용해서 해결하는 것으로 )가 입력될 때마다, 스택에 있는 (를 하나씩 지운다!(가 없으면 올바른 괄호 문자열이 아니다.모두 순회한 뒤 스택이 비어있으면 올바른 괄호 문자열이다.분할정복 - 큰 문제를 작은 문제로 분할하여 작은 문제의 답을 모아 큰 문제의 답을 구한다.합병 정렬..

유클리드 호제법 - 최대 공약수를 구할 때 사용한다.N의 약수 찾기1 ~ N까지 나누어서 나머지가 0이 되는 수의 개수 찾기 = 복잡도 N호제법 - 서로 나눈다!두 자연주 a,b에 대해 (a>b) a를 b로 나눈 나머지를 r이라 하면 a,b의 최대 공약수는 b와 r의 최대 공약수와 동일하다.b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.1071과 1029를 구하자!1071 % 1029 = 421029 % 42 = 21 42는 21로 나누어 떨어지므로 최대 공약수는 21이다! 코드로 구현하자! def GCD(a,b): while b: a,b = b,a%b return aGCD - 최..

시간 복잡도 - 문제를 해결하는 데 걸리는 시간과 입력 사이의 관계빅 오 - 상한 접근 = 최악 경우빅 오메가 - 하한 접근 = 최선의 경우빅 세타 - 둘의 평균빅 오 표기법 종류1 - 일정한 복잡도 = 입력의 크기와 상관 없이 즉시 출력값을 얻어낼 수 있다.log N - N이 커질 수록 N보다 1의 복잡도에 가까워진다. = 중간값을 제시하면서 경우의 수를 절반 씩 나누는 법N - 선형 복잡도 = 입력과 실행시간이 같은 비율로 증가 (입력 값이 커질수록 계수의 의미가 퇴색)N log N -N^2 - 2차 복잡도 = 2중 for문에서 보인다.2^N - 지수 복잡도 = 특별한 경우를 제외하고는 안나오므로 다른 접근 방식을 고민해보는 것이 좋다.N! - 시간 복잡도가 가장 크다.시간 복잡도에 따라 실행 시간이..

https://www.youtube.com/watch?v=nyjFmDUDgO4 길찾기갈 수 있는 지점을 기록할 리스트 생성하고, 시작 위치 넣기1. 리스트[0] 확인하여 그위치 간 뒤 리스트[0] 삭제하고 서있는 지점 -1로 두기 - 더 이상 갈 곳이 없다면 도착지에 갈 수 없다.2. 이동가능한 지점을 리스트에 넣기 - 목적지가 리스트에 있으면 도달 가능한 것이다.3. 1번으로 돌아가기반복하다보면 길을 찾는다.너비 우선 탐색 방식이다! - BFS리스트의 마지막을 꺼내면 깊이 우선 탐색 방식 - DFShttps://www.youtube.com/watch?v=qaiuC3Q73-M다익스트라 - 최단 경로  https://jeong-devlog.tistory.com/entry/%EC%BD%94%EB%94%A9-..

퀵 정렬 Alg quickSort(l) 1. if(l.size()>1){ k = a position in l lt, eq, gt = partition(l,k) quickSort(lt) quickSort(gt) l = merage(lt,eq,gt) } 2. return 피봇을 기준으로 큰 것은 오른쪽, 작은것은 왼쪽으로 나눈뒤 그 나눈 것 다시 재귀하여 크기 1이 될 때 까지 돌리기. 합치는 것은 그대로 합치기 분할 합병정렬에선 merge가 오래걸렸지만 퀵정렬에서는 partition이 오래걸린다. Alg partition(l,k) 1. p = l.get(k) 2. lt,eq,gt = empty list 3. while(!l.isEmpty()){ e = l.removeFirst if(e p} gt.addLa..

기말 요약 퀵 기본 원리 1. lt, eq, gt = partition(l,k) 2. quickSort(lt) 3. quickSort(gt) partition(l,k) 1. p = l.get(k) 2. e = l.removeFirst 3. if (e p} gt.addLast(e) 4.return lt,eq,gt inPlacePartition(a,l,r,k) 1. p = a[k] 2. a[k] swap a[r] 3. i = l 4. j = r-1 5. while(i

연습문제 n개의 항목집합 S의 각 항목 i는 양의 이득 bi와 양의 무게 wi로 이루어졌다. 주어진 무게 W를 넘지 않으면서 최대 이득이 되는 S의 부분집합을 계산하는 효율적인 탐욕 알고리즘 Fractional-knapsack(S,W)을 작성하라 Alg fractionalKnapsack(S,W) 1. for dach i to S{ xi = 0 vi = bi/wi //무게에 따른 효율 } 2. w = 0 3. Q = a priority queue contaning all the items of S using vi as keys 4. while (w < W){ i = Q.removeMin() //왜 remove min인진 모르겠지만 고효율 부터 뽑아서 넣는다. xi = min(wi,W-w) // 무게가 넘치..