문제: 음악 프로그램 (백준 2623번)문제 분석이 문제는 사이클 탐색과 위상 정렬을 결합한 문제이다.지문은 길지만, 문제의 핵심은 주어진 조건에 따라 유방향 그래프를 만들고, 그 그래프에서 사이클이 있는지 확인한 뒤, 사이클이 없다면 위상 정렬을 수행하는 것이다.해결 접근사이클 탐색각 가수 간의 선후 관계를 유방향 그래프로 표현한다.사이클이 있으면 그 그래프는 위상 정렬이 불가능하다.DFS를 사용하여 그래프에서 사이클을 탐지한다.위상 정렬사이클이 없으면 위상 정렬을 통해 가수들의 순서를 결정한다.위상 정렬은 진입 차수가 0인 노드를 먼저 처리하며, 이를 통해 순서를 구한다.우선순위 큐위상 정렬을 수행하는 중에 여러 노드가 진입 차수가 0일 때, 우선순위 큐를 사용하여 가장 작은 번호부터 처리하도록 한다..

문제: 보석 도둑 (백준 1202번)문제 분석이 문제는 풀이법이 바로 떠오른다면 쉽게 해결할 수 있지만, 그렇지 않다면 접근법을 찾기 어려운 웰메이드 문제이다.알고리즘 자체는 복잡하지 않으나, 핵심 아이디어를 도출하는 것이 도전 과제다.핵심 아이디어정렬가방과 보석을 무게 순으로 오름차순 정렬한다.작은 가방부터 차례로 탐색하며 해당 가방에 들어갈 수 있는 보석들을 선택한다.우선순위 큐현재 가방에 들어갈 수 있는 보석들을 모두 우선순위 큐에 삽입한다.이때, 우선순위 큐는 보석의 가치를 기준으로 내림차순 정렬되도록 설정한다.우선순위 큐의 맨 앞에 있는 보석은 현재 가방이 담을 수 있는 최고 가치의 보석이다.탐욕적 선택작은 가방부터 순서대로 처리하며, 현재 가방이 담을 수 있는 최고 가치의 보석을 선택한다.이를..

문제: 낚시왕 (백준 17143번)간만에 빡구현 문제를 풀어보았다.각각의 알고리즘 자체는 어렵지 않지만, 구현할 내용이 많아 세심한 작업이 필요했다.이 문제의 핵심은 상어의 이동 계산이다. 이동을 시뮬레이션할 때 1칸씩 이동하지 않고 최종 위치를 계산하는 방식으로 처리해야 한다.이 부분만 주의하면 큰 시간 초과 없이 문제를 해결할 수 있다.상어 클래스 정의상어의 위치, 속도, 이동 방향, 크기를 관리하기 위해 Shark 클래스를 작성했다.생성자에서는 초기 위치와 속도, 방향, 크기를 입력받아 초기화한다.또한, 상어의 이동을 처리하는 Move 메서드를 구현하여 방향과 속도에 따라 위치를 업데이트한다.class Shark {public: int x, y; int speed; int direc..

C++에서 제공하는 정렬 함수: IntroSortC++의 알고리즘 헤더에서는 sort() 함수를 지원한다. 정말 많은 sort 알고리즘이 존재하지만 C++에서 제공하는 정렬 함수는 어떤 알고리즘을 사용하는지 알아보자.정렬 알고리즘의 종류와 시간 복잡도여러가지 알고리즘에 대한 간략한 설명과 시간 복잡도를 보면 다음과 같다.알고리즘시간 복잡도 (최선)시간 복잡도 (평균)시간 복잡도 (최악)공간 복잡도퀵 정렬 (Quick Sort)O(n log n)O(n log n)O(n²)O(log n)힙 정렬 (Heap Sort)O(n log n)O(n log n)O(n log n)O(1)삽입 정렬 (Insertion Sort)O(n)O(n²)O(n²)O(1)C++의 IntroSort이런 널리 알려진 정렬 알고리즘과 달리..