Algorithm/BaekJoon

[백준] 1563번: 개근상(Java)

Notion에 정리한 글을 옮긴 것입니다. 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 문제 풀이 완전탐색을 이용해야하지만, 완전탐색만 사용한다면 경우의 수가 O(3^1000)의 시간복잡도가 발생한다. 그래서 재귀적 접근(DFS) + dp ⇒ dp의 bottom-up방식을 사용하여 풀었다. 이 문제의 핵심은 점화식을 찾는 것인데, 간단한 예를 통해 알아보자. 한 학기를 3일이라고 하자. 지각(late)는 2일 이상이면 안되고, 결석(absent)은 연속 3일 이상이면 안된다. dp[idx][late][absent] 3..

[Java] 카운팅 정렬 (Counting Sort)

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 백준 10989번 수 정렬하기3 문제를 Collections.sort()로 오름차순 정렬했더니 아래와 같은 메모리 초과 오류가 떴다. 구글링을 통해 알아보았더니, Collections.sort()나 Arrays.sort()같은 메소드는 평균 시간복잡도가 𝚶(nlogn) 인 반면에 Counting sort는 평균 시간복잡도가 𝚶(𝑛) 인 성능을 보여주는 알고리즘인 것을 알게 되었다. Arrays.sort()는 평균: ..

[백준] 1920번 : 수 찾기 - JAVA [자바] 이분 탐색 문제

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다. 알고리즘 [접근 방법] 일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자. 이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고,..

[백준] 1874번 : 스택 수열 - JAVA [자바]

www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 스택의 원리만 이해한다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 아마 이 문제를 처음 접한다면 무슨 말인가 할 수도 있겠지만, 이해만 한다면 정말 쉬운 문제다. 스택 자료구조는 본문에서도 나와있듯이 LIFO(후입선출) 특성을 갖고있다. 스택에 대한 기본적인 이해는 다음 포스팅을 참고하시길 바란다. 자바 [JAVA]..

[백준] 1654번 : 랜선 자르기 - JAVA [자바]

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 이분 탐색의 응용 문제다. 알고리즘 [접근 방법] 일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다. 그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다. https://st-lab.tistory.com/267 [백준] 10816번 : 숫자 카드 2 - JAVA [자바] https://ww..