Ikjo's Technology blog

퀵 정렬이란? 퀵 정렬은 주어진 데이터 상 특정 값(피벗)을 기준으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 옮겨 2개의 파티션(Partition)으로 분할(Divide)해 나가는 방식으로 정렬한다. 퀵 정렬에 사용되는 기법을 분할 정복 알고리즘(Divide and conquer algorithm)이라고 하는데, 이는 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 일반적으로 재귀 함수(Recursive function)를 통해 자연스럽게 구현된다. 퀵 정렬은 주어진 데이터 상 최초 피벗을 몇 번째 데이터로 정하는지에 따라 그리고 데이터 상태에 따라 다른 성능을 보일 수 있는데, 대표적으로 배열의 첫 번째 데이터를 피벗으로 정하는 호어 분할 방식이 있..

실생활에서의 인터페이스 인터페이스란 무엇일까? 인터페이스는 객체(사람, 사물 등)간 상호작용하기 위한 행동(action)이라고 할 수 있다. 예를 들어, 어떤 고객이 식당에서 특정 메뉴를 주문한다고 가정했을 때, 고객이 식당에 특정 메뉴를 주문하기 위해서는 일종의 '수단'이 필요하다. 이때 이러한 수단에는 카운터 직원이나 키오스크 등이 존재할 수 있다. 즉, 가게에서는 고객의 주문을 위한 수단으로서 카운터 직원, 키오스크 등의 수단을 제공하는데, 이러한 수단들은 공통적으로 '주문 받기', '결제하기' 등의 행동으로 고객들과 상호작용한다. 고객 입장에서는 자신을 응대하는 수단이 무엇인지와 또한 내부 처리 과정이 어떤지에 대해서는 큰 관심이 없다. 단지 메뉴를 주문하기 위해 해당 수단이 제공하는 '주문 받기..

삽입 정렬이란? 삽입 정렬은 주어진 데이터들을 순회하면서 특정 데이터를 적절한 위치에 삽입하는 방식으로 정렬한다. 이때 마법의 단어 '적절한'이 들어갔는데, 이 단어가 이전에 다루었던 버블 정렬과 선택 정렬과의 차이를 낳는다. 이전에 다루었던 버블 정렬과 선택 정렬의 경우, 주어진 데이터의 정렬 상태 등에 상관없이 항상 모든 요소를 순회하면서 비교하는 비효율적인 문제가 있었다. 하지만 삽입 정렬의 경우, 순회 중 특정 데이터를 삽입할 적절한 위치를 찾으면 삽입 후 기존 순회를 중단하고 다음 순회로 넘어간다. 이로써 기존 데이터의 상태가 어느정도 정렬된 상태라면, 더욱 빠른 속도로 정렬할 수 있게 된다. 그림으로 삽입 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 ..

버블 정렬이란? 버블 정렬은 정렬 알고리즘 중에서 가장 원시적인 방법으로서 주어진 데이터들을 순회하면서 서로 붙어있는 2개의 데이터씩 비교해, 하나씩 맨 뒤에 차곡차곡 옮겨놓는 방식으로 정렬한다. 그림으로 버블 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 버블 정렬을 통해 오름차순으로 정렬해보자. 우선 맨 앞에서부터 서로 붙어있는 2개의 데이터씩 비교를 하는데, 작은 값을 왼쪽에 큰 값을 오른쪽에 옮겨나가면서 배열을 순회한다. 이때 순회의 마지막 지점에서 이루어지는 비교는 주어진 배열에서 가장 큰 값을 배열 맨 뒤에 옮겨놓는 것이 된다. 즉, 맨 마지막 요소는 정렬이 되었다고 볼 수 있으므로 맨 마지막 인덱스 직전까지 앞선 작업들을 반복해나간다. ..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 우선순위 큐를 활용하여 해결할 수 있었습니다. 문제 조건 분석 문제에서는 각 작업별로 최초 요청 시간과 작업 시간이 주어졌을 때, 각 작업별로 요청되는 시간부터 작업이 종료되는 시간(이하 '처리 시간' = 대기 시간 + 실행 시간)의 '최소' 평균을 요구하고있습니다. 이때 각 작업별 처리 시간 동안 작업의 상태를 다음과 같이 나타내볼 수 있겠습니다. 여기서 실행 시간은 고정되어있는 값으로, 각 작업별 처리 시간의 최소 평균을 구하기 위해서는 대기 상태를 최대한 줄이는 노력이 ..