ETC/자료구조 이론4

• 

  [JAVA] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍의 조건 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다. 비효율적인 피보나치 수열 구현 import java.util.*; public class Main { // 피보나치 함수(Fibonacci Function)을 재귀함수로 구현 public static int fibo(int x) { if (x == 1 || x == 2) { return 1; } return fibo(x - 1) + fibo(x - 2); } public static void main(String[] args) { System.out.println(fibo(4)); } } 탑다.. ETC/자료구조 이론 2022. 9. 19.

• 

  [자료구조] Queue(큐) - Java, Python 큐(Queue) 큐는 선입선출(FIFO : First In First Out)로 처리되는 자료구조이다. 즉 먼저 들어가는 원소가 가장 먼저 나오는 구조이다. 위 사진에서 원소 1은 제일 먼저 큐에 들어왔기때문에 제일 먼저 제거된다. 이게 바로 선입선출이다.(FIFO : First In First Out) 큐에 원소를 넣는 것을 enqueue 라고 하며, 큐에서 원소를 제거하는 것을 dequeue 라고 한다. C, C++, Java, Python 또는 C#과 같은 다양한 언어들로 스택을 구현할 수 있지만, 성능은 거의 동일하다. 큐의 기본적인 명령어 - Enqueue : 큐 끝(마지막)에 원소 추가 - Dequeue : 큐 맨 앞(시작점)에 위치한 원소 제거 - IsEmpty : 큐가 비어있는지 체크 - .. ETC/자료구조 이론 2021. 8. 16.

• 

  [자료구조] Stack(스택) - Java, Python 스택 (Stack) 스택은 후입선출(LIFO : Last In First Out)로 처리되는 자료구조이다. 즉 스택의 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. 다시말해 데이터의 삽입과 삭제가 데이터의 한쪽 끝에서만 일어난다. 위와 같은 구조에서 우리는 크게 두가지 행동을 할 수 있다. - 새로운 접시를 추가하는것. - 맨 위의 접시를 제거하는것. 만약 새로운 접시를 맨 아래에 놓거나, 맨 위가 아닌 특정 위치에 놓고싶다면 놓고싶은 위치를 기준으로 위에 있는 접시들을 모두 제거한 후 추가해야한다. 이것이 바로 스택이 작동하는 방식이다. 후입선출(LIFO : Last In First Out)의 원리 Stack 위에 어떤 원소를 집어넣는것을 Push 라고 하고, 원소를 제거하는것을 Pop 이라고 .. ETC/자료구조 이론 2021. 8. 14.

• 

  [JAVA] 순차탐색(Sequential Search), 이진탐색(Binary Search) 순차탐색 ( Sequential Search ) 이진탐색 ( Binary Search ) int[] arr = {1, 19, 9, 7, 3, 11, 5, 109, 292, 30}; 위와 같은 배열이 있을때, 숫자 7이 몇번째에 있는지 알아내고자 한다. 순차탐색(Sequential Search) 순차탐색은 말 그대로 차례대로 비교해가면서 찾는것이다. arr[0]부터 하나하나 7인지 아닌지 확인하다 arr[3] 이 7이므로 탐색을 종료하게되는것이다. 순차탐색의 복잡도 만약 arr 배열에서 1을 탐색한다면 1번만에 찾아낼것이다. 19는 2번만에, 9는 3번만에 찾아낼 것이다. 30을 탐색한다면 10번만에 찾아낼것이다. 그렇다면, 탐색하는데 걸리는 평균 연산 횟수는 이 될것이다. 따라서 arr 배열의 크기가 n.. ETC/자료구조 이론 2020. 9. 8.