동적계획법 (Dynamic Programming) 문제를 쪼개서 작은 문제의 답을 구하고 그걸로 더 큰 문제의 답을 구하는 것을 반복 1) 정의 : DP함수의 정의 2) 구하는 답 : 문제에서 요구하는 정답 (출력값) 3) 초기값 : DP함수의 초기값 4) 점화식 : DP함수의 점화식 피보나치 수열 1) 정의 : f(i) : i번째 피보나치 수 2) 구하는 답 : f(n) 3) 초기값 : f(0) = 0 f(1) = 1 4) 점화식 : f(i) = f(i-2) + f(i-1) if i >= 2 1) Bottom-up 방식으로 구현 : 반복문 let input = Int(readLine()!)! var arr = [Int]() arr.append(0) arr.append(1) for i in 2...90 ..

👉 그래프 정점과 정점간의 관계를 표시하는 간선으로 구성된 자료 ex) 지하철 노선의 최단 경로 (지하철역 = 정점) 👉 그래프 구성요소 1) 정점 (Node, Vertex) 2) 간선 (Edge) 👉 그래프 관련 용어 1) 방향 방향 그래프 무방향 그래프 (=양방향 그래프) 2) 순환 (cycle) 순환 그래프 비순환 그래프 → 어디에도 사이클이 하나라도 있으면 순환그래프 방향성 비순환 그래프 (DAG)→ 과거에서 미래로 계속 진행하기에 방향성 → 미래에서 과거로 갈 수 없기에 비순환 ex) 블록체인, 깃허브브랜치 3) 연결요소 1개 안에 있는 노드들은 서로 이동가능 👉 코드로 그래프 나타내는 방법 1) 인접행렬 검색 속도가 빠르다 O(1) 2) 인접리스트 차지하는 메모리가 적음 시간복잡도 O(n) 간..

배열 삽입삭제는 느리고 조회는 빠르다 배열의 인덱스를 지정하여 한 삽입삭제의 시간복잡도 : O(n) insert() 는 느린 연산이다. 마지막에 추가하는 시간복잡도 O(1) append() 조회 → 임의접근이 가능하기 때문에 속도가 빠름 O(1) 임의 접근 : 인덱스값이 있기에 연결리스트 배열과 반대 삽입삭제는 빠르고 조회는 느리다 insert() → O(1) delete() → O(1) 임의접근이 가능하지 않음 (어디있는 지 보장할 수 없어서) 처음 노드가 다음 노드의 주소값을 가지고 있기에 스택 선입후출 , 후입선출 들어가는 순서와 나가는 순서가 반대 마지막으로 들어온 게 제일 처음으로 나간다 삽입삭제 → O(1) 무조건 맨위의 값이 나가고 들어올때도 마지막으로 들어오기 때문에 큐 스택의 반대 선입선..

알고리즘의 시간복잡도 입력의 크기가 커질때 시간이 어떤 속도로 증가하는 지 나타냄 시간 복잡도는 O()으로 표기 1) 규칙 입력의 크기 : n ex: 입력이 정수 배열일 때 n은 배열의 크기를 나타낸다 / 입력이 문자열일 때 n은 문자열의 길이를 나타낸다 O(1) 코드가 단일 명령어로만 구성되어 있을 때 (ex: a += 1) O(n) 반복문 안의 내용이 n번 수행될 때 for i in 0...count { //...... } O(n2) 이중반복문 for i in 0...count { for j in 0...count { //..... } } TIP ! 코드에서 시간복잡도가 다양하게 구성되어 있을 때는 가장 큰 것이 적용된다. 어차피 가장 느린 것이 있으면 느리기 때문이다. TIP ! sort() = ..