뭥미

힙 정렬(Heap Sort)

힙 정렬이란? 힙 트리 구조를 이용하는 정렬 방법 힙 정렬 선행 지식: 힙 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 --> EX) 최대 힙(Max Heap), 최소 힙(Min Heap) 완전 이진트리를 표현하기 위해 배열을 사용해도 된다. 배열에서 데이터와 Index 관계가 매우 중요하다 먼저, 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용 힙 생성 알고리즘의 시간 복잡도는 O(log N) 트리를 힙 구조로 변환하는 시간 복잡도는 O(N..

퀵 정렬 (Quick Sort) - 정의

얼마나 빠르길래 이름 자체가 퀵 정렬일까? 지금까지 선택, 버블, 삽입 정렬들은 이름에서 어떻게 해결하는지 알 수 있었는데, 이건 유추가 불가능 퀵 정렬 - 피봇(Pivot)을 고르고, 피봇보다 작은 값은 피봇의 왼쪽, 큰 값을 피봇의 우측 이동해 정렬하는 알고리즘 - 분할 정복 방법 - 평균적으로 O(N*logN)을 보여주고 있으나, 최악의 경우 O(N^2)의 시간복잡도를 가짐. - 최악의 경우는 이미 정렬 되어 있는 경우를 의미. - 퀵 정렬 알고리즘은 코드를 따라가면서 직접 해보는게 좋다. - 추가로 코드를 올릴 예정

기본 정렬 비교 (1)- 선택 정렬, 버블 정렬, 삽입정렬

기본 정렬에 대해서 설명하려고 한다. 다른 부가 설명이 추가되면 좋겠지만, 직관적으로 설명하기 위해 특징만 쓴다. 소스 코드는 하나하나 다뤄보면서 업로드 할 예정이다. 1) 선택 정렬 ( Selection Sort ) - 가장 작은 값 또는 큰 값을 선택해서 차례로 앞에서부터 정렬하는 알고리즘 - O(N^2) 2) 버블 정렬 ( Bubble Sort ) - 바로 옆에 있는 데이터와 비교해서 정렬하는 알고리즘 - 그래서 계속 옆과 비교해서 거품같다해서 버블 정렬이라고 하는 것 같음. - O(N^2) --> Big-O 표기라서 선택 정렬과 다를 게 없어 보이지만, 진짜 코드를 보면 최악 그 자체 3) 삽입 정렬 ( Insertion Sort ) - 각 숫자를 적절한 위치에 삽입해 정렬하는 알고리즘 - 필요할..

힙(Heap)

처음에 공부했을 때, 그 프로세스의 메모리 구조인 힙을 생각했었다. 틀린 건 아닌데, 카테고리가 자료구조이니깐 자료구조/힙을 생각합시다. 이것 또한 면접 대비를 위해 기초 질문, 심화 질문? 점차 확장해간다. 힙(Heap) 은 완전 이진 트리 형태를 가지고 잇어야하고, 부모의 값보다 크거나 작아야하는 규칙을 가진 자료구조 그리고 영단어로는 힙은 무엇인가를 차곡차곡 쌓아올린 더미라는 뜻이다. 그래서 Max Heap, Min Heap 이 나오게되는데, 목적이 중요하다. 말 그대로 최댓값, 최솟값을 빠르게 찾기위해서 사용된다는 것을 알아두고 규칙을 이해하면 된다. 그리고, 찾아보면 단순히 최댓값또는 최솟값을 찾기 위해서라면 항상 완전 이진트리 형태일 필요는 없다고 한다. --> 아직 더 찾아봐야하는데, 사실 ..

스택과 큐

면접 대비용으로 쓰이는 것이니, 올바른 답변을 쓰도록 노력은 하고 있습니다. 그러나 올바르지 않을 경우 언제든지 댓글로 알려주시면 바로 수정하고, 다시 복습하겠습니다. --> 사실 제 블로그를 보는 사람이 없어서 아무도 피드백을 안해주는게 사실.... 스택은 후입 선출 ( 나중에 들어온 데이터가 제일 먼저 나간다 ) 특징의 자료구조 큐는 선입 선출 ( 먼저 들어온 데이터가 먼저 나간다 ) 특징의 자료구조 스택은 우리도 모르게 사용되고 있다. 재귀함수 재귀함수가 제일 나중에 호출된 데이터의 반환을 먼저하는 형식이다. 큐는 다른 알고리즘에서도 많이 쓰이지만, 대표적인 운영체제에서 사용되고 있다. 우선 순위 큐를 사용하여, 들어온 프로세스를 라운드 로빈 형식으로 처리하고 있다. 여기서 은근 운영체제 공부도 되..

배열과 연결리스트

면접 대비용으로 이 게시글을 업로드 한다. 그래서 자세한 내용은 없을 수 있다. 먼저, 정의를 내리자면, 배열은 연속된 형태의 데이터를 그 자체 메모리에 올리는 자료구조 연결리스트는 각각의 데이터를 포인터로 연결해서 공간 효율성을 극대화 시킨 자료구조 그래서 굳이 비교하자면, 배열은 순차적으로 데이터 접근이 가능하다. 즉, 인덱스를 이용해서 랜덤 액세스가 가능하다. --> 그래서 이진탐색이 배열에서 쉽게 적용됨. 그러나 배열의 끝 데이터 추가 및 삭제는 상관없으나, 중간에 데이터 추가 및 삭제는 비효율적인 처리가 발생 반대로, 연결리스트는 데이터 추가 및 삭제에 유리한 자료구조.

스택/큐 42748 K번째수

문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. a..

스택/큐 42586 기능개발

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..

스택/큐 42588문제 탑

문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 송신 탑..

스택/큐 주식가격

문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 pricesreturn [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 ..