전체 글
-
백준(BOJ) 1966번 프린터 큐알고리즘 풀이/백준(Boj) 2019. 7. 30. 19:27
문제 : https://www.acmicpc.net/problem/1966 문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.예를 ..
-
백준(BOJ) 11051번 이항 계수 2알고리즘 풀이/백준(Boj) 2019. 7. 30. 01:27
문제 : https://www.acmicpc.net/problem/11051 문제자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 나의 풀이: 이항계수(N, K) 를 구하는 방법은 (N-1, K-1) + (N-1, K) 이고 재귀적으로 호출해주면 된다. 하지만 N이 1000이기에 시간내에 풀기에는 불가능하다. ex ) 이항계수(5, 2)를 예로 이항계수(4,1) 부터 쭉 재귀적으로 내려가서 답을 구한 다고 가정하면 또 (4,2)를 구할 때에도 (3,1), (2,1) 등 구한 값을 다시 구해야 한다. 따라서 중복이 되는 경우는 메모이제이션을 통하여 중복을 제거 해주어야 한다. 코드 ( C++ ) #include #include using n..
-
백준(BOJ) 1507번 궁금한 민호알고리즘 풀이/백준(Boj) 2019. 7. 29. 17:12
문제 : https://www.acmicpc.net/problem/1507 문제강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다...
-
문제 09 -1 우선순위 큐의 활용Data Structure/윤성우의 열혈 자료구조 2019. 7. 29. 03:50
// UsefulHeap.h #pragma once #define TRUE1#define FALSE0 #define HEAP_LEN100 // typedef char HData;typedef char * HData;typedef int PriorityComp(HData d1, HData d2); typedef struct _heap{PriorityComp * comp;int numOfData;HData heapArr[HEAP_LEN];} Heap; void HeapInit(Heap * ph, PriorityComp pc);int HIsEmpty(Heap * ph); void HInsert(Heap * ph, HData data);HData HDelete(Heap * ph); //UsefulHeap.c #..
-
백준(BOJ) 2884번 알람 시계알고리즘 풀이/백준(Boj) 2019. 7. 29. 03:11
문제 : https://www.acmicpc.net/problem/2884 문제상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.바로 "45분 일찍 알람 맞추기"이다.이 방법은 단순하다. 원래 맞춰져있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.현재 상근이가 맞춰논 알람 시..
-
백준(BOJ) 1436번 영화감독 숌알고리즘 풀이/백준(Boj) 2019. 7. 29. 01:00
문제 : https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다..
-
백준(BOJ) 2750번 수 정렬하기알고리즘 풀이/백준(Boj) 2019. 7. 26. 16:39
문제 : https://www.acmicpc.net/problem/2750 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 나의풀이 : N이 최대 1000이니 삽입정렬의 시간복잡도(N^2)로도 충분히 가능하기에 삽입정렬로 풀이 하였다. 삽입정렬은 필요한 만큼만 정렬을 할 수 있기에N^2의 복잡도중 가장 효율이 좋다. 사실 이 문제는 c++ stl algorithm에 std::sort 로 간단히 해결 가능하다. std:sort는 quicksort를 기반으로 구현되며 nlgn 에 복잡도를 보장하기 때문에 가능하다. 코드 ( C ++ ) #include #include using namespace std;int N;const int MAX = 1000;int arr[MAX]; ..
-
소풍알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 26. 03:33
문제 : https://algospot.com/judge/problem/read/PICNIC 문제안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.(태연,제시카) (써니,티파니) (효연,유리)(태연,제시카) ..