문제: 신입 사원(백준 1946번)문제 분석이 코드는 신입 사원 선발 문제를 해결하기 위한 코드다.주어진 t개의 테스트 케이스에 대해 각 지원자의 서류 성적과 면접 성적이 주어진다.이 중 두 성적 중 하나라도 다른 지원자보다 나은 경우에만 선발한다.즉, 어떤 지원자가 다른 지원자들에 의해 완전히 밀리지 않는 경우를 찾는 문제다.알고리즘 설명입력받기각 테스트 케이스마다 n명의 지원자 정보(서류 성적, 면접 성적)를 입력받는다.정렬서류 성적 기준으로 오름차순 정렬한다.이로 인해 서류 성적이 앞서는 지원자만 비교하면 된다.최소 면접 성적 추적서류 성적이 낮은 순서로 순회하면서,이전까지의 최소 면접 성적(minVal)보다 현재 지원자의 면접 성적이 더 낮다면,해당 지원자는 선발 가능하다. 이 경우, answer..

문제: 후위 표기식(백준 1918번)문제 분석이 문제는 주어진 중위 표기식을 스택을 사용하여 후위 표기식으로 변환하는 문제다.후위 표기식은 연산자를 나중에 쓰는 표기법으로, 계산 순서를 명확히 나타낼 수 있다는 장점이 있다.후위 표기식중위 표기식은 연산자가 피연산자 사이에 위치한다.예: A + B후위 표기식은 연산자가 피연산자 뒤에 위치한다.예: AB+후위 표기식의 특징은 괄호 없이도 연산 우선순위를 명확히 알 수 있다는 점이다.예를 들어, A + B * C를 후위 표기식으로 바꾸면 ABC*+가 된다.알고리즘피연산자는 바로 출력한다.(문자열에서 알파벳이 나오면 바로 cout으로 출력)연산자는 스택에 넣는다.단, 스택에 있는 연산자와 우선순위를 비교해,스택의 연산자가 현재 연산자보다 우선순위가 높거나 같으..

문제: 음악 프로그램 (백준 16724번)문제 분석이번 문제는 주어진 그래프에서 사이클의 개수를 구하는 문제이다.입력 형식을 보면 지도 밖으로 나가는 방향의 입력은 주어지지 않기 때문에 결국 화살표들은 사이클을 최소 1개 이상 무조건 생성을 하게 되어있다.DFS를 사용한 사이클 개수 찾기사이클 개수를 구하기 위해 DFS를 활용한다.이때, 사이클 판별을 위해 visited와 finish 배열을 사용한다.visited[y][x]는 현재 칸이 방문되었는지 여부를 저장한다.finish[y][x]는 현재 칸에 대한 탐색이 끝났는지를 나타낸다.DFS를 통해 현재 칸에서 다음 칸으로 이동하면서, 다음과 같은 조건으로 사이클을 판별한다.다음 칸이 방문된 적이 있지만 탐색이 끝나지 않은 칸이라면, 이는 사이클이 형성되었..

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

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

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

문제: 사이클 게임 (백준 7579번)우리는 주어진 앱들의 메모리 사용량과 비활성화 비용을 바탕으로, 필요한 메모리 M 이상을 확보하기 위해 최소 비용을 계산해야 한다.이 문제는 0-1 Knapsack 문제를 응용한 형태로 볼 수 있다.핵심 아이디어앱의 메모리 사용량을 배낭 문제의 "가치", 비활성화 비용을 "무게"로 해석한다.목표는 최소 비용으로 M 이상의 메모리를 확보하는 것이다.비용(c)을 역순으로 탐색해 중복 계산을 방지한다.dp[j]는 "비용이 j일 때 확보할 수 있는 최대 메모리"를 나타낸다.코드 전체#include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m;..

문제: 빙산 (백준 2573번)간만의 구현 문제이다. 구현 문제는 말 그대로 구현하는 데 시간이 많이 걸리기 때문에 사용하는 알고리즘 자체는 크게 어렵지 않은 경우가 많다. 이번 문제도 그런 케이스이며, 전체적인 로직은 다음과 같다.문제 의도배열에 1 이상의 수가 남아있는 동안 반복time을 증가시키고2차원 배열을 돌며 상하좌우의 0의 개수와 해당 좌표를 저장저장해둔 0의 개수만큼 해당 좌표의 값을 감소 (0 미만이 되지 않도록)2차원 배열을 돌며 BFS로 그룹 개수 체크그룹 개수가 2개 이상이면 반복문을 정지배열의 1 이상의 수가 있으면 time을 출력아니면 0을 출력알고리즘 개요시간(time) 증가매번 반복할 때마다 시간을 증가시킨다.녹을 빙산 계산 각 좌표에서 상하좌우로 바다가 몇 칸 있는지 계산하..

문제: 사이클 게임 (백준 20040번)지문을 딱 보자마자 눈살이 찌푸려진다. 처음 이 문제의 지문을 읽었을 때 문제의 의도를 도출하는 데 꽤 시간이 걸렸다. 글자도 많고, 마치 비문학을 읽는 것처럼 의도하는 바가 무엇인지 이해하기 쉽지 않다.문제 의도와 핵심이 문제에서 요구하는 결론은 n개의 정점(노드)의 사이클 생성 여부를 알아내라는 것이다. 지문이 복잡하게 설명되었지만, 실제로는 간단한 Union-Find 알고리즘을 활용하여 사이클을 판별하는 문제다.같은 알고리즘을 사용하는 골드 5 난이도의 문제도 있는 걸 보면, 지문 이해 난이도가 추가되어 골드 4로 책정된가 아닌가 싶다.문제 요구 사항n개의 정점과 m개의 간선이 주어진다.간선이 입력될 때마다 사이클이 발생하는지 확인한다.사이클이 발생하면 해당 ..

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이런 널리 알려진 정렬 알고리즘과 달리..