본문 바로가기

분류 전체보기126

이진탐색 순차 탐색 vs 이진 탐색ex) 리스트에서 12인 원소의 위치 찾기순차 탐색리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인 → 시간복잡도: O(N)이진 탐색정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색 → 시간복잡도: O(logN)이진탐색 수행할 때 시작점(left)와 끝점(end)을 기준으로 탐색 범위 명시각 단계마다 탐색 범위를 2로 나누기이상적인 경우 매 단계마다 범위가 반으로 감소 → log 복잡도를 가짐대표적인 사례매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우이진 탐색 코드이진 탐색은 배열이 정렬되어있다는 가정하에 수행1. 재귀함수 이용function binarySea.. 2026. 4. 4.

그리디(Greedy)/탐욕적 알고리즘 그리디 알고리즘현재 상황에서 당장 가장 좋아보이는 상황만을 선택하는 알고리즘최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많음 → 최적의 해에 가장 가까운 근사 해를 구할 수 있음ex) 루트에서 출발해서 단말 노드까지 가는 경우, 거쳐가는 노드의 합이 가장 큰 경우 구하기완전탐색으로 풀기최적의 해: 10 (1→4→5)모든 상황을 고려해야 함그리디 알고리즘으로 풀기매 상황에서 단순히 가장 큰 노드를 선택: 8 (1→5→2)모든 경우의 수를 고려하지 않아도 되지만, 최적의 해는 아니다![접근 방식]1. 방법 고안하기: 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안2. 정당성 확인하기: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인(증명 단계) ex) 거스름돈 문제카운터에 500원, .. 2026. 4. 4.

정렬(Sorting)-선택정렬, 버블정렬, 삽입정렬, 병합정렬 1. 선택 정렬(Selection Sort)매 단계에서 '아직 처리되지 않은 가장 작은 원소를 선택'해서 앞으로 보내는 정렬 방법앞으로 보내진 원소는 더 이상 위치가 변경되지 않음선형 탐색: 매 단계에서 가장 작은 것 선택하는데 약 N번의 연산 필요시간 복잡도: O(N2) → 비효율적[동작방식]1. 각 단계에서 가장 작은 원소를 선택2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치 교체 2. 버블 정렬(Bubble Sort)버블: 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고해서 붙여진 이름이다. 인접한 두 원소를 확인해서 정렬이 안되어 있다면 위치를 서로 변경→ 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정함!(즉, 오른쪽부터 차례대로 정렬됨)[동작 방식]1. 첫 번째.. 2026. 4. 4.

즉시 실행 함수 즉시 실행 함수, IIFE(Immediately-involked-function): 즉시 실행되는 함수 주로 함수를 선언하자마자 바로 호출을 할 때 사용 즉시 실행 함수를 사용이유 const a=1; function ong(x){ document.write(x+1); } ong(a); ong함수가 호출되면, 문서에 매개변수 x에 1을 더한 값을 씀 함수 표현은 함수를 정의하고, 변수에 함수를 저장하고 실행하는 과정인 반면, 즉시 실행함수는 함수를 정의하고 바로 실행 → 즉, 함수를 생성하고 따로 함수를 호출하는 것이 아니라, 함수를 정의하자마자 바로 함수를 실행하는 방식 1. 초기화 코드 부분에 사용 : 변수를 전역으로 선언하는 것을 피하기 위하여(코드 충돌없이 구현 가능) ex) var initText.. 2023. 1. 6.

이전 1 ··· 18 19 20 21 22 23 24 ··· 32 다음

티스토리툴바