th42500의 TIL

프로그래머스의 문제를 풀다가 새롭게 알게된 이진 탐색에 대해 정리하였다. 이진 탐색(Binary Search)이란? 👉 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 👉 대상 데이터의 중앙값과 찾고 싶은 대상을 비교하여 데이터의 크기를 절반씩 줄여가며 대상을 찾음 👉 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 알고리즘 이진 탐색의 시간복잡도 👉 O(logN) 이진 탐색 알고리즘 탐색 과정 해당 알고리즘은 반드시 정렬된 상태에서 진행하여야 함 1️⃣ 현재 데이터 셋의 중앙값(mid) 선택 2️⃣ 중앙값 > 찾고 싶은 대상 값이라면 중앙값 기준으로 왼쪽 데이터셋 선택 3️⃣ 중앙값 < 찾고 싶은 대상이라면 중앙값 기준으로 오른쪽 데이터셋 선택 4️⃣ 중앙값 == 찾고 싶은 대상일때까..

피보나치 수열 이란? 👉 0(0항)과 1(1항)로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열 피보나치 수열 함수 피보나치 수열의 i번 째 값을 계산하는 함수 F 👉 F0 = 0, F1 = 1 👉 Fi = Fi-1 + Fi-2 (단, i >= 2 일 때) 피보나치 수를 구하는 재귀함수 위의 정의를 이용하여 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현 가능 fibo(n) IF n < 2 : RETURN n ELSE : RETURN fibo(n-1) + fibo(n - 2) 이 때 fibo(n)는 n항을 구하는 메소드(함수) 피보나치 수열을 구했을 때 문제점 피보나치를 재귀로 구현하였을 때 문제점은 매우 많은 중복 호출이 존재한다는 점 그렇다면 중복을 피할 수 있는 방법은 없을까? 이..

재귀, 순열, 순열과 조합의 차이는 정리했었는데 조합에 대해 정리한 글이 없다는 것을 지금 알게되어 늦게나마 정리를 해본다..🌱 조합 (Combination) 조합 (Combination) ? 👉 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 조합의 수식 nCr은 n개의 원소 중에 r개를 선택한다는 의미이며, 이는 n-1개의 원소 중 r-1개를 선택한 경우의 수와 n-1개의 원소 중 r개를 선택하는 경우의 수를 합친 것과 같음 즉, nCr = n-1Cr-1 + n-1Cr 이므로 재귀함수를 적용할 수 있음 재귀함수를 모른다면 밑의 링크를 참고해보자. 재귀 함수 👉 https://ichijeochi.tistory.com/11 재귀 (Recursive) 재귀 함수(Recursive Function) ..

BFS (Breadth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ BFS 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘으로, 너비 우선 탐색이라고도 불림 선입선출 형태의 Queue자료구조 활용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도 : O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 Queue에 삽입하고 방문 처리 2️⃣ Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3️⃣ 2️⃣ 과정을 수행할 수 없을 때까지 반복 ✔ 예시 1️⃣ 시작 ..

배열(Array) 배열이란? 👉 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조 배열의 필요성 👉 프로그램 내에서 여러 개의 변수가 필요할 때, 한번의 선언만으로 둘 이상의 변수를 선언할 수 있음 배열의 선언과 접근 1) 배열의 선언 자료형 이름[] = new 자료형[길이]; int arr[] = new int[10]; 2) 배열의 접근 배열명[인덱스번호] = 값; arr[0] = 20; 배열 순회 👉 ex) 2*n 배열 순회하는 방법 for(int i=0; i< arr.length(); i++) { for(int j=0; j 0; i--) { arr[i] = arr[i-1]; } arr[0] = temp; // 저장해두었던 원소 다시 채우기 } } 2️⃣ 배열 원소 왼쪽 Shift ..

DFS (Depth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ DFS 특징 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림 재귀적으로 구현 또는 후입선출 구조의 스택을 적용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도는 O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리 2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 ..