Greedy3 투 포인터 알고리즘 Two Pointer Algorithm 프로그래머스에서 구명보트 문제를 풀다가 알게 된 투 포인터.사실 예에전에 코딩테스트에서 한번 맞닥뜨리고, 완탐으로 풀었던 나는 처참히 망해버렸다...후후... 복습하지 않고 있었는데, 이번 문풀을 기회 삼아 정리해 보자! 투 포인터 알고리즘이란? 투 포인터(Two Pointer) 알고리즘은 배열, 리스트 또는 문자열과 같은 선형 데이터 구조에서 두 개의 포인터를 사용해 특정 조건을 만족하는 부분을 탐색하거나 계산하는 알고리즘 기법이다.두 포인터가 데이터 구조의 양 끝에서 시작하거나, 같은 위치에서 출발하여 서로 다른 방향으로 이동하며 문제를 해결한다. 왜 쓰이는지? 효율적으로 배열이나 리스트에서 특정 조건을 만족하는 부분을 찾거나 연산을 수행.중첩 루프(이중 반복문) 없이 문제를 해결하여 시간 복잡도를 .. 2024. 12. 5. [Kotlin] BOJ 11000. 강의실 배정 출처https://www.acmicpc.net/problem/11000 문제수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 출력강의실의 개수를 출력하라. 풀이import java.io.BufferedReaderimport java.io.Input.. 2024. 11. 8. [C++] Softeer Lv.3 강의실 배정 출처https://softeer.ai/practice/6291 문제 김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다. 제약조건1 ≤ N ≤ 106 인 정수1 ≤ Si ＜ Fi ≤ 109 입력첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다. 출력첫 번째 줄에 최대 강의 수를 출력하라. 풀이#define _CRT_SECURE_NO_WARNINGS #include using namespace std;int main() { int N; sca.. 2024. 10. 29. 이전 1 다음
