본문 바로가기

프로그래밍/Algorithm109

힙(Heap) vs 이진 탐색 트리(Binary Search Tree) 힙(Heap)이란?힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조로서, 힙에 데이터를 저장해 놓으면 O(1), 즉 상수 시간에 최솟값이나 최댓값에 접근할 수 있다. 이것이 가능한 이유는 힙이 최솟값 또는 최댓값을 트리의 루트(root)에 저장해 놓기 때문이다. 보통, 최솟값을 트리의 루트에 위치시키는 힙을 최소 힙(Min Heap)이라고 하고, 최댓값을 트리의 루트에 위치시키는 힙을 최대 힙(Max Heap)이라고 한다.  힙에서 값을 연속해서 꺼내면 자동으로 정렬되는 효과가 나기 때문에 기본적으로 정렬에 활용할 수 있다. 몇 번째로 가장 작은 값 또는 가장 큰 값을 구해야 하는 상황에서도 유용하게 사용할 수 있다. 예를 들어, 3번째로 작은 값이 필요하다.. 2023. 10. 4.
[프로그래머스 Programmers] 피자 나눠 먹기(2) 문제 설명 머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요. 제한 사항 1 ≤ n ≤ 100 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; public class Solution { public int solution(int n) { var r = lcm(n, 6); var answer = r / .. 2023. 9. 27.
[프로그래머스 Programmers] 옷가게 할인 받기 문제 설명 머쓱이네 옷가게는 10만 원 이상 사면 5%, 30만 원 이상 사면 10%, 50만 원 이상 사면 20%를 할인해줍니다. 구매한 옷의 가격 price가 주어질 때, 지불해야 할 금액을 return 하도록 solution 함수를 완성해보세요. 제한사항 10 ≤ price ≤ 1,000,000 price는 10원 단위로(1의 자리가 0) 주어집니다. 소수점 이하를 버린 정수를 return합니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; using System.Collections.Generic; using .. 2023. 9. 27.
해시 테이블(Hash Table)에 대해서 해시 테이블이란?해시 테이블(hash table)은 키(key)와 값(value)으로 이루어진 여러 쌍의 데이터를 저장할 수 있는 자료구조(Data Structure)이다. 키를 알고 있으면 'O(1)', 즉 상수 시간에 값을 접근 할 수 있으며 데이터 검색을 최적화하기 위해서 많이 사용한다. 해시 테이블은 프로그래밍 언어마다 약간씩 다른 이름으로 불리고 있어서 헷갈릴 수 있는데대표적으로 C#에서는 사전(Dictionary)가 해시 테이블의 역할을 담당하고, C++에서는 맵(map)이 같은 역할을 한다.자바에서는 'HashTable' 또는 'HashMap'이 해시 테이블에 해당하는 내장 자료형이다. 해시 테이블은 내부적으로 각 키가 값을 가르키는 구조로 되어 있기때문에 값에 접근하든 추가하든 갱신하든 삭.. 2023. 9. 27.
[프로그래머스 Programmers] 삼각 달팽이 문제 설명 정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요. 제한 사항 n은 1 이상 1,000 이하입니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 코드 using System; using System.Collections.Generic; public class Solution { public int[] solution(int .. 2023. 9. 21.
배열(Array)에 대해서 순서 있게 값을 저장 배열의 가장 중요한 특징은 값을 인덱스(index)를 사용하여 순서 있게 저장한다는 것이다. 그래서 이 인덱스를 통해서 특정 위치에 저장되어 있는 값을 상수 시간(O(1))에 읽고 쓸 수 있다. 예를 들어, 다음과 같은 형태로 값이 저장되어 있는 배열 'arr'가 있을 때, value: A B C D E F G H I J index: 0 1 2 3 4 5 6 7 8 9 인덱스 3에 있는 값을 'D'에서 'K'로 변경해 보겠습니다. print(arr[3]) # 'D' arr[3] = 'K' # 인덱스 3에 있는 값을 'D'에서 'K'로 변경 print(arr[3]) # 'K' 이와 같이 대부분 프로그래밍 언어에서는 배열이 가리키고 있는 변수명 뒤에 대괄호를 붙여서 'arr [i]'와 .. 2023. 9. 20.

티스토리툴바