본문 바로가기

Thinking87

Sort 계수 정렬 (Counting Sort) 알고리즘 [Sort] 계수 정렬 (Counting Sort) 알고리즘 계수 정렬은 데이터의 키에 따라 객체를 수집 정렬 하는 정렬 알고리즘이다.비교 연산을 하지 않는 정렬 알고리즘이다.키의 다양성이 데이터의 수보다 상당히 크지 않은 상황에서 유용하다.O(n)의 시간 복잡도를 가진다.데이터 중 가장 작은 값과 가장 큰 값을 기준으로 하는 공간 크기가 필요하다. (1~10의 경우 10개의 공간이 필요하지만 1과 10000이 들어 있는 데이터에서는 10000의 배열 크기가 필요하다.)특정한 값이 몇번 등장했는지에 따라 정렬을 수행한다.계수를 다 카운팅 한 후에 앞에서 부터 차례대로 배열에 넣는다. 정렬 과정10000개의 공간에 1 ~ 10까지의 정수가 무작위로 들어가 있다고 가정한다.최솟값 최댓값을 알고 있을 때, 각.. 2023. 10. 1.

Sort 기수 정렬 (Radix Sort) 알고리즘 [Sort] 기수 정렬 (Radix Sort) 알고리즘 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.공간을 나눠 알맞은 데이터를 놓는 방법이 버킷 정렬 (Bucket Sort)과 비슷하다.* 버킷 소트(bucket sort)는 배열의 원소를 여러 버킷으로 분산하여 작동하는 정렬 알고리즘이다. 특징데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬을 진행하는 방식이다.비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘이다. 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다.전체 데이터의 기수를 위한 버킷이라는 추가적인 메모리 공간이 필요하다. 10 진수인 데이터들을 정렬하기 위해서는 0~9 를 저장할 10.. 2023. 10. 1.

스털링 근사 (Stirling's approximation) 스털링 근사 (Stirling's approximation) 수학에서 스털링 근사(영어: Stirling’s approximation) 또는 스털링 공식(영어: Stirling’s formula)은 큰 계승을 구하는 근사법이다. 나아가 실수와 복소수까지 확장시켜 감마 함수에 대한 근삿값을 구할 수 있도록 한다. 계승(팩토리얼: factorial)이란 기호로 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다. 일반적으로 확률과 통계, 수학 과목에서는 n! = 1×2×3×⋯⋯×(n−1)×n 으로 배운다. (n부터 1씩 빼면서 곱하는 것) 아래 표는 20까지의 팩토리얼 값을 정리한 것이다. 이처럼 n이 커질 수록 해당 값이 기하급수적으로 증가하게 되는데 이 때 스털링의 근사식을 응용.. 2023. 10. 1.

C++ 프로그래머스 Lv5 집합과 쿼리 [C++] 프로그래머스 Lv5 집합과 쿼리 2023년 현대모비스 알고리즘 경진대회 예선 문제이다.본 게시글의 풀이는 58.3점으로 해결하지 못한 문제로 남아있다. 문제 설명정수 0 ~ n-1을 담고 있는 크기가 n인 1차원 정수 배열 a가 있습니다. 배열의 각 원소마다 하나의 집합을 이루고 있습니다. 당신은 여기에 다음 쿼리들을 실행하려고 합니다. [1, x, y] 형태의 쿼리가 주어집니다.y가 포함된 집합의 원소들을 모두 x가 포함된 집합으로 옮깁니다.x와 y가 같은 집합에 속해있다면 해당 쿼리는 실행하지 않습니다.[2, x, y] 형태의 쿼리가 주어집니다.새로운 집합을 생성합니다.x와 y가 포함된 집합에서 x와 같거나 늦게 집합으로 들어왔으면서 y와 같거나 빠르게 집합으로 들어온 원소들을 새로 생성한.. 2023. 9. 22.

자료구조 트리(Tree) 구조 [자료구조] 트리(Tree) 구조 개념자료구조 Tree는 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아서 트리 구조라고 부른다.자료구조 Tree는 그래프의 여러 구조 중 무방향 그래프의 한 구조이다.트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.트리 구조는 데이터를 순차적으로 나열시킨 선형 구조가 아니라,하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.트리 구조는 루트라는 하나의 꼭짓점 데이터를 시작으로, 여러 개의 데이터를 간선으로 연결한다.트리 구조는 각 데이터를 노드라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가.. 2023. 9. 22.

Sort 힙 정렬(Heap Sort) 알고리즘 [Sort] 힙 정렬(Heap Sort) 알고리즘 힙(Heap)이란?힙이란 완전 이진 트리의 형태로 만들어진 자료구조이다.돌 더미, 장작 더미 처럼 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다. 완전 이진 트리(Complete Binary Tree)란?완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 가지고 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있는 자료구조이다. 최하단 레벨의 노드는 좌측 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 한다. 힙 정렬(Heap Sort)이란 ?힙 정렬(Heap sort)이란 최대 힙(부모 노드 > 자식 노드) 트리나 최소 힙(부모 노드 트리를 구성해 정렬을 하는 방법이다.힙(.. 2023. 9. 19.

C++ BAEKJOON 28278번 : 스택2 [C++] BAEKJOON 28278번 : 스택2 시간 제한메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초1024 MB67742693225940.622%문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.3: 스택에 들어있는 정수의 개수를 출력한다.4: 스택이 비어있으면 1, 아니면 0을 출력한다.5: 스택에 정수가 있다면 맨 .. 2023. 9. 18.

C++ 프로그래머스 Lv3 하노이의 탑 [C++] 프로그래머스 Lv3 하노이의 탑 문제 설명하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로.. 2023. 9. 16.

C++ 프로그래머스 Lv1 추억 점수 [C++] 프로그래머스 Lv1 추억 점수 문제 설명사진들을 보며 추억에 젖어 있던 루는 사진별로 추억 점수를 매길려고 합니다. 사진 속에 나오는 인물의 그리움 점수를 모두 합산한 값이 해당 사진의 추억 점수가 됩니다. 예를 들어 사진 속 인물의 이름이 ["may", "kein", "kain"]이고 각 인물의 그리움 점수가 [5점, 10점, 1점]일 때 해당 사진의 추억 점수는 16(5 + 10 + 1)점이 됩니다. 다른 사진 속 인물의 이름이 ["kali", "mari", "don", "tony"]이고 ["kali", "mari", "don"]의 그리움 점수가 각각 [11점, 1점, 55점]]이고, "tony"는 그리움 점수가 없을 때, 이 사진의 추억 점수는 3명의 그리움 점수를 합한 67(11 + 1.. 2023. 9. 15.

C++ 프로그래머스 Lv3 연속 펄스 부분 수열의 합 [C++] 프로그래머스 Lv3 연속 펄스 부분 수열의 합 문제 설명어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다. 예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다. 정수 수열 seq.. 2023. 9. 15.

C++ 프로그래머스 Lv2 디펜스 게임 [C++] 프로그래머스 Lv2 디펜스 게임문제 설명준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다. 준호는 처음에 병사 n명을 가지고 있습니다. 매 라운드마다 enemy[i]마리의 적이 등장합니다. 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다. 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다. 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다. 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격.. 2023. 9. 15.

C++ 프로그래머스 Lv2 요격 시스템 [C++] 프로그래머스 Lv2 요격 시스템 문제 설명A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에.. 2023. 9. 15.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바