문제접근가중치 O방향 O방향과 가중치가 있는 그래프이기 때문에 클래스를 활용한 인접리스트를 구현하였다.그 후에 모든 학생이 위치한 노드로부터 X(파티 장소) 까지로의 최단 거리와 X(파티 장소) 에서 다시 자신이 위치한 마을로 돌아가는 최단 거리를 합친 것 중 가장 큰 값을 출력해야 하기 때문에 다익스트라 알고리즘을 사용하였다.다익스트라 알고리즘은 그래프에서 하나의 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 동작하며, 음의 가중치가 없는 그래프에 적합합니다.다익스트라 알고리즘은 음의 가중치를 가진 그래프에서 사용할 수 없습니다. 음의 가중치가 있는 경우, 벨만-포드 알고리즘과 같은 다른 알고리즘을 사용해야 합니다.문제 풀이가중치 있는 ..

[백준 1167] 트리의 지름접근트리의 지름트리 내의 두 노드 사이의 가장 긴 경로이다.문제 풀이입력을 트리로 변환인접 리스트에 Point클래스 (목적지 노드, 가중치) 자료형 사용해서 가중치 있는 그래프 표현.DFS 를 통해서 1에서 가장 멀리 떨어진 노드 탐색가장 멀리 떨어진 노드를 기준으로 다시 DFS를 진행해서 트리의 지름을 구함.사용한 알고리즘DFS시간 복잡도O(n)막힌 부분.DFS를 통해서 가장 멀리 떨어진 노드를 탐색하는 것까지는 생각함.그 이후에 어떻게 지름을 구하는지에 대해서 막혔다.지름을 구하기 위해서 다시 DFS 탐색이 필요하다는 것까지 생각을 못했다.. ㅜㅜ2-1. 모든 경로의 경우의 수를 탐색해서 지름을 구하는 것도 생각했는데 이때 노드가 많아질수록 모든 경로를 탐색하는데 드는 시..

백준 16953 A -> B접근처음에는 이진 트리로 1차원 배열에 두 연산을 저장하면서 진행하려고 했으나 메모리 초과가 발생한다는 것을 깨닫고 방향을 전환하였다.BFS 를 통해서 B까지 도달할 수 있는 가능한 연산 횟숫를 찾고자 하였다.만약 가능한 연산이 없을 경우에는 -1을 출력해야 한다.전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ne..

구간 합 구하기 5참고 : https://www.acmicpc.net/problem/11660접근해당 문제는 이차원 배열에서 누적합을 구해서 주어진 구간의 합을 구해야 한다고 생각했습니다.map이라는 N * N 의 2차원 배열에 누적합을 계산해서 저장시간 복잡도 : O(N^2)(i열 , j-1행의 누적합) + (i-1열, j행의 누적합) - (i-1열, j-1행의 누적합) + (i열, j행)i 열 j 행 의 누적합은 아래 식을 통해서 구할 수 있습니다.주어진 구간에서의 합 구하기해당 과정을 통해서 점화식을 구하면 아래와 같습니다.- 코드를 구현할 때는 map, sumMap의 크기를 N+1로 해서 진행.전체 코드package baekjoon_day01;import java.io.*;import java.u..

문제문제1차 접근쿼터 : 0.25다임 : 010니켈 : 0.05페니 : 0.01** 거스름돈은 항상 $5.00 이하 **** 손님이 받는 동전의 개수 최소 **ex ) $1.24 거술러 주어야 한다면- 4 쿼터- 2 다임- 0 니켈- 4 페니그리디 알고리즘을 사용하여 우선적인 동전으로 처리하고 그 후에 나머지 동전들을 처리하는 로직으로 진행하였다.확인T = int(input())for test_case in range(1, T+1): price = int(input()) coins = [] while price > 0: for i in [25, 10, 5, 1]: a = price // i b = price % i p..

문제접근 방법정답 여부접근 방법1. queue 자료구조를 활용해서 회전마다 popleft를 횟수마다 해주고 다시 빼낸 것을 append하여 회전 때마다의 리스트를 구한다.2. 그 후 list를 잘라서 해당 숫자를 join 해 문자열로 만들어서 set 자료구조에 넣어서 중복이 없도록 한다.3. 해당 set을 리스트로 바꾸고 16진수를 10진수로 변경한다.4. 내림차순으로 sort한 후, K번째 수를 빼낸다.코드from collections import dequeT = int(input())for test_case in range(1, T+1): N, K = map(int, input().split()) lst = list(input()) n_set = set() count = N //..

문제1차 접근 방법정답 여부1차 접근 방법N * N 의 사이즈에서 각 칸 마다 파리의 숫자가 있는데 M * M 사이즈의 파리채를 통해 가장 많은 수의 파리를 잡아야 하는 것이 목적이다.이를 위해 N * N 배열을 순회하면서 M * M 사이즈만큼 확인해서 각 sum 을 구하고 그 가운데 최댓값을 구하는 방법을 고안하였다.그러기 위해서는 N - M + 1 범위까지만 순회하여도 M 사이즈 만큼은 다시 순회를 할 것이기 때문에 세로, 가로는 처음에 N - M +1 만큼 순회를 2중으로 순회를 하고,그 안에서 다시 M 만큼 가로, 세로 순회를 해야한다.그리고 M만큼 순회를 하기 전에 현재 파리채의 sum을 0으로 초기화하고 계산한 다음 max_sum과 비교하면서 최댓값을 정해야한다.아래가 구현 코드이다!!for문..

문제1차 접근 방법정답 여부1차 접근 방법방향을 잘 조절해서 2차원 배열 안에 1 ~ (N * N + 1)을 넣어주자.T = int(input())for test_case in range(1, T + 1): N = int(input()) print(f'#{test_case}') answer = [[0] * N for _ in range(N)] directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] direction_index = 0 x, y = 0, 0 # 시작 위치 for i in range(1, N * N + 1): answer[x][y] = i next_x, next_y = x + directions[..

[SWEA]1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (python)문제문제 풀이1차 접근 방법정답 여부2차 접근 방법정답 여부1차 접근 방법1차로 접근 했을 때는 배열을 순회하면서 현재의 index와 value에 대해서 index도 크고 가장 value가 큰 것을 변경하는 과정을 거쳐서 총 교환 회수에서 빼주었다.또한, 교환 횟수가 배열을 다 순회하고도 남았을 경우에 짝수 개수이면 49 -> 92 -> 49 (총 2회) 다시 제자리 값으로 돌아오기 때문에 넘겨주고, 홀수인 경우에는 중복 숫자가 있으면 짝수 개수처럼 처리하고, 중복 숫자가 없는 경우에는 마지막 두 자리 수를 변경해주었다.import syssys.stdin = open("1244_D3/input.txt", "r")from c..