![]()
개요문제 이름: LCS (9251)문제 링크: https://www.acmicpc.net/problem/9251플랫폼: 백준알고리즘 분류: DP소요 시간: 1시간 문제 전문설명입출력 문제 풀이해설이 문제는 두 문자열이 주어졌을 때, 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)의 길이를 찾는 문제입니다. LCS 문제는 대표적인 동적 계획법(Dynamic Programming, DP) 문제 중 하나입니다. 동적 계획법은 큰 문제를 작은 부분 문제로 나누어 풀이하는 알고리즘 설계 기법입니다. LCS 문제에서는 두 문자열의 부분 문제에 대한 솔루션을 통해 전체 문제의 솔루션을 구할 수 있습니다. 이 문제를 해결하기 위해서는 2차원 DP 테이블을 사용합니다. DP ..
![]()
개요문제 이름: 전화번호 목록 (5052) 문제 링크: https://www.acmicpc.net/problem/5052플랫폼: 백준알고리즘 분류: 정렬, 트리소요 시간: 1시간 30분 문제 전문설명입출력 문제 풀이해설이 문제는 주어진 전화번호 목록이 일관성을 유지하는지 판단하는 문제입니다. 전화번호 목록이 일관성을 유지하려면, 어떤 번호가 다른 번호의 접두어인 경우가 없어야 합니다. 문제를 해결하기 위해서는 다음과 같은 접근 방식을 사용할 수 있습니다.전화번호 목록을 정렬합니다.정렬을 하면 접두어 관계에 있는 번호들이 서로 인접하게 됩니다.정렬된 목록을 순회하면서 인접한 번호 쌍을 비교합니다.현재 번호가 다음 번호의 접두어인 경우, 목록은 일관성이 없는 것입니다. (NO 출력)현재 번호가 다음 번호의 ..
![]()
개요문제 이름: 트리 (1068) 문제 링크: https://www.acmicpc.net/problem/1068플랫폼: 프로그래머스/백준알고리즘 분류: 트리, DFS소요 시간: 1시간 30분 문제 전문설명 입출력 문제 풀이해설이 문제는 트리의 리프 노드 개수를 구하는 문제로, 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다. 주어진 트리에서 특정 노드를 삭제한 후 남은 트리의 리프 노드 개수를 세는 것이 목표입니다. 문제에서 요구하는 사항을 정리하면 다음과 같습니다.트리의 노드 개수 N이 주어진다. (N은 50 이하의 자연수)0번 노드부터 N-1번 노드까지 각 노드의 부모 노드 정보가 주어진다. 루트 노드는 -1로 표시된다.삭제할 노드 번호가 주어진다.주어진 트리에서 삭제할 노드를 제거하..
![]()
개요문제 이름: N번째 큰 수 (2075)문제 링크: https://www.acmicpc.net/problem/2075플랫폼: 백준알고리즘 분류: 정렬, 우선순위 큐소요 시간: 3시간 문제 전문설명제한사항메모리가 12 MB로 제한됨입출력 문제 풀이해설이 문제는 우선순위 큐를 사용하여 N x N 크기의 표에 채워진 N^2개의 수 중에서 N번째로 큰 수를 찾는 문제입니다. 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 특징이 있으며, 표에 채워진 수는 모두 다릅니다. 그러기에 주어진 표에서 각 줄을 읽어 들이면서 현재 읽은 숫자들 중에서 N개의 가장 큰 수만 우선순위 큐에 유지하면 됩니다. 여기서 우선순위 큐는 우선순위가 가장 높은 요소를 먼저 꺼내는 자료구조입니다. 이 문제에서는 숫자가 클수록 우선순위..
![]()
개요문제 이름: 평범한 배낭 (12865)문제 링크: https://www.acmicpc.net/problem/12865플랫폼: 백준알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제소요 시간: 5시간 문제 전문설명입출력 문제 풀이해설이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있는 대표적인 0-1 냅색 문제(Knapsack Problem) 혹은 배낭 문제 입니다. 냅색 문제는 제한된 용량의 가방(배낭)에 가치와 무게가 다른 물건들을 넣어 가방에 담을 수 있는 물건들의 가치합을 최대로 만드는 문제입니다. 0-1 냅색 문제는 각 물건을 가방에 담을지 안 담을지 두 가지 선택만 가능한 냅색 문제의 한 종류로, 동적 계획법의 대표적인 예시 문제 중 하나입니다. 이 문제에서 요..
![]()
개요문제 이름: 파도반 수열 (9461) 문제 링크: https://www.acmicpc.net/problem/9461플랫폼: 백준알고리즘 분류: 다이나믹 프로그래밍소요 시간: 50분 문제 전문설명입출력 문제 풀이해설이 문제는 다이나믹 프로그래밍이라고 불리는 동적 계획법을 사용하여 파도반 수열의 N번째 값을 구하는 문제입니다. 파도반 수열은 다음과 같은 점화식을 가집니다.P(N) = P(N-2) + P(N-3)N >= 4이는 N번째 파도반 수의 길이는 N-2번째 파도반 수의 길이와 N-3번째 파도반 수의 길이의 합과 같다는 것을 의미합니다.이 점화식을 활용하면 N번째 파도반 수의 길이를 계산할 수 있습니다. 동적 계획법의 핵심은 이전에 계산한 결과를 저장해 두고 필요할 때 그 값을 사용하는 것입니다. 이..
![]()
개요문제 이름: 정수 삼각형 (1932)문제 링크: https://www.acmicpc.net/problem/1932플랫폼: 백준알고리즘 분류: 다이나믹 프로그래밍소요 시간: 1시간 문제 전문설명입출력 문제 풀이해설이 문제는 정수 삼각형에서 맨 위층부터 아래층까지 경로를 따라 내려오면서 수를 선택할 때, 선택된 수의 합이 최대가 되는 경로를 구하는 문제입니다. 이를 해결하기 위해 다이나믹 프로그래밍(DP) 알고리즘을 활용합니다. 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 푸는 알고리즘으로, 이전에 계산한 부분 문제의 답을 메모리에 저장하여 다시 계산하지 않도록 합니다. 이 문제에서는 특정 층의 특정 위치에 도달했을 때 해당 위치까지의 선택된 수의 합이 최대인 값을 메모이제이션(Memoiza..
![]()
개요문제 이름: 내리막 길 (1520)문제 링크: https://www.acmicpc.net/problem/1520플랫폼: 백준알고리즘 분류: DFS소요 시간: 2시간 문제 전문설명입출력 문제 풀이해설이 문제는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 주어진 지도에서 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다. DFS는 그래프나 트리 등의 자료구조를 탐색하는 알고리즘 중 하나로, 현재 정점에서 갈 수 있는 경로를 따라 깊이 우선으로 탐색을 진행합니다. 더 이상 갈 수 없는 정점에 도달하면 이전 정점으로 돌아와 다른 경로를 탐색하는 과정을 반복합니다. 이 문제에서는 현재 위치에서 상하좌우로 이동할 수 있으며, 이동한 지점의 높이가 현재보다 낮아야 합니다. 이러한 조건을 만족하는 경로를 ..
![]()
개요문제 이름: 1, 2, 3 더하기 (9095)문제 링크: https://www.acmicpc.net/problem/9095플랫폼: 백준알고리즘 분류: 다이나믹 프로그래밍소요 시간: 10분 문제 전문설명입출력 문제 풀이해설이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 재활용함으로써 효율적으로 문제를 해결하는 알고리즘입니다. 이 문제에서는 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 합니다. 이를 위해 우선 작은 숫자부터 시작하여 점진적으로 큰 숫자에 대한 해답을 구하는 접근 방식을 취합니다.1을 만드는 방법: 1 (1가지)2를 만드는 방법: 1+1, 2 (2가..
![]()
개요 문제 이름: 경로 찾기 (11403)문제 링크: https://www.acmicpc.net/problem/11403플랫폼: 백준알고리즘 분류: DFS소요 시간: 2시간 문제 전문설명입출력 문제 풀이해설이 문제는 주어진 방향 그래프에서 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 있는지 판별하는 문제입니다. 이를 위해 DFS(깊이 우선 탐색) 알고리즘을 사용하여 각 정점에서 시작하여 도달 가능한 모든 정점을 탐색하고, 그 결과를 인접 행렬 형태로 저장합니다. DFS는 그래프의 탐색 알고리즘 중 하나로, 시작 정점에서부터 한 방향으로 갈 수 있는 만큼 깊이 탐색하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 계속 반복하여 모든 정점을 방문하는 순..
![]()
개요문제 이름: 토마토 (7569)문제 링크: https://www.acmicpc.net/problem/7569플랫폼: 백준알고리즘 분류: BFS소요 시간: 2시간 문제 전문설명입출력문제 풀이해설이 문제는 3차원 공간에서 토마토의 익는 시간을 구하는 문제입니다. BFS (Breadth-First Search) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 너비 우선 탐색으로, 시작점에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. 입력받은 토마토 상자 정보를 3차원 배열로 저장합니다.익은 토마토의 위치를 큐에 넣고, 방문 표시를 합니다.BFS를 수행하면서, 익은 토마토의 인접한 위치에 있는 익지 않은 토마토를 익게 만들고, 익은 토마토의 위치를 큐에 넣습니다.BFS가 종료되었을 때, 모든 토마토..
![]()
개요문제 이름: 숨바꼭질 (1697) 문제 링크: https://www.acmicpc.net/problem/1697플랫폼: 백준알고리즘 분류: BFS소요 시간: 1시간 문제 전문설명입출력문제 풀이해설이 문제는 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 그래프나 트리에서 인접한 노드를 먼저 탐색하는 알고리즘으로, 시작 노드에서 가까운 노드들을 먼저 방문하고 멀리 떨어진 노드를 나중에 방문합니다. 문제에서 수빈이는 현재 위치에서 걷거나 순간이동을 할 수 있습니다. 걸을 때는 X-1 또는 X+1로 이동하고, 순간이동을 할 때는 2*X의 위치로 이동합니다. 이를 그래프로 표현하면, 각 노드는 수빈이의 현재 위치를 나타내고, 각 노드에서 인접..
![]()
개요문제 이름: 바이러스 (2606)문제 링크: https://www.acmicpc.net/problem/2606플랫폼: 백준알고리즘 분류: DFS소요 시간: 2시간 문제 전문설명입출력문제 풀이해설이 문제는 주어진 컴퓨터 네트워크에서 1번 컴퓨터가 웜 바이러스에 감염되었을 때, 1번 컴퓨터와 직접 또는 간접적으로 연결된 컴퓨터 중에서 웜 바이러스에 감염되는 컴퓨터의 총 개수를 구하여 출력해야 하는 문제입니다. DFS 알고리즘을 사용하여 그래프를 탐색하는 전형적인 예시라고 할 수 있겠습니다. 그래프를 생성하고, 시작점(1번 컴퓨터)부터 DFS 탐색을 수행하여 연결된 컴퓨터들을 방문하고, 방문한 컴퓨터의 수를 세어주는 과정으로 해결할 수 있습니다. 사실상 주어진 네트워크 상에서 1번 컴퓨터와 직접 또는 간접..
![]()
개요문제 이름: 전쟁 - 전투 (1303) 문제 링크: https://www.acmicpc.net/problem/1303플랫폼: 백준알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색소요 시간: 3시간 문제 전문설명입출력 문제 풀이해설이 문제는 전쟁터에서 각 병사의 위치와 소속팀이 주어졌을 때, 각 팀의 전투력을 계산하는 문제입니다. 전투력은 같은 팀의 병사들이 인접해 있을 때 그 그룹의 크기의 제곱으로 계산됩니다. 이 문제는 그래프 탐색 알고리즘 중 하나인 DFS(Depth-First Search, 깊이 우선 탐색)를 사용하여 해결할 수 있습니다. 문제 해결을 위해 다음과 같은 접근 방식을 사용할 수 있습니다.전쟁터를 2차원 배열로 표현하고, 각 병사의 위치와 소속팀을 입력받..
![]()
개요문제 이름: 호텔 대실 (155651) 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/155651플랫폼: 프로그래머스알고리즘 분류: 그리디소요 시간: 4시간 20분 문제 전문설명제한사항입출력 문제 풀이해설호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다. 예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 반환하는 함수를 완성하는 것이 문제의 목표입니다. 문제 해결을 위한 접근 방식은 아래와 같습니다.시간 표현 변환: 주어진 시각 형..
![]()
개요문제 이름: 무인도 여행 (154540) 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154540플랫폼: 프로그래머스알고리즘 분류: 일반소요 시간: 5시간 문제 전문설명제한사항입출력 문제 풀이해설이 문제는 2차원 격자 형태의 지도에서 연결된 무인도를 탐색하고, 각 무인도에서 최대로 머물 수 있는 일수를 계산하는 문제입니다. 문제를 해결하기 위해서는 그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색(DFS)을 활용합니다. DFS는 그래프의 한 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식으로 진행됩니다. 즉, 한 방향으로 갈 수 있을 때까지 깊이 탐색하다가 더 이상 갈 수 없게 되면 이전 노드로 돌아와서 다른 방향으로 탐색을 ..
![]()
개요문제 이름: [3차] 방금그곡 (17683) 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17683플랫폼: 프로그래머스알고리즘 분류: 일반소요 시간: 7시간 문제 전문설명입출력 문제 풀이해설이 문제는 네오가 기억하고 있는 멜로디를 바탕으로 실제로 방송된 음악을 찾는 문제입니다. 문제 해결을 위해서는 주어진 음악 정보를 바탕으로 실제로 재생된 멜로디를 구하고, 네오가 기억하고 있는 멜로디가 그 안에 포함되어 있는지를 확인해야 합니다. 문제 해결을 위한 접근 방식은 다음과 같습니다.네오가 기억하고 있는 멜로디와 음악 정보의 멜로디에서 '#'이 붙은 음을 소문자로 변환합니다.이는 같은 음임에도 불구하고 '#'의 유무에 따라 다른 음으..
![]()
개요문제 이름: 귤 고르기 (138476)문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/138476플랫폼: 프로그래머스알고리즘 분류: 일반소요 시간: 1시간 문제 전문설명제한사항입출력 문제 풀이해설이 문제는 귤의 크기별 개수를 파악하여, 최소한의 종류로 k개의 귤을 고르는 문제입니다. 문제 해결을 위해 먼저 귤의 크기별 개수를 파악하고, 개수가 많은 순서대로 귤을 고르는 그리디 알고리즘을 적용할 수 있습니다. 문제 접근 방식은 다음과 같습니다.귤의 크기별 개수를 파악하기 위해 객체(sizeCount)를 생성합니다.주어진 배열(tangerine)을 순회하면서 각 크기의 귤이 몇 개 있는지 객체에 저장합니다.객체의 값(귤의 개수)을 배열..
![]()
개요문제 이름: 멀쩡한 사각형 (62048)문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/62048플랫폼: 프로그래머스알고리즘 분류: 일반소요 시간: 40분 문제 전문설명제한사항입출력 문제 풀이해설이 문제는 격자 형태로 그어진 직사각형 종이에서 대각선으로 잘라낸 후 사용할 수 있는 정사각형의 개수를 구하는 문제입니다. 문제 해결을 위해서는 전체 사각형의 개수에서 대각선에 의해 잘린 사각형의 개수를 빼는 방식을 사용할 수 있습니다. 문제에서 주어진 조건은 다음과 같습니다.가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다.종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있습니다.모든 격자칸은 1cm x 1c..
![]()
개요문제 이름: 예상 대진표 (12985)문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12985플랫폼: 프로그래머스알고리즘 분류: 일반소요 시간: 30분 문제 전문설명제한사항입출력 문제 풀이해설이 문제는 토너먼트 형식의 대회에서 두 참가자가 몇 번째 라운드에서 만나는지를 찾는 문제입니다. 문제를 해결하기 위해서는 라운드를 진행하면서 A와 B의 위치를 업데이트하는 방식을 사용할 수 있습니다. 문제에서 주어진 조건은 다음과 같습니다.N명의 참가자는 1부터 N번까지 번호를 배정받습니다.1번 2번, 3번 4번, ... , N-1번N번의 참가자끼리 게임을 진행합니다.각 게임에서 이긴 사람은 다음 라운드에 진출합니다.다음 라운드에 진출할 참..
