본문 바로가기

Programming

 (110)
[백준 13164번] 행복 유치원 link : https://www.acmicpc.net/problem/13164행복 유치원 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB37623718163.066%문제행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양..
그리디 알고리즘(Greedy Algorithm) 1. 개념 그리디 알고리즘이란 "매 선택에서 당장의 최적 답을 선택해 적합한 결과를 도출하는" 알고리즘이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에는 최적이지만 그것을 종합적으로 봤을때에는 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 2. 적용 그리디 알고리즘은 한 번의 선택이 다음 선택에는 전혀 무관해야하며, 매 순간 최적해가 문제의 답인 경우에 사용한다. 3. 추가 그리디 알고리즘은 동적 프로그래밍이 너무 많은 일을 하기 때문에 그를 도와주기 위해 착안된 알고리즘이다. 동적 프로그래밍을 대체하는 것이 아니고 보완하는 개념이다. [예제 : http://gyutts.tistory.com/53]
[백준 1826번] 연료 채우기 link : https://www.acmicpc.net/problem/1826연료 채우기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB88319714525.261%문제성경이는 트럭을 정글 속에서 운전하다가 트럭의 연료탱크에 갑자기 구멍이 나서 1km를 가는데 1L의 연료가 새 나가게 되었다. 이것을 고치기 위해서는 가장 가까운 마을에 가야 한다. 그런데 그냥 가다가는 중간에 연료가 다 빠질 수가 있다. 다행스럽게도 정글 곳곳에 연료를 채울 수 있는 주유소가 N개 있다. 그런데 정글 속에서 중간에 차를 멈추는 행위는 매우 위험한 행위이므로 주유소에서 멈추는 횟수를 최소화 하려 한다.그리고 다행이도 성경이의 트럭은 매우 좋아서 연료 탱크에는 연료의 제한이 없이 많이 충분히 많이 넣을 수 ..
Heap(힙) & Priority Queue(우선순위 큐) 힙(Heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. ::A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다:: 힙에는 두 가지 종류가 있으며 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만..
[백준 9935번] 문자열 폭팔 link : https://www.acmicpc.net/problem/9935문자열 폭발 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초 (언어별 추가 시간 없음)128 MB105591699114918.858%문제상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.폭발은 다음과 같은 과정으로 진행된다.문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한..
[백준 9627번] 문장 link : https://www.acmicpc.net/problem/9627문장 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB2531116139.610%문제옛날 옛적에 수학을 공부하는 사람들만 사는 나라가 있었다. 이 나라에 살고있는 상근이와 창영이는 자명한 문장에 대해서 토론을 하고 있었다.자명한 문장에는 숫자를 하나만 포함하고 있으며, 그 숫자는 문장을 이루는 글자의 개수와 같다. 예를 들면, "This sentence has thirtyone letters.”, “Blah blah seventeen”과 같다.상근이는 창영이에게 자명한 문장에서 숫자만 지운 문장을 주었다. 창영이는 가장 작은 수를 문장에 넣어 올바른 자명한 문장을 만드는 프로그램을 작성하려고 한다.문장은 ..
[백준 7785번] 회사에 있는 사람 link : https://www.acmicpc.net/problem/7785회사에 있는 사람 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB322297970440.553%문제상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.입력첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진..
[백준 3190번] 뱀 link : https://www.acmicpc.net/problem/3190뱀 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB99032218152321.832%문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 이동한 칸에..

티스토리툴바