알고리즘 풀이/정렬
-
백준 1005번 ACM Craft :: 마이구미알고리즘 풀이/정렬 2017. 7. 2. 23:06
이번 글은 백준 알고리즘 문제 1005번 "ACM Craft" 를 다뤄본다.문제 번호를 보다시피, 오래된 문제로 제출량이 만건이 넘은 문제이다.정답률이 17%밖에 안되지만, 어려운 문제가 아닌, 쉬운 문제로 속한다.1년 전 풀었지만, 재채점으로 인해 런타임에러가 떴기에, 복습 겸 다시 풀어보았다.문제 풀이의 접근은 위상 정렬을 활용한다. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 ..
-
백준 1015번 수열 정렬 :: 마이구미알고리즘 풀이/정렬 2017. 2. 7. 01:05
이번 글은 백준 알고리즘 1015번 "수열 정렬" 을 다뤄본다.문제 이름을 보다시피 정렬 관련 문제다. P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 문제의 키워드는 비내림차순과 사전순으로 볼 수 있다.문제를 해결하기 위해 수열 P를 구해보자. 적용하는 방법으로 나와있는 B..
-
백준 1377번 버블 소트:: 마이구미알고리즘 풀이/정렬 2016. 12. 28. 22:52
이번 글은 백준 알고리즘 사이트의 1377번 "버블 소트" 를 다뤄본다.정답률은 20% 대로, 200명정도이다.1377번 버블 소트 - https://www.acmicpc.net/problem/1377 이미 문제에서도 버블 소트의 소스를 보여줬다.출력되는 정답이 의미하는 건 버블 정렬이 몇단계를 거쳤는지를 알아내는 것이다.버블 정렬을 잠깐 살펴보자. (기본적으로 버블 정렬을 숙지하고 있다고 가정하겠다.)다음과 같이 주졌다고 하자. (10 4 2 5 9 1)10 4 2 5 9 1 -> 4 10 2 5 9 1 -> 4 2 10 5 9 1 -> 4 2 5 10 9 1 -> 4 2 5 9 10 1 -> 4 2 5 9 1 10위의 경우가 1단계라고 하자.그렇다면 다음이 2단계라고 할 수 있다.4 2 5 9 1 1..
-
백준 11650번 좌표 정렬하기 :: 마이구미알고리즘 풀이/정렬 2016. 10. 19. 00:45
이번 글은 백준 11650번 좌표 정렬하기 문제를 다룰 것이다.문제는 간단하다.백준 11650번 좌표 정렬하기https://www.acmicpc.net/problem/11650백준 11650번 좌표 정렬하기 2https://www.acmicpc.net/problem/11651 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 문제에 보다시피 정렬하는 문제이다. 1차원적인 문제라면 정렬 문제는 정말 쉽다. 본인의 경우는 큰 어려움이 없는 한 Arrays.sort()를 통해 처리한다. 하지만 이렇게 2개 이상의 기준을 가진다면 조금 까다롭게 느껴진다. 이전 글에서도 정렬 문제를 다룬 적이 2번 있다...