C++
-
백준(BOJ) 10989번 수 정렬하기 3알고리즘 풀이/백준(Boj) 2019. 7. 31. 15:03
문제: https://www.acmicpc.net/problem/10989 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 나의 풀이: 시간복잡도 N을 요구하고 범위가 1~10000으로 정해져 있으니 기수 정렬을 통하여 크기를 기준으로 개수를 세주면 된다. printf와 scanf로 입력을 받아줘서 시간을 줄이자 코드 ( C++ ) #include using namespace std; int mycount[10000];int N;int main(){ scanf("%d", &N);for (int i = 0; i < N; ++i){int num;scanf("%d", &num);// 0부터 시작이므로 num-1 인덱스를 1 추가 한다.mycount[num-1]++;}for (i..
-
백준(BOJ) 1431번 시리얼 번호알고리즘 풀이/백준(Boj) 2019. 7. 31. 14:32
문제 : https://www.acmicpc.net/problem/1431 문제다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.A와 B의 길이가 다르면, 짧은 것이 먼저 온다.만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 ..
-
백준(BOJ) 1181번 단어 정렬알고리즘 풀이/백준(Boj) 2019. 7. 31. 13:38
문제: https://www.acmicpc.net/problem/1181 문제알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터길이가 같으면 사전 순으로 나의풀이 : 1. string 배열을 만들어 담는다2. size를 기준으로 정렬 한다 + 길이가 같을시 사전순으로 정렬 compare 만든다.3. unique를 통해 중복을 제거 해준다. unique에 관한 설명은 www.cppreference.com에 가셔서 검색하시면 보다 자세히 알 수 있습니다. cppreference.com 코드 ( C++ ) #include #include #include #include using namespace std; int N;bool compare..
-
백준(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를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다...
-
백준(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개이상 연속으로 들어가는 수를 말한다..