알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving)77

• 백준 19644번: 좀비 떼가 기관총 진지에도 오다니 문제풀이 문제 설명기관총 사거리 ( M_L ): 기관총이 좀비에게 도달할 수 있는 거리 기관총 살상력 ( M_K ): 기관총이 좀비에게 주는 데미지 수류탄 개수 ( C ): 남은 수류탄 개수 진지 앞쪽 거리 ( L ): 좀비가 등장하는 총 거리 좀비 체력 ( Z_i ): 각 거리에서 좀비의 체력 좀비는 기관총 사거리 내에서 최대 ( M_K ) 데미지를 받습니다. 만약 이를 초과하는 체력이 남으면 수류탄을 사용해야 합니다. 수류탄이 없으면 게임은 실패(NO), 끝까지 방어할 수 있으면 성공(YES) 입니다. 문제 풀이 과정1. 초기 입력 설정import sysinput = sys.stdin.readlineL = int(input()) # 진지 앞쪽 거리M_L, M_K = map(int, input()... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 12. 7.

• 

  백준 20186번: 수 고르기 문제 풀이 문제 설명백준 20186번 "수 고르기" 문제는 주어진 수열에서 특정 개수의 수를 선택하여 최대 합을 구하는 문제입니다. 단, 선택된 숫자의 합에서 특정 공식을 활용한 감산값이 존재하므로, 이에 따라 최적화된 선택이 중요합니다.목차문제 요약 및 제약 조건풀이 아이디어코드 설명코드 분석최적화 방안1. 문제 요약 및 제약 조건입력:첫 줄: (N) (수열의 길이)와 (K) (선택할 숫자의 개수).둘째 줄: (N)개의 정수.출력:(K)개의 숫자를 선택해 얻을 수 있는 최대 합.감산 공식: 선택한 (K)개의 수의 합에서 (K \times (K-1) / 2)를 빼야 합니다.2. 풀이 아이디어그리디 알고리즘 활용:수열을 내림차순으로 정렬.가장 큰 수부터 (K)개를 선택해 합산.감산 처리:(1, 2, 3, \ldots.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 12. 6.

• 

  백준 1059번: 좋은 구간 문제 풀이 1. 문제 개요백준 1059번 좋은 구간 문제는 특정 정수 (n)을 포함하지 않는 좋은 구간을 찾아, 그 안에서 (n)보다 작은 숫자와 큰 숫자 사이의 조합을 구하는 문제입니다.주어진 숫자 리스트에서 (n)을 포함하지 않는 구간을 찾아 가능한 조합 수를 계산해야 하며, 수학적 사고와 간단한 구현을 요구합니다.2. 접근 방법입력 데이터 처리 및 정렬입력받은 리스트를 정렬하고, 정렬된 리스트의 인접한 수를 사용하여 (n)이 속한 구간을 찾습니다.구간 계산(l): (n)보다 작은 가장 큰 수 + 1(r): (n)보다 큰 가장 작은 수 - 1이 구간을 기준으로 (n)을 포함하지 않는 조합을 계산합니다.조합 공식(n)보다 작은 수에서 (n)보다 큰 수로 가는 조합: ((r - n + 1) \times (n - l.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 12. 5.

• 

  백준 20044번: Project Teams 문제 풀이 1. 문제 개요백준 20044번, Project Teams 문제는 주어진 개발자들의 능력치를 이용해 팀을 구성하고, 각 팀의 능력치 합 중 최댓값을 최소화하는 것이 목표입니다. 이를 효율적으로 해결하기 위해 정렬과 양 끝의 포인터를 활용하는 접근법에 대해 알아보겠습니다.2. 접근 방법문제를 효율적으로 해결하기 위해 다음과 같은 로직을 설계했습니다.정렬하기능력치 리스트를 오름차순으로 정렬하여, 가장 작은 값과 큰 값을 쌍으로 묶으면 팀 능력치의 최대값을 최소화할 수 있습니다.양끝 더해서 최솟값 계산각 팀의 능력치를 구하기 위해 정렬된 리스트의 양 끝 값을 더합니다.최솟값 비교 반복가능한 모든 팀 조합의 능력치 중 최대값의 최솟값을 구합니다. 이를 위해 NN번 반복하며 최솟값을 업데이트합니다.3. 구현 코드.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 12. 4.

• 백준 28353번: 고양이 카페 문제 풀이 1. 문제 개요백준 28353번, 고양이 카페 문제는 제한된 **최대 무게(K)**를 초과하지 않도록 고양이들의 무게를 조합하여 가능한 한 많은 쌍을 만들라는 문제입니다. 이를 효율적으로 해결하기 위해 정렬과 투포인터를 활용하는 방법에 대해 알아보겠습니다.2. 접근 방법문제를 효율적으로 풀기 위해 다음과 같은 방법을 사용했습니다.무게 정렬: 무게를 오름차순으로 정렬하여 작은 값과 큰 값을 비교하기 쉽게 만듭니다.투포인터 활용:양 끝의 포인터 l과 r을 설정합니다.두 포인터의 합이 최대 무게 K 이하이면 쌍을 만들 수 있으므로 둘 다 포인터를 좁힙니다.합이 K보다 크면, 오른쪽 포인터(r)를 줄여서 더 작은 값을 탐색합니다.종료 조건:두 포인터가 교차하면 반복을 종료합니다.3. 구현 코드# 입력 받기N, .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 12. 4.

• 

  [순열 사이클 분할] 백준 10451 순열 사이클 이번 포스트에서는 백준 10451번 문제인 "순열 사이클"을 파이썬으로 풀이한 방법을 공유하고자 합니다. 이 문제는 주어진 순열 내에서 사이클이 몇 개 존재하는지를 찾는 문제로, DFS(깊이 우선 탐색)를 활용하여 해결할 수 있습니다.순열 사이클 분할 설명순열 사이클 분할은 주어진 순열을 사이클 구조로 분해하는 과정입니다. 순열은 각 요소가 다른 요소로 매핑되는 일종의 함수입니다. 이때, 순환 구조(사이클)를 찾는다는 것은 해당 순열 내에서 자기 자신으로 돌아오는 경로를 찾는 것을 의미합니다.예를 들어, 순열이 다음과 같이 주어졌다고 가정합니다:( \text{순열} = [2, 3, 1, 5, 6, 4] )이 순열에서 사이클을 찾아보면:1 → 2 → 3 → 1 (사이클 형성)4 → 5 → 6 → 4 (사이.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [다익스트라] 백준 1753 최단경로 이번 포스팅에서는 백준 1753번 문제를 다익스트라 알고리즘을 활용하여 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 시작점에서 다른 모든 정점으로 가는 최단 경로를 찾는 문제로, 그래프 이론에서 자주 등장하는 문제 유형입니다.문제 설명주어진 그래프에서 시작점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 그래프는 방향성이 있으며, 간선마다 가중치가 부여되어 있습니다. 다익스트라 알고리즘은 이와 같은 가중 그래프에서의 최단 경로 문제를 효율적으로 해결할 수 있는 알고리즘입니다.다익스트라 알고리즘 개요다익스트라 알고리즘은 그래프 이론에서 가장 널리 사용되는 최단 경로 탐색 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서, 하나의 시작 정점으로부터 다른 모든 정점으로 가는 최.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [등차수열] 백준 2108 수들의 합 이번 포스팅에서는 백준 2108번 문제를 효율적으로 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 수 ( N )을 등차수열로 나타낼 수 있는 모든 경우의 수를 구하는 문제입니다. 특히 이 문제는 자기 자신을 포함한 수열을 고려하는 것을 요구합니다.문제 분석주어진 숫자 ( N )을 자기 자신도 포함하여 하나 이상의 자연수로 이루어진 등차수열로 나타낼 수 있는 모든 경우의 수를 찾는 것이 목표입니다. 수열의 길이가 1 이상인 등차수열을 찾는 과정에서 우리는 ( N )의 약수와 관련된 규칙을 활용할 수 있습니다.핵심 개념등차수열이란?: 등차수열은 연속된 수들의 합입니다. 예를 들어, 1, 2, 3, 4, 5는 모두 연속된 수들이므로, 그 합은 15입니다. 이 문제에서는 어떤 수 ( N )을 연속된 자연수들의.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2024. 8. 10.

• [자료구조/큐] 백준 18258 큐2 package 큐덱; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * push * pop * size * empty * front * back * 명령 수 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 18.

• 

  [누적합]백준 25682 체스판 다시 칠하기 2 package 누적합; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class boj_25682_체스판다시칠하기2 { private static int N, M, K, answer; private static String[][] board; private static int[][][] accSum; public static void main(String[] args) throws IOException { // 1. M x N 크기의 2차원 배열 입력 // 2. 검, 흰 두 가지의 색으로 칠해져 있음 // 3. 아무 곳을 기준으로 K x K 만큼 자르기 // 4. 칠해야 하.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 7.

• 백준 16430 제리와 톰 package 단순구현; import java.util.Scanner; public class boj_16430_제리와톰 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); int B = sc.nextInt(); System.out.print(B-A +" " + B); } } 해당 문제는 다른 문제를 풀다가 머리 식힐겸 풀게된 문제인데 문제는 마치 나눗셈을 유도하는 듯 하지만 나누기연산의 개념이 다른 컴퓨터 내부작동 원리를 어떻게 해결할 지 물어보는 문제 같다. 1kg 기준으로 기약분수 꼴로 나눠야 하므로 결국 1 * B - A / B를 묻는 거나 다름이 없기에 B-A와 B를.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 5.

• [큐] 백준 15828 Router package 큐덱; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class boj_15828_Router { private static Queue router; public static void main(String[] args) throws IOException { router = new LinkedList(); int routerSize, packetCount = 0; BufferedReader br = new BufferedReader(new InputStreamReade.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 3.