백준 (61) 썸네일형 리스트형 [백준] DFS 스페셜 저지 (16964번) 1. 문제 해석사용자가 DFS를 통해 정답을 제출했을 때 복수의 정답을 채점하는 경우의 알고리즘을 짜는 문제이다즉 답이 여러 개일 경우 해당 제출한 답이 맞는지 확인하는 코드를 작성하는 문제이다 2. 사용되는 자료구조Set[] 인접 리스트 사용목적 : 노드끼리 연결된 노드들만 저장하기 위해 사용이유 : 인접 행렬(int[][])를 사용했을 때 공간 복잡도에 걸림또한 List[]를 사용했을 때 해당 노드에 접근하는데 시간복잡도(73%에서 걸렸습니다)가 걸림Stack목적 : 사용자가 입력한 값을 이용하여 해당 노드로 접근이 가능한지 파악할 때 접근을 할 수 없다면 이전 노드로 돌아가야 하기 때문이유 : 매개변수로 제어해볼려고 했었지만 이전의 이전 노드를 저장할 수 없어 사용하게 되었음 3. 핵심 아이디어최초.. [백준] 후위 표기식 (1918번) 후위 표기식(Reverse Polish Notation, RPN) 변환 방법1. 후위 표기식이란?일반적으로 우리가 사용하는 수식은 중위 표기식(Infix Notation)입니다.예를 들어:중위 표기식: A + B * C후위 표기식: ABC*+후위 표기식은 연산자가 피연산자 뒤에 위치하는 표기법으로, 괄호 없이도 연산 순서를 명확히 표현할 수 있습니다. 2. 사용되는 자료구조후위 표기식으로 변환할 때는 스택(Stack)과 큐(Queue) 를 활용합니다.스택(Stack): 연산자를 저장하는 용도로 사용됩니다.큐(Queue) 또는 문자열: 변환된 후위 표기식을 저장하는 용도로 사용됩니다.이유연산자는 우선순위에 따라 LIFO(Last-In-First-Out, 후입선출) 구조인 스택에 저장해야 합니다.피연산자와 .. [백준] 숫자놀이 (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.. 이전 1 2 3 4 ··· 8 다음 목록 더보기