민규의 흔적

2025년 5월 30일문제 링크 : 백준 2467번 - 용액 문제 접근 오름차순으로 각 용액의 특성값이 주어지는데, 두 용액을 선택해 특성값을 더했을 때 0에 가장 근접하는 두 용액의 특성값을 출력하면 되는 문제이다. 만약 그러한 두 용액 쌍이 2개 이상 존재할 경우 아무 용액 쌍이나 출력해도 된다. 모든 용액 쌍을 구해 각 합에 절댓값을 씌워 0에 가장 가까운 용액 쌍을 출력하는 단순한 방식은, N 이 용액의 개수일 때 시간복잡도 O(N^2)을 가지게 된다. 용액의 개수가 최대 100,000이므로 시간 초과를 범할 것이기에 적절하지 않은 방식이다. 이에 나는 투 포인터를 활용해 포인터를 적절하게 움직여 O(N) 시간복잡도를 가지는 알고리즘 설계를 고안했다. 시도 1 (예외가 발생하는 틀린 풀이)(올바른..

2025년 5월 16일문제 링크 : 백준 1300번 - K번째 수 문제 접근 문제는 정말 간단한다. (이런 간단한 문제가 정말 무서운 문제다.) N 이 3이라면 3X3 사이즈의 A 행렬은 다음과 같이 나타낼 수 있다. i 행 j 열의 값은 i * j 로 채워져 있다. 이를 1 X N ^2 사이즈의, A 행렬의 각 요소를 오름차순으로 정렬한 B 벡터는 다음과 같이 나타낼 수 있다. 문제에서 원하는 바는 어떤 정수 k가 주어졌을 때 B[k] 의 값을 구하는 것, 즉 A행렬의 값들 중 k 번째로 작은 값을 구하는 것이다.( k는 min(10^9, N ^2)보다 작거나 같은 자연수 ) Naive method (시간 초과) 단순하게 생각할 수 있는 방법으로 문제를 다음과 같이 접근해 볼 것이다. 1. A 행..

2025년 5월 16일문제 링크 : 백준 28119번 - Traveling SCCC President 문제 접근 문제를 요약하면 다음과 같다. 요약1. 대학 캠퍼스에는 1부터 N 까지 번호가 붙어 있는 N 개의 건물이 있다. 건물 번호는 중복 없이 1부터 N 까지 정수가 정확히 하나씩 존재한다.2. 서로 다른 두 건물을 연결하고 1부터 M 까지 번호가 붙어 있는 M 개의 도로가 있다. 각 도로는 통행하는 데 일정 시간이 소요된다. 두 건물을 직접 잇는 도로가 존재하지 않더라도, 다른 이어진 건물로 우회하여 이동할 수 있다면 두 건물은 연결되어 있다고 표현한다. 모든 건물은 도로를 통해 이어져 있으며, M 은 최소 N - 1개 존재한다. 3. 건물 N 개 모두를 주어진 차례대로 방문해야 한다.4. 한 번 ..

2024년 11월 26일위상 정렬 위상 정렬이란, 순환하지 않는 유향 그래프(DAG, Directed Acyclic Graph)를 방향성에 거스르지 않도록 순서대로 배열하는 방법이다. 이게 무슨 의미인가. 다음 예시를 통해 쉽게 이해해보자. 나는 어떤 RPG 게임을 시작하려고 한다.해당 RPG 게임에서는 첫 레이드인 A 보스 레이드에 참여하기 위해서 50레벨을 달성하고 모든 장비 강화를 10단계 이상 달성해야 한다.그리고 다음 레이드인 B 보스 레이드에 참여하기 위해서, A 보스 레이드를 클리어한 상태에서 모든 장비 강화를 15단계 이상 달성해야 한다.그리고 장비를 업그레이드 하기 위해서는 B 보스 레이드를 클리어한 상태에서 기존 장비를 상위 장비로 계승해야 한다. 어떤 RPG 게임에서 내가 이룩하고 싶..