뱀귤 블로그

문제 링크 : https://www.acmicpc.net/problem/15552

단순한 A+B 지만 빠른 입출력을 사용해야 합니다.

자바 입력에 대한 포스팅 https://bcp0109.tistory.com/37

자바 출력에 대한 포스팅 https://bcp0109.tistory.com/38

입력때 Scanner

출력때 System.out.print 

둘중 하나만 사용하더라도 시간 초과가 납니다.

입력엔 BufferedReader를 사용하고

출력엔 BufferedWriter나 StringBuilder를 사용하면 됩니다.

둘의 차이는 거의 나지 않으므로 편한걸 사용하시면 됩니다.

저는 개인적으로 BufferedReader와 비슷하게 생긴 BuffedWriter를 사용하는 편입니다.

문제 링크 : https://www.acmicpc.net/problem/2438

굉장히 간단한 별찍기 문제지만 자바의 입/출력에 따라서 성능 차이가 납니다.

System.out.print는 속도가 느리기 때문에 많은 출력이 필요할 때는 BufferedWriter나 StringBuilder를 사용하는 것이 좋습니다.

N 만큼의 줄을 먼저 for문으로 돌면서 현재 i 만큼만 별을 출력하는 2중 for문을 사용하여 해결할 수 있습니다.

문제 링크 : https://www.acmicpc.net/problem/1924

월, 일을 입력받아서 요일을 출력하는 문제입니다.

각 월의 일수를 담아놓는 month 배열을 사용하여서

현재 월 이전까지의 모든 일수를 더합니다.

예를 들어 3월이면 1월~2월까지의 일수를 더합니다.

그 후에 현재 일수만큼 더한 다음 7을 나눈 나머지를 요일로 출력해주시면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/1157

입력 받은 String 에서 가장 많이 사용되는 알파벳을 출력하는 문제입니다.

만약 가장 많이 사용된 알파벳의 수가 동일하다면 ? 을 출력합니다.

알파벳 갯수만큼 사이즈 26인 배열 arr 을 선언하여 알파벳의 갯수를 담아둡니다.

max값보다 크다면 새로운 알파벳을 answer 값에 갱신해주고 만약 max 값과 똑같다면 '?' 값을 answer에 입력합니다.

idx 값은 소문자에서 -'a' 를 해주면 인덱스만큼 구할 수 있습니다.

이후에 값을 넣을 때는 대문자로 출력해야 하기 때문에 i+65 값을 바꿔주면 됩니다.

문제 링크 : https://www.acmicpc.net/problem/9466

싸이클을 형성하지 못하는 노드 갯수를 찾는 문제입니다.

일반적인 DFS로 모든 노드를 탐색하면 시간 초과가 납니다.

테스트케이스가

2 3 4 5 1

이렇게 주어졌을 때 모든 DFS를 탐색한다면

1->2->3->4->5

2->3->4->5->1

3->4->5->1->2

4->5->1->2->3

5->1->2->3->4

O(n^2)의 시간복잡도를 갖게 되고, 최대 10만의 n 값으로 탐색한다면 시간 초과가 날 수밖에 없습니다.

따라서 이 문제의 핵심은 더이상 방문할 필요가 없는 노드를 구분해서 쓸데없는 탐색을 막는 것입니다.

그렇다면 어떻게 구분 할 것인가?

일단 이 문제는 모든 노드들은 무조건 다른 노드 한개를 가리킨다라는 조건이 있습니다.

이 말은 DFS 탐색이 끝나기 위해선 무조건 싸이클에 들어가야 한다는 뜻입니다.

예제 테스트케이스를 봐도

1->3->3

2->1->3->3

3->3

어디서 시작해도 끝은 항상 싸이클입니다.

이 점을 이용한다면 1, 2, 3 번 노드를 모두 탐색 할 필요 없이 1번 노드 탐색만으로도 싸이클을 만난다는 사실을 알 수 있습니다.

그렇다면 2번과 3번 노드는 끝까지 탐색할 필요가 없게 됩니다.

2번 노드를 탐색해서 1번 노드를 찾아 들어간다면 1번에서 탐색한 결과와 똑같이 나오기 때문에 이를 방지하여 중복을 최소화 합니다.

그래서 기본적으로 DFS 탐색에 사용되는 visited 배열 외에 finished 배열을 하나 더 만들어줍니다.

visited 배열은 단순히 방문 여부를 체크하는 것이고, finished 배열은 방문한 노드에서 싸이클을 이미 뽑아냈었는가를 확인합니다.

1->3->3

1번 노드 탐색을 할 때는 visited[3] 값이 true기 때문에 탐색이 끝납니다.

탐색의 끝은 항상 싸이클이기 때문에 3번 노드는 무조건 싸이클을 형성하는 노드 중 하나라는 사실을 알 수 있습니다.

그럼 3번 노드부터 연결된 노드를 탐색하는 for문을 통해 3번 노드와 싸이클을 이루는 노드 갯수를 카운트합니다.

이 작업이 끝나면 1번과 3번 노드는 더이상 사용할 필요가 없기 때문에 finished 값을 true로 바꿔줍니다.

2->1->3->3

2번 노드 탐색을 할 때는 1번 노드를 만납니다.

하지만 1번 노드는 이미 사용한 노드라 finished 값이 true입니다.

1번 노드와 같은 싸이클을 만날 것이기 때문에 2번 노드는 더이상 탐색을 진행하지 않고 빠져나옵니다.

같은 방식으로 모든 노드를 탐색하면 O(n)의 시간복잡도로 탐색을 끝낼 수 있습니다.

문제 링크 : https://www.acmicpc.net/problem/2075

주어진 숫자 중에서 N 번째로 큰 수를 출력하는 문제입니다.

1. 굉장히 간단하게 N*N 크기의 배열을 만들어서 수를 넣고 정렬해버리면 되긴 합니다.

<결과>

2. 하지만 시간을 좀더 줄여보기 위해 PriorityQueue를 사용할 수 있습니다.

우선순위 큐는 아시다싶이 일반 큐와 달리 우선순위를 비교해서 자동으로 정렬이 되는 자료구조입니다.

정렬 조건을 직접 설정할 수도 있고, 기본적으로 Integer 형으로 선언 하면 작은 수가 제일 먼저 pop 됩니다.

우선순위큐의 사이즈를 N 만큼 유지하면서 삽입/삭제를 반복하면 마지막에 남는 peek() 값이 N 번째로 큰 수가 됩니다.

<결과>

생각보다 속도가 많이 줄지는 않았습니다.

3. 조금이라도 더 줄여보기 위해 peek과 비교하는 작업을 추가합니다.

<결과>

문제 링크 : https://www.acmicpc.net/problem/1005

건물의 빌드 순서를 정해줄 때 특정 건물을 짓기 위해 총 소요되는 시간을 구하는 문제입니다.

DFS로 해당 건물에 도달하기 위한 모든 경우를 탐색하는 방법도 있지만

방향을 갖고 사이클이 없다는 DAG 특성을 이용하여 위상 정렬을 사용하였습니다.

위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21

일반적인 위상정렬과 다른 점은 노드의 순서가 아니라 소요 시간을 기억해야한다는 점입니다.

result 배열을 따로 만들어서 총 소요시간을 저장해둡니다.

1. 처음 indegree 가 0 인 건물들은 이전 테크가 없기 때문에 총 소요시간이 d[i] 입니다.

2. Queue에서 건물을 빼면서 해당 건물과 연결된 다른 건물들의 result 를 갱신해줍니다.

3. 이전까지의 소요시간 result[node] + 현재 건물의 소요시간 d[i] 로 이루어지며 이전 테크가 전부 올라가야 현재 건물을 지을 수 있기 때문에 가장 오래 걸리는 시간으로 갱신해줍니다.

문제 링크 : https://www.acmicpc.net/problem/1766

문제를 푸는 순서를 정해야 합니다.

문제를 효율적으로 풀기 위해서 선수 문제가 필요한 문제는 무조건 순서에 맞춰서 풉니다.

이 문제는 위상 정렬을 사용하면 쉽게 해결할 수 있습니다.

위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21

한가지 다른 점은 원래 위상 정렬은 결과값이 하나가 아닙니다.

간선에 따라서 여러 결과가 나오기도 하는데 이 문제는 무조건 숫자가 낮은 문제를 먼저 풀어야 한다고 딱 정했습니다.

그래서 위상 정렬을 구현할 때 일반 큐 대신에 우선순위 큐(PriorityQueue)를 사용합니다.