백준 (59) 썸네일형 리스트형 [백준] 숫자놀이 (1679번) 문제 힌트 1. 자료구조배열을 이용한 DP (동적 계획법) 활용목적: 특정 숫자를 만들기 위한 최소 연산 횟수를 기록하여 계산 최적화이유:매번 새로운 숫자를 만들 때, 이전에 계산된 최적의 값(dp[i])을 활용하면 중복 연산을 피할 수 있음최댓값 기반 DP 테이블 크기 설정방법: dp[max * K + 1] 크기의 배열 생성이유:주어진 숫자들을 조합하여 만들 수 있는 최대값은 max * K+1을 추가하여 배열 인덱스를 다루기 쉽게 설정 2. 핵심 아이디어1부터 최댓값까지 반복 탐색1부터 최댓값(max * K + 1)까지 순차적으로 확인현재 숫자를 만들기 위한 최소 연산 횟수(dp 값)을 계산dp[i] > K가 되는 순간, 게임 종료사용할 수 있는 숫자 방문오름차순 정렬된 사용 가능한 숫자 배열을 순회하.. [백준] 수 묶기(1744번) 문제 힌트1. 자료구조음수, 양수 리스트음수는 음수끼리 양수는 양수끼리 곱을 하여 관리하기 위해 자료구조 분리이유 : 음수의 갯수가 홀수 일 때 관리의 번거로움이 생김Collections.sort()리스트에 값을 전부 저장하고 정렬하기이유: 1 2 3 4 5가 주어졌을 때 가장 큰 수는 5*4 + 3*2 + 1이 가장 높은 수 이기 때문boolean zeroFlag0이 있는지 여부를 저장이유 : 0은 사용하지 않는 음수가 있을 때 곱을 하여 해당 음수를 0으로 만들어 가장 큰 수로 만들 수 있음0이 2개 이상일 경우 몇 개가 있어도 의미가 없는 숫자이기 때문에 boolean으로 관리 2. 핵심 아이디어리스트를 사용한 정렬 및 분류음수와 양수를 분리하여 정렬하고 각각 계산하므로, 구조가 간단하면서도 효율적.. [백준] 알고리즘 수업 - 깊이 우선 탐색 2 (24480번) 문제 힌트1. 자료구조List[] (그래프 표현)정점 간의 간선을 표현하기 위해 인접 리스트를 사용합니다.이유: 정점과 간선의 수가 크기 때문에 인접 행렬을 사용하면 공간 복잡도가 매우 비효율적입니다. 인접 리스트를 통해 필요한 간선 정보만 저장해 메모리를 절약할 수 있습니다.int[] (방문 순서 기록)방문 순서를 저장하기 위해 배열을 사용합니다.이유: 정점 번호와 배열의 인덱스를 매칭하여 빠르게 방문 순서를 기록할 수 있습니다. 배열을 통해 O(1) 시간에 순서를 조회하거나 설정할 수 있습니다.Collections.sort (내림차순 정렬)문제에서 요구하는 인접 정점을 내림차순으로 방문을 구현하기 위해 사용합니다.이유: 탐색 전에 인접 리스트를 내림차순으로 정렬함으로써 DFS 수행 중 자연스럽게 내림.. [백준] 토마토 (7569번) 코드 힌트자료 구조토마토 관리 : 상, 하, 좌, 우, 위, 아래를 관리하기 위해 3차원 배열을 사용상태 변화 : 이중 큐를 사용하여 이미 익은 토마토와 방금 익은 토마토를 관리핵심 로직그래프를 초기화(입력 받기) 시킵니다.이 때 익은 토마토(값이 1일 때)를 큐에 저장을 합니다.회차 별로 BFS를 시작합니다.익은 토마토로 인해 확산되어 익은 토마토는 또 다른 큐에 저장합니다기존의 큐에 저장을 하면 count를 제대로 할 수 없습니다.BFS가 종료되었을 때 이제 막 익은 토마토 큐가 비어있는 지 확인합니다.만약 새롭게 익은 토마토가 없다면(큐가 비어있을 때) 그대로 종료합니다.새롭게 익은 토마토가 있다면 익은 토마토 큐에 저장을 하고 막 익은 토마토 큐를 비워줍니다.새롭게 익은 토마토가 없을 때 까지 반.. [백준] 친구 (1058번) N명의 사람들이 친구 관계를 나타내는 그래프를 바탕으로, 특정 사람의 "2-친구"(직접 친구거나 친구의 친구인 관계)를 계산한 뒤, 가장 많은 2-친구를 가진 사람의 수를 출력합니다. 코드 힌트입력 처리사람 수 N과 N×N 크기의 친구 관계를 나타내는 그래프를 입력받습니다.그래프는 각 사람이 다른 사람과 친구인지 여부를 "Y"(친구)와 "N"(친구 아님)으로 나타냅니다.최대 2-친구 탐색각 사람을 시작점으로 하여, "2-친구"를 탐색합니다.이를 위해 너비 우선 탐색(BFS)를 사용합니다:시작점에서 직접 친구(깊이 1)와 친구의 친구(깊이 2)까지만 탐색합니다.이미 방문한 사람은 중복 처리하지 않습니다.결과 계산각각의 사람에 대해 계산된 2-친구 수를 확인하고, 가장 큰 값을 갱신합니다.마지막에 가장 많은.. [백준] 평행사변형 (1064번) 문제 해결 흐름1. 입력3개의 점의 좌표 A(x1,y1), B(x2,y2), C(x3,y3)를 입력받습니다.2. 일직선 확인주어진 3개의 점이 일직선상에 위치하는지 확인해야 합니다.조건: 점 A, B, C가 일직선상에 존재하면 평행사변형은 물론 사각형을 만들 수 없으므로 프로그램을 종료합니다.기울기 공식 : 기울기(AB) = (y2 - y1) / (x2 - y1)프로그래밍으로 나눗셈을 계산할 때는 부동소수점으로 인하여 계산이 정확하지 않습니다. 나눗셈을 사용하는 대신 곱셈 방식으로 변경하여 계산합니다.나눗셈을 곱셈으로 변경: (x2−x1)⋅(y3−y1)=(x3−x1)⋅(y2−y1)3. 거리 계산점과 점 사이의 거리를 계산하기 위해 유클리드 거리 공식을 사용합니다유클리드 거리(Euclidean.. [백준] 요세푸스 문제(1158번): 커스텀 원형 연결 리스트로 해결하기 코드 힌트문제 흐름n명의 사람들이 원형으로 앉아 있습니다.매 k번째 사람을 제거하는 작업을 반복해 최종 순서를 출력합니다.기본적으로 요세푸스 문제는 큐를 활용한 풀이가 일반적이지만, 이 코드는 원형 연결 리스트를 직접 구현해 해결합니다.핵심 아이디어원형 연결 리스트 구현: 각 노드가 자기 자신을 포함한 원형 구조를 형성합니다. 마지막 노드는 처음 노드를 참조하며 리스트의 끝이 없습니다.현재 노드 추적: pointNode를 활용해 현재 노드를 추적하며, 매 k번째 노드를 제거합니다.출력 최적화: StringBuilder를 사용해 제거된 노드의 순서를 효율적으로 출력합니다.알고리즘 흐름리스트 초기화CircularLinkedList 클래스에서 노드를 추가해 원형 연결 리스트를 구성합니다.첫 번째 노드는 sta.. [백준] 1, 2, 3 더하기 문제 흐름문제 목표숫자 n이 주어졌을 때, 숫자 1, 2, 3을 사용해 그 합이 n이 되는 모든 경우의 수를 계산합니다.입력 및 출력 설명여러 테스트 케이스에 대해 각각의 숫자 n을 입력받고, 각 경우에 대해 결과를 출력합니다. 핵심 아이디어동적 프로그래밍(DP)현재 숫자 i를 만들기 위해 마지막에 추가하는 숫자가 1, 2, 또는 3일 때의 경우를 합산합니다.점화식: arr[i] = arr[i-1] + arr[i-2] + arr[i-3]여기서 arr[i]는 숫자 i를 만드는 경우의 수를 나타냅니다.이 문제는 미리 계산된 DP 배열에서 결과를 빠르게 조회하는 방식으로 해결할 수 있습니다. 알고리즘 흐름DP 배열 초기화arr[0]=1로 초기화합니다.배열을 통해 1부터 10까지의 결과를 미리 계산합니다.DP .. 이전 1 2 3 4 ··· 8 다음