코딩하는 해달이

선택 정렬이란?선택 정렬은 제자리 정렬(In- place sorting) 알고리즘의 하나로 원소를 넣을 위치는 이미 정해져있으며, 어떤 원소를 넣을지 선택하는 알고리즘입니다.선택 정렬 과정작업 순서리스트를 순회하며 가장 작은 요소 찾기가장 작은 요소와 첫 번째 요소 교환리스트의 다음 위치로 이동반복시간 복잡도최악, 평균, 최선 모든 경우에 O(n^2)의 시간 복잡도를 가집니다.공간 복잡도O(1): 제자리 정렬 알고리즘으로 추가적인 메모리 사용이 거의 없습니다.장점구현이 간단하고 이해하기 쉽습니다.단점시간 복잡도가 O(n^2)이기 때문에, 데이터의 크기가 큰 경우 비효율적입니다.코드 public void selectionSort(int[] array) { int n = array.leng..

버블 정렬이란?버블 정렬은 무작위로 배치되어있는 요소들을 일정한 기준에 맞추어 정렬하는데 그 방법이 인접한 두 요소를 비교하여 의도한 순서가 될 때까지 교체하는 알고리즘입니다.버블 정렬 과정작업 순서첫 번째 인덱스부터 시작해서 두 요소를 비교한다.첫 번째 요소가 두 번째 요소보다 크면 서로 교체한다.이제 두 번째 요소와 세 번째 요소를 비교하여 교체가 필요한 경우 교체한다.마지막 요소까지 반복한다.시간 복잡도사이클을 돌 때마다 n, n-1, n-2, .... , 2, 1번 실행되게 되므로 시간 복잡도는 O(n^2)이다.코드이를 코드로 나타내면 다음과 같다.public void bubbleSort(int[] array) { int n = array.length; // 배열의 모든 ..

위상 정렬위상 정렬은 주로 작업 순서를 정하거나 의존성 관계를 해결할 때 사용하는 알고리즘으로 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘이다.특징비순환 방향 그래프에서만 적용이 가능하다.정렬 결과가 여러가지 일 수 있다.사이클이 있는 그래프에서는 위상 정렬이 불가능하다.  - 사이클 : 한 정점에서 출발하여 간선과 정점을 지나 다시 출발했던 정점으로 돌아오는 것알고리즘 구현 방법DFS(깊이 우선 탐색) 기반 방법 : 그래프를 DFS로 탐색하며 탐색이 끝나느 정점부터 스택에 삽입, 스택에서 꺼내는 순서가 정렬의 결과진입차수 기반 방법 : 진입차수가 0인 정점을 큐에 넣고 하나씩 꺼내면서 간선을 제거, 큐에서 꺼내는 순서가 정렬의 결과시간 복잡도O(V + E) (V : 정점의 수,..

학습 목표 ▶ 재귀의 뜻을 이해한다. ▶ 재귀가 사용되는 문제의 예시들을 학습하여 재귀의 원리를 이해한다. ▶ 재귀와 수학적 귀납법 간의 밀접한 관계를 이해한다. # 재귀는 자주 등장하는 주제, 자료구조와 알고리즘을 공부하면서 반드시 알고 있어야 하는 주제 재귀(recursion)란? 내 안의 나를 찾는 것 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것 재귀 함수(recusive function), 재귀 호출(recursive call) 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법 재귀 알고리즘 자신과 성격은 똑같지만 크기만 작은 알고리즘(들)을 호출하는 알고리즘 복잡한 문제도 간..

알고리즘의 기술 방법 자연어를 이용한 서술적 표현 (영어 or 한국어) 장점 : 대화나 의사소통을 통해서 전달하기 때문에 의사소통만 가능하다면 편하게 전달이 가능함 단점 말하는 사람과 듣는 사람에 따라 다르게 이해할 수 있어 일관성과 명확성이 떨어짐 언어, 단어, 표현등에 의존적임 ex) 배열에서 최대값 찾기 알고리즘 도식화 : 흐름도 (flowchart) 장점 : 간단하고 명확하게 흐름을 표현 가능 단점 : 복잡한 알고리즘을 표현하기에는 어려울 수 있음 ex) 배열에서 최대값 찾기 알고리즘 가상코드를 이용한 추상화 : 의사 코드 (pseudo-code) 장점 의사코드를 실제코드로 변환하기만 하면 되기 때문에 편하게 구현이 가능 알고리즘 기술에 가장 많이 사용 코드지만 프로그래밍 언어에 대한 의존성이 없..

자료구조 데이터를 저장, 조직, 관리하는 방법 문제 해결에 사용할 부품 프로그래밍과 문제 해결 데이터와 구조 모듈에 대한 이해 프로그래밍 언어, 정수, 문자열,.... 리스트, 스택, 큐, 우선순위 큐, 검색트리, 그래프,..... 종류 선형 자료구조 배열 연속적인 메모리에 데이터를 저장하는 자료구조 특징 : 같은 형태의 데이터 집합을 같은 사이즈의 메모리로 나열 연결리스트 데이터를 연결하는 방식으로 저장하는 자료구조 특징 : 한 개의 노드가 데이터부분과 다음 데이터를 가르키는 포인터부분으로 나뉨 행렬 파이썬에서는 이중 리스트로 구현하게 되는 자료구조 특징 : 행과 열로 이루어져있음 스택 특징 : 마지막에 들어온 데이터가 가장 처음으로 나가는(Last In First Out) 구조로 이루어짐 큐 특징 :..