algorithm (20) 썸네일형 리스트형 힙 정렬(Heap Sort) 힙 정렬은 분할 정복 알고리즘의 대표 격인 병합 정렬과 퀵 정렬만큼 빠른 알고리즘이다. 힙 정렬은 힙 트리 구조를 활용한 정렬 기법을 말한다. 여기서 힙은 완전 이진 트리로 구성된 구조인데, 완전 이진 트리(Complete Binary Tree)는 이진 트리 중에서도 트리의 노드가 중간에 빈 곳없이 모두 채워져 있는 이진 트리를 말한다. 완전 이진 트리이면서 힙의 특성을 갖고 있는 것을 힙이라고 하는데, 이 특성은 부모 노드가 자식 노드보다 무조건 크거나 작은 특성을 말한다. 최소 힙은 부모가 항상 자식 노드보다 작은 값을 가진 힙이고 최대 힙은 부모 노드가 항상 자식 노드보다 큰 값을 가진 힙이다. 다만 자식 노드들끼리는 대소 관계가 정해지지 않는다. 오름차순 정렬을 구현한다고 했을 때 우리는 최대 힙.. 병합 정렬 알고리즘(Merge Sort) 병합 정렬 앞에서 살펴본 퀵 정렬과 같이 분할 정복 개념을 사용한 정렬이다. 둘의 차이점은 데이터를 분할 할때 병합정렬에서는 반드시 반으로 나눈다는 것이다. 따라서 N * log N의 성능을 보장하는 것이 병합 정렬 알고리즘이다. 그렇지만 평균적으로는 퀵정렬이 더 빠르다. 병합 정렬의 개념은 '일단 데이터를 모두 각각 반으로 쪼개고 본다!' 이다. 즉 데이터를 계속 쪼개서 각각의 데이터가 하나가 되었을 때부터 시작한다. 그림으로 한번 표현해보았다. 이제 모두 쪼개진 데이터로부터 시작해서 각각의 데이터를 병합(Merge) 해나갈 텐데, 두 집합의 데이터를 비교해서 정렬하여 병합한다. 따라서 병합의 단계가 진행될 때마다, 그 집합은 정렬이 되어있음이 보장된다. 이게 무슨 말이냐 하면, 데이터가 위와 같다고 .. 퀵정렬 알고리즘(Quick Sort) 퀵 정렬 퀵정렬 알고리즘은 대표적인 빠른 알고리즘으로서 '분할 정복' 기법을 활용하는 알고리즘이다. 평균적으로 O(N*logN)의 속도를 내지만 최악의 경우에는 O(N^2)의 속도를 낼 수도 있다. 퀵정렬은 '피벗'(pivot)이라는 하나의 값을 기준으로 큰 숫자와 작은 숫자를 교환한 후에 배열을 두 부분으로 나눈다. 기본적인 퀵정렬은 피벗 값을 가장 왼쪽에 있는 값으로 정한다. 즉 위 데이터에서는 7로 정한다. 그 다음 피벗보다 피벗보다 큰 값을 왼쪽에서부터 찾고, 피벗보다 작은 값을 데이터의 오른쪽에서부터 찾는다. 큰 값은 9, 작은 값은 4이다. 이 두 값의 위치를 교환한다. 다시 피벗보다 큰 값을 왼쪽에서부터 찾고, 작은 값을 오른쪽에서부터 찾는다. 이번에는 큰 값이 9, 작은 값이 6인데 두 값.. 객체지향 프로그래밍이란? 객체지향 프로그래밍 (Object Oriented Programming) 프로그램을 단순히 데이터와 처리방법의 모임으로 보는시각에서 벗어나서, 프로그램을 수많은 객체로 나누어 객체들간의 상호작용으로 서술하는 방식을 말한다. 여기서 객체는 하나의 역할을 수행하는 단위로서 변수와 메서드의 묶음을 의미한다. 각각의 객체는 메시지 전달을 통해 통신하며, 데이터를 처리할 수 있다. 객체지향 프로그래밍의 장점 - 코드 재사용이 가능한 장점이 있다. 상속을 통해 확장을 통한 재사용이 가능하다. (재사용이 목적이 아니고 확장에 초점을 둔다) - 유지보수가 보다 쉽다. 연관된 코드가 모여있기 때문에 코드를 수정할때, 제한된 영역만 고치면 된다. - 클래스(객체)별로 모듈화하여 사용하기 때문에 대형 프로젝트를 구성하는 데.. 배열과 연결리스트 배열 (Array) 다수의 데이터를 저장할 수 있는 자료구조 정적 타입의 언어에서는 한가지 타입의 자료만 저장할 수 있다. (C언어) 동적 타입의 언어에서는 여러가지 다른 타입의 자료가 저장 될 수 있다. (자바스크립트, 파이썬) 컴파일언어에서는 배열의 크기가 정적이기 때문에 한번 생성하면 바꿀수 없다. JS, Python 같은 스크립트 언어에서는 배열의 크기가 동적으로 조절 될 수 있다. bracket([])을 통해서 자료에 접근할 수 있다. const array = [0, 1, 2]; console.log(array[2]) // 2 특정 데이터에 접근하는 것은 O(1)의 시간복잡도가 요구된다. 중괄호를 이용해서 해당 인덱스에 바로 접근할 수 있기 때문이다. 데이터를 검색(조회)하는 데에는 최대 배열의.. 인접행렬과 인접리스트 그래프는 비선형 자료구조의 하나로서 정점(노드)과 간선(엣지)으로 이루어진 구조입니다. 정점들 간에는 서로를 이어주는 간선이 있을 수도 있고 없을 수도 있습니다. 그래프 상에 존재하는 각 두 정점들 간의 관계(간선이 있는지 없는지)를 구조화해서 나타 낼 수 있는데, 이를 인접 행렬과 인접 리스트라고 칭합니다. 그래프의 간선은 방향을 가질 수 있지만 이 글에서는 방향이 없는 간선을 가진 그래프를 기준으로 인접 행렬과 리스트를 다루겠습니다. 인접 행렬 (Adjacency Matrix) 인접 행렬은 2차원 배열로서 노드 갯수 * 노드갯수 만큼의 크기를 가지며 즉, N * N 배열이라고 생각하시면 됩니다. 이 2차원 배열을 adjs라 하고 adjs[i][j] 를 통해서 해당 값에 접근을 하면 이 값은 노드 i .. [6kyu] Compare powers 문제설명 You certainly can tell which is the larger number between 210 and 215.But what about, say, 210 and 310? You know this one too.Things tend to get a bit more complicated with both different bases and exponents: which is larger between 39 and 56?Well, by now you have surely guessed that you have to build a function to compare powers, returning -1 if the first member is larger, 0 if they are eq.. [6kyu] Financing a purchase 문제설명Description:The description is rather long but it tries to explain what a financing plan is.The fixed monthly payment for a fixed rate mortgage is the amount paid by the borrower every month that ensures that the loan is paid off in full with interest at the end of its term.The monthly payment formula is based on the annuity formula. The monthly payment c depends upon:rate - the monthly inte.. 이전 1 2 3 다음
