[Data Structure] 우선순위 큐와 힙(Priority Queue and Heap) 이해하기

인트로 본 포스팅을 이해하기 위해선 힙 자료구조 배경지식이 필요합니다. 본 포스팅은 1)우선순위 큐 설명 2)우선순위 큐와 힙의 관계 3)구현 코드로 구성되어 있습니다. 우선순위 큐란? 큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In First Out, FIFO) 구조의 자료구조를 말한다. 우선순위 큐(Priority Queue)는 일반 큐와 이름은 비슷하지만 동작하는 방식이 다르다. 우선순위 큐의 각 원소(데이터)는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다. 우선순위 큐와 힙 (우선순위 큐 ≠ 힙) 당신에게 음료수 자판기를 만들라는 과제가 주어졌다. 당신은 자판기를 만들기 위한 고민을 하기 시작할 ..

• format_list_bulleted Data structure
• · 2021. 9. 2.
• textsms

[C, C++] 배열(Array)은 포인터(Pointer)가 아니다!

인트로 배열을 포인터라고 알고 있거나 배열의 이름이 포인터 내지는 포인터 상수라고 알고 있는 경우가 많다. 하지만 놀랍게도 배열은 포인터가 아니다! 배열은 배열이고 포인터는 포인터일 뿐이다. 다만 대부분의 코드에서 배열의 이름이 포인터로 변환되기에 배열의 이름 = 포인터라고 알고 있는 것 같다. 배열을 포인터로 나타낼 수 있는 이유는 C와 C++의 암시적인 변환(Decay) 정책에 의해 가능한 일이다. Decay란? 암시적으로 배열이 포인터로 변환하는 과정에서 배열의 타입과 크기를 잃어버리는 것을 Decay라고 한다. 본 포스팅에선 Decay를 "변환"이란 단어로 대체했다. 배열과 포인터 여기 배열이 하나 있다. int arr[3]; arr은 3개의 Integer를 담을 수 있는 메모리 공간이 있다. 그..

• format_list_bulleted C++
• · 2021. 8. 26.
• textsms

[Algorithm] 버블 정렬(Bubble Sort) 코드와 시간 복잡도

인트로 기초 정렬 알고리즘인 버블 정렬(Bubble Sort)과 시간 복잡도를 알아보자 참고로 성능이 좋지 못해 버블 정렬이 사용될 일은 극히 드물다. 버블 정렬 활용 문제는 다음 포스팅을 참고하세요. [Algorithm] level0 : Special Sort(구글 인터뷰) [Algorithm] level0 : Special Sort(구글 인터뷰) 인트로 정렬을 알고리즘을 적용하는 문제이다. 어떤 정렬을 사용할진 문제를 읽어보고 고민하길 바란다. Special Sort(구글 인터뷰) 문제 N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한 kangworld.tistory.com 버블 정렬(Bubble Sort) : 개념 [ Cycle 1 ] 1. 배열의 "0"번 원소와 "1"번 원소를 비교해서 대소..

• format_list_bulleted Algorithm/정렬
• · 2021. 8. 19.
• textsms

[Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘

인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한다. 그래프라는 건 추상적인 개념이다. 0번 정점과 1번 정점이 연결되어 있다는 정보만 있을 뿐 실질적으로 그래프를 구현하는 자료구조는 배열이 될 수도 리스트가 될 수도 벡터가 될 수 있다. 어떤 자료구조를 사용할진 개발자의 선택이다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 구현하는 간단한 코드를 소개하려 한다. 결론부터 말하면 재귀 함수를 사용해 DFS를 구현했다. BFS가 궁금하다면? [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 인트로 ..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 17.
• textsms

[Algorithm] 24. Jolly Jumpers

인트로 재밌는 문제라고 생각해서 기록하려 한다. Jolly Jumper를 구하는 문제이다. Jolly Jumper의 정의는 다음과 같다. Jolly Jumper : N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지는 수열 Jolly Jumper 문제 N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지면 그 수열을 유쾌한 점퍼(jolly jumper)라고 부른다. 예를 들어 다음과 같은 수열에 서 1 4 2 3 앞 뒤에 있는 숫자 차의 절대 값이 각각 3 ,2, 1이므로 이 수열은 유쾌한 점퍼가 된다. 어떤 수열이 유쾌한 점퍼인지 판단할 수 있는 프로그램을 작성하라. ※ 입력설명 첫 번째 줄에 자연수 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 6.
• textsms