코딩일지

- 구상 문제를 푸는 방법은 다양할 듯 하다. 여러 경우를 모두 시행해보고, 최솟값을 찾을 수도 있을 듯 하고(이 방법으로 처음 생각했었는데, 시간 초과가 떠서 실패했다), 원하는 결과를 만족시키는 특정 조건에 따라 작업을 수행해도 될 것 같다. 후자는 그리디 알고리즘(Greedy Algorithm)이라는 방식으로, 이 문제가 이 파트에 속해있다. 그래서 그리디 알고리즘으로 풀어볼 것이다. ➡ 먼저 그리디 알고리즘(Greedy Algorithm)이 무엇인지 생각해보자. ➡ ChatGpt에게 물어보니, 다음과 같은 설명을 해주었다. 그리고 내가 문제 풀며(푼 게 얼마 없긴 한디), 느낀 바로는, 그리디 알고리즘이란 사람이 머리를 엄청 써서 굉장히 간단히 풀 수 있는 방식이다. ➡ 즉 사람에 대한 의존이 심..

카테고리 없음 2023. 8. 18. 22:04

- 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net - 구상 사실 최소를 찾기만 하면 되기에, 결과론적으로 생각하면 편하다. ➡어찌됐건 총 기다린 시간을 생각해보면, 1번째로 수행한 사람의 시간은 N번 반복해서 더해질 것이고, 2번째로 수행한 사람의 시간은 N-1번 반복해서 더해질 것이고, ... N번째로 수행한 사람의 시간은 뒤에 사람이 더 없으니, 1번만 더해질 것이다. ➡ 이 점을 이용해서 돈을 인출하는 데에 가장 적은 시간이 걸리는 사람을 첫번째로, 가장 많은 ..

카테고리 없음 2023. 8. 18. 21:34

- 문제 https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net - 구상 이해만 하면 쉬운데 이해가 어렵다. 문제를 꼭 꼼꼼히 읽고, 다음 사고과정을 따라가자. ➡ 먼저 stack의 특성상, push()한 값을 바로 pop()하면 그대로 나오므로, 사실상 stack인 부분들은 없다고 생각해도 된다. 그리고 나머지는 queue이므로, 하나의 queue가 해당 위치의 값들로..

카테고리 없음 2023. 8. 15. 17:34

Def : "Doulbe-Ended Queue"라는 의미로, 큐와 비슷하나, 삽입과 삭제 부분이 정해진 queue와 달리, 양 방향으로 삽입 삭제가 가능해진 구조이다. 시내버스같은 구조로, 사람들이 많으면 버스도 앞문 뒷문 구분 없이 막 내리지 않는가. 그와 비슷한 것 같다. deck(갑판)이 아니다. Functions to use : push_front, push_back, empty, front, back, size etc. push_back(x) : 덱의 가장 윗 데이터에 메모리를 생성, 데이터 x를 넣는다. push_front(x) : 덱의 가장 아래 데이터에 메모리를 생성, 데이터 x를 넣는다. pop_back() : 덱의 가장 마지막에(최근에) 입력된 데이터를 삭제한다. 덱가 비었다면 연산 정..

카테고리 없음 2023. 8. 15. 17:20

- 큐(queue) Def : 대기줄이라는 영어 뜻 그대로, 뒤에서 value가 추가되고, 앞에서 사라지는 구조이다. 가장 처음으로 넣은 값(First In)이 가장 처음으로 빠진다(First Out)는 의미에서, FIFO구조(First In First Out)라고 불린다. Functions to use : push, pop, empty, front, back, size etc. push(x) : 큐의 가장 윗 데이터에 메모리를 생성, 데이터 x를 넣는다. pop() : 큐의 가장 처음에(오래 전에) 입력된 데이터를 삭제한다. 큐가 비었다면 연산 정의 불가상태(error 발생)가 된다. empty() : 큐가 비었다면 1을 return하고, 그렇지 않다면 0을 반환한다. front() : 큐의 가장 처음..

카테고리 없음 2023. 8. 14. 17:21

문제 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이..

카테고리 없음 2023. 8. 9. 00:10

- 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. - 입력 첫 줄에 n (1 ≤ n ≤ 100,000)..

카테고리 없음 2023. 7. 29. 23:56

- 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에..

카테고리 없음 2023. 7. 27. 18:40