가치투자자

백준 24060번 : 병합 정렬1 🔗 문제 링크 https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 🎯 풀이를 위한 개념 설명 병합 정렬에 대한 이해가 있어야 풀 수 있는 문제이다. 쉽게 설명을 하자면, 병합 정렬은 입력된 배열을 크기가 1인 부분 배열로 쪼갠 다음, 각 부분 배열의 인덱스 0번째 값을 비교하여 작은 값부터 빈 배열에 넣어 정렬하는 알고리즘이다. 병합 정렬에 대해 더 자세한 설명은 아..

병합 정렬 (merge sort) 1. 병합 정렬이란? 병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다. 병합 정렬 알고리즘은 다음 개념들을 바탕으로 진행된다. 분할(Divide) : 입력된 배열을 같은 크기의 부분 배열 2개로 분할한다. 정복(Conquer) : 부분 배열의 크기가 충분히 작지 않으면(리스트의 길이가 0 또는 1이 아니면) 다시 분할을 한다. 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다. 병합 정렬은 다음 단계들로 진행된다. 부분 배열의 요소들을 결합할 빈 배열이 필요하다. 부분 배열의 크기(length)가 1이 될 때까지 쪼개준다. 부분 배열의 0번째..

백준 2164번 : 카드2 🔗 문제 링크 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 💬 문제 큐(queue) 에 대한 이해가 있다면 더 잘 이해할 수 있고, 큐를 몰라도 쉽게 이해할 수 있는 문제이다. 숫자 N이 주어지므로 1부터 N까지 담고 있는 배열을 생성해준다. 맨 위에 있는 수, 즉 배열 첫 번째 요소를 제거(shift)해준다. 그 다음 위에 있는 수를 빼서(shift) 맨 밑으로 옮겨준다(push). 그리고 단 1장의 숫자가 남을..

연결리스트 (Linked List) 큐(queue)에 해당하는 알고리즘 문제를 풀다가 시간 복잡도 문제를 해결하기 위해 연결리스트에 대해 공부해보았다. 1. 연결리스트란? 연결리스트(Linked List) 는 index 번호를 사용하는 배열과 달리 연결(link)을 이용해 구현한 리스트를 말한다. 배열의 경우엔 아래처럼 index 번호로 값을 알 수 있다. 즉, index 번호와 값이 서로 연결되어 있다. const arr = ['a', 'b', 'c']; console.log(arr[1]) // index 1번의 값은 b 하지만 연결리스트는 각각의 값들이 서로 연결되어 있다. 아래의 사진을 보면, 10이라는 값에는 10이라는 data뿐만 아니라 10과 연결된 20의 주소(Link)까지도 담고 있다. 이..

스택(stack)과 큐(queue) 스택과 큐. 처음 들었을 땐 어려울 수 있지만, 쉽게 설명해보고자 한다. 1. 스택 (Stack) 스택(stack) 은 데이터를 아래에서 위로 쌓아올리는 구조를 말한다. 이때 데이터를 추가하거나 제거할 때 위에서부터 추가/삭제해야 하며, 이러한 자료구조를 LIFO(후입선출, Last-in, First-out)이라고 한다. 예로는 다음과 같은 것이 있을 수 있다. 브라우저창에서 뒤로가기 새로운 주소에 접속하면 그 방문기록이 히스토리 스택 아래에서부터 쌓일거고, 뒤로 돌아간다는건 맨 위에 쌓인 방문기록에서 아래로 돌아가는 것 Ctrl+Z로 실행 취소하여 직전 상태로 되돌아가기 역순 문자열 만들기 가장 마지막에 입력된 문자부터 출력하기 때문 수식의 괄호 검사 연산자 우선순위..

백준 10773번 : 제로 🔗 문제 링크 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 💬 문제 스택(stack) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다. 1. 빈 배열인 스택(stack)을 만들어준다. 2. 재현이가 올바른 수를 부를 경우, stack에 그 수를 넣어준다(push). 3. 재현이가 잘못된 수를 부른 다음 0을 말하므로, 0이 나올때마다 stack에서 이전 수를 빼준다(pop). ..