개인 공부185 [알고리즘] 재귀 & 그리디 알고리즘 🎯 목표 재귀 알고리즘의 구조를 이해한다. 그리디 알고리즘을 이해하고 자주 나오는 유형을 익힌다. 🔄️ 재귀 알고리즘 자기 자신을 다시 호출하는 구조를 가진 알고리즘이다. 보통 더 작은 구조를 다시 호출해서 해결한다. 이는 분할-정보 알고리즘과 유사하다. public void recursion(int n) { if (n == MIN_SIZE) { // 가장 작은 단위의 일을 한다. } // 가장 작은 단위가 될 때까지 쪼갠다. return recursion(n - 1); } ✌ 특징 코드가 이뻐보일 순 있다. 하지만 스택 오버플로우가 발생할 수 있고 정확한 호출 회수를 예측하기 어렵다. 따라서, 재귀로 풀 수 있는 문제는 다른 방법으로 먼저 접근해본다. 그래도 재귀로 풀겠다면, 가장 작은 단위의 일에 대.. 2023. 5. 3. [Java] 백준 1374번 : 강의실 https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 💡 문제 풀이 강의실 배정 문제이다. 이 문제는 최선의 강의실 개수를 구하는 문제이다. 가장 빨리 끝나는 강의 혹은 가장 빨리 시작하는 강의를 기준으로 탐색해서 해결할 수 있다. 이번 문제에선 가장 빨리 시작하는 강의를 기준으로 해결했다. 대기 중인 강의가 우선순위 큐에 저장되고 강의의 개수만큼 탐색한다. 지금 하는 강의가 끝나고 대기 중인 다음 강의가 진행될 수 있다면 다음 강의를.. 2023. 5. 3. [Java] 백준 24460번 : 특별상이라도 받고 싶어 https://www.acmicpc.net/problem/24460 24460번: 특별상이라도 받고 싶어 첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수) 두 번째 줄부터 $N$개 줄의 $i$번째 줄에는 $i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨 www.acmicpc.net 💡 문제 풀이 분할 정복과 재귀가 합쳐진 문제이다. 주어진 영역을 4개의 구역으로 나눠서 가장 작은 구역이 되었을 때 그 값을 리턴하도록 한다. ✔️ 느낀 점 재귀의 핵심은 역시 가장 작은 단위가 되었을 때 어떤 값을 리턴하도록 하는 것인가? 인 것 같다. 어렵지는 않았지만 자바 코드로 작성하는 게 매우 어색한 문제였다. 💻 코드.. 2023. 5. 2. [Java] 백준 1477번 : 휴게소 세우기 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 💡 문제 풀이 이분 탐색 문제이다. 세워야 할 휴게소만큼 각 구간 별로 확인해서 모두 세울 수 있는지 확인하면 된다. 검색할 값은 휴게소간의 거리이고, 확인 값은 주어진 거리로 휴게소를 세울 때 조건만큼 세울 수 있는지이다. 시작 범위(0부터)와 마지막 범위(고속도로 끝까지)도 따져야 하므로 0과 l을 리스트에 추가해 준다. ✔️ 느낀 점 이분 탐색에 부족함을 느끼고 풀었던 문제인데, 생각보다 금방 풀었다. 💻 코드 i.. 2023. 4. 28. [알고리즘] 정렬 & 탐색 알고리즘 😋 들어가기 앞서 이번에 알고리즘 스터디를 새롭게 시작했다. 내 입맛대로 그러면서 이전에 공부했던 것을 복습하는 시간을 가지기 위해서 한번 싹 정리해볼까 한다. 내가 가장 기본이라 생각하는 정렬, 탐색 알고리즘부터 시작해볼까 한다. 🎯 목표 정렬 알고리즘의 종류를 익히고, 각각의 시간복잡도와 구현법을 익힌다. 이분탐색 알고리즘을 이해한다. 🪜 정렬 알고리즘 이름 그대로 주어진 데이터를 정렬하는 알고리즘이다. 7가지 알고리즘이 기본이고, 응용에 따라서 추가적인 알고리즘이 존재한다. 1️⃣ 선택 정렬 선택한 값을 모두 비교해서 알맞은 자리를 찾는 정렬 알고리즘이다. 즉, 선택한 값 다음에 오는 모든 값을 비교해서 가장 작은 값과 위치를 바꾼다. 시간복잡도 : O(n^2) public void selectio.. 2023. 4. 28. [Python] 백준 3079번 : 입국심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 💡 문제 풀이 이분탐색 문제이다. 이번 이분탐색 문제에서 중심이 되는 값은 주어진 시간에 얼마나 많은 사람들이 통과할 수 있을까이다. 최대 범위(모든 사람이 가장 오래걸리는 심사대)에서 최소 범위(0)부터 이분탐색을 진행한다. 모든 입국 심사대를 확인하는데, 주어진 시간으로 얼마나 많은 사람들이 통과할 수 있는지만 보면 된다. ✔️ 느낀 점 이분 탐색은 항상 헷갈리는 문제이지만 어떤.. 2023. 4. 27. 이전 1 2 3 4 5 6 7 ··· 31 다음
