오늘은 너비 우선 탐색(BFS) 을 사용해 그래프의 정점을 탐색하면서 방문 순서를 기록하는 방법을 배웠습니다. BFS는 큐(queue)를 사용하여 가까운 정점부터 방문하므로, 그래프의 각 정점을 최단 거리 순서로 방문할 수 있습니다. 이번 문제에서는 각 정점의 방문 순서를 기록하고, 시작 정점에서 도달할 수 없는 정점은 0으로 표시하도록 했습니다.문제링크 :https://www.acmicpc.net/problem/24444문제 접근 과정1, 문제 분석과 그래프 구현 방식 선택주어진 그래프는 무방향 그래프로, 각 간선은 양방향으로 연결됩니다. 이를 위해 양방향 간선을 인접 리스트 형태로 구현해야 했습니다.그래프 탐색에서는 인접 행렬보다 인접 리스트가 메모리와 속도 면에서 더 효율적이므로, 인접 리스트를 사..

오늘은 깊이 우선 탐색(DFS)을 통해 그래프의 방문 순서를 기록하는 방법을 배웠습니다. DFS는 재귀 호출을 통해 그래프의 노드를 탐색하며, 방문 순서까지 기록하는 방식으로 응용할 수 있습니다. 특히 인접 리스트를 사용한 오름차순 탐색과 양방향 그래프 처리가 중요한 포인트였습니다.문제 링크 : https://www.acmicpc.net/problem/24479문제 접근 과정1, 문제 분석과 그래프 구조 선택주어진 그래프는 무방향 그래프로, 양방향 간선이 존재하기 때문에 각 간선을 양쪽 모두에 추가해야 합니다.정점과 간선의 개수가 크기 때문에, 인접 리스트를 사용해 그래프를 구현하였습니다. 인접 행렬 방식은 메모리와 속도에서 비효율적이므로 인접 리스트가 더 적합했습니다.2, DFS 탐색 순서와 오름차순 ..

오늘은 이분 탐색을 활용해 예산 분배 문제를 풀면서 탐색 범위 설정과 조건에 맞는 최적의 상한액을 찾는 방법을 배웠습니다. 특히 제한된 예산 내에서 최대 상한액을 찾는 과정에서 이분 탐색이 효율적이라는 점을 실감했습니다.문제 링크 : https://www.acmicpc.net/problem/2512문제 접근 과정상한액 설정과 탐색 범위 설정주어진 예산을 초과하지 않으면서 지방의 요청 예산을 최대한 배정해야 합니다. 이를 위해 특정 상한액 이하의 요청은 그대로 배정하고, 상한액을 초과하는 요청은 상한액만 배정합니다.탐색 범위는 low = 1부터 high = 가장 큰 요청 금액까지 설정합니다. 상한액을 이 범위 내에서 조정해 최적의 값을 찾아야 합니다.이분 탐색을 통한 최적 상한액 찾기이분 탐색을 사용해 상..

오늘은 징검다리 문제에서 이분 탐색을 활용하여 최대 몇 개의 징검다리를 밟을 수 있는지 찾는 풀이 방법을 정리했습니다. 이 문제에서 중요한 부분은 조건을 수식으로 변환하고, 오버플로우를 방지하는 이분 탐색을 사용하는 것이었습니다.문제링크 : https://www.acmicpc.net/problem/11561문제 접근 과정규칙 분석승택이는 N번 징검다리를 반드시 밟아야 하며, 이전에 밟았던 징검다리보다 1 이상 더 먼 거리를 점프해야 합니다. 예를 들어, 점프 거리가 1, 2, 3, ..., K가 되며, 이 점프들의 총합이 N을 넘지 않아야 합니다.이 규칙을 통해 등차수열의 합 공식을 적용할 수 있습니다: 합 =  K * (K + 1) / 2 ​K 값 찾기 - 이분 탐색을 활용한 최대값 찾기이분 탐색을 통..

오늘은 문제 해결 과정에서 이분 탐색(Binary Search)을 어떻게 식별하고 적용할지에 대해 정리해보았습니다.문제 설명형택이는 과거 스파이더 카드놀이에서 이긴 횟수와 게임 횟수가 주어졌을 때, 승률을 1% 올리기 위해 최소 몇 번의 추가 승리가 필요한지를 구해야 합니다.문제 링크 : https://www.acmicpc.net/problem/1072문제 접근 방법처음에는 재귀 함수로 각 경우를 일일이 검사하면서 승률을 올리는 방식을 생각했습니다. 하지만 문제의 입력 범위가 매우 컸기 때문에, 재귀를 통해 모든 경우를 하나씩 검사하는 것은 불필요하게 많은 함수 호출을 야기해 비효율적이었습니다. 특히, 승률이 한 번 변하는 최소 조건을 찾는 문제에서는 이런 순차적인 접근이 적합하지 않았습니다. 큰 입력에..

이 문제는 N개의 문제에 대해 각 문제를 풀었을 때 받을 수 있는 컵라면 수와 해당 문제를 풀어야 하는 마감시간(데드라인)이 주어졌을 때, 동호가 받을 수 있는 최대 컵라면 수를 구하는 문제입니다. 각 문제는 데드라인 안에 풀어야 하고, 문제를 풀 때 걸리는 시간은 1시간입니다.문제링크:https://www.acmicpc.net/problem/1781 문제 분석문제의 조건:각 문제는 단위 시간 1이 걸리며, 각 문제마다 주어진 데드라인 내에 풀어야 합니다.각 문제를 풀면 받을 수 있는 컵라면 수가 주어집니다.N개의 문제 중 데드라인 내에서 최대한 많은 문제를 풀어 최대 컵라면을 얻어야 합니다.접근 전략:각 문제를 데드라인이 짧은 순서대로 풀면서, 컵라면 수를 최대화해야 합니다.만약 데드라인보다 많은 문제..

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "숨바꼭질 2" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 수빈이가 동생을 찾기 위해 이동하는 가장 빠른 시간과 그 시간으로 동생을 찾는 방법의 수를 구하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다. 문제링크: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제개요 "숨바꼭질 2" 문제는 수빈이가 동생을 찾기 위해 이동하..

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "괄호 추가하기" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 수식에 괄호를 적절히 추가하여 만들 수 있는 식의 결과값 중 최대값을 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다. 문제링크: https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제개요 "괄호 추가하기" 문제는 수식에 괄호를 적절히 추가하여 만들 수 있는 식의 결과값 중 최대값을 찾는..