내가 올리고 싶은대로 올리는 개발 블로그

[알고리즘]크루스칼 알고리즘 자바 구현법

들어가며1197번: 최소 스패닝 트리위 문제를 풀면서 최소 스패닝 트리를 만드는 크루스칼 알고리즘을 작성해보았다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;public class 크루스칼 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in))..

[백준] 13334- 철로 문제 풀이(자바,Java)

문제13334번: 철로들어가며이 문제는 선형 탐색으로 풀면 O(N^2)으로 시간 초과가 발생한다.그렇기에 다른 방식을 탐색해야 하는데 우선순위 큐를 사용해서 풀 수 있다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.PriorityQueue;public class 철로_13334_3 { public static void main(String[] args) throws IOException { Buff..

[백준] 3190- 뱀 문제 풀이(자바,Java)

문제3190번: 뱀 들어가며뱀의 머리를 저장할 생각을 처음부터 왜 못했을까..코드package m03.d25;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Queue;public class 뱀_3190 { static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}}; public static void main(String[] args) throws IOException { ..

[백준] 1655- 가운데를 말해요 문제 풀이(자바,Java)

문제1655번: 가운데를 말해요들어가며대충 우선 순위 큐를 쓰는 건 짐작했으나, 두 개를 써야할 줄은 상상도 못했다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Collections;import java.util.PriorityQueue;public class 가운데를_말해요_1655_3 { static StringBuilder result = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new B..

[백준] 10000 - 원 영역 문제 풀이(자바,Java)

문제10000번: 원 영역들어가며5시간 넘게 쳐다봤던 것 같다..그럼에도 못 풀었다.아직 플레는 멀었다..화이팅코드package m03.d24;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Stack;public class 원의영역_10000_3 { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

[백준] 2439 - 탑 문제 풀이(파이썬,Python)

문제2493번: 탑들어가며이 문제는 스택으로 풀 수 있다. 처음 접근은 이전에 풀었던 히스토그램처럼 접근했더니가볍게 출력초과(시간초과)가 반겨주었다. 코드import sysinput = sys.stdin.readlinen = int(input().strip())towers = list(map(int, input().strip().split()))stack = []result = [0] * n # 결과를 저장할 리스트 초기화for i in range(n): # 현재 탑보다 낮은 탑은 스택에서 제거 while stack and towers[stack[-1]] 풀이스택에는 현재까지 처리된 탑들의 인덱스를 저장한다.현재 탑의 높이가 스택에 저장된 마지막 탑의 높이보다 크면, 해당 탑은 신호를 받을 ..

문제6549번: 히스토그램에서 가장 큰 직사각형들어가며플레의 벽은 높았다.. 코드def largest_rectangle(histogram): stack = [] # 스택에는 인덱스를 저장합니다. max_area = 0 # 최대 넓이를 저장할 변수 n = len(histogram) for i in range(n): # 현재 높이가 스택의 최상단 높이보다 작으면 넓이를 계산합니다. while stack and histogram[stack[-1]] > histogram[i]: height = histogram[stack.pop()] # 스택에서 꺼낸 높이 width = i if not stack else i - stac..

문제11053번: 가장 긴 증가하는 부분 수열 들어가며DP 문제의 대표격이다.하지만, 이 문제는 이분 탐색으로도 풀 수 있다.이 글은 이분 탐색으로 어떻게 푸는지에 대한 이야기이다. 코드from typing import MutableSequencedef lis_binary_search(arr : MutableSequence): lis = [] # LIS 배열 초기화 for num in arr: pos = binary_search(lis, num) if pos == len(lis): lis.append(num) # num이 가장 크다면 추가 else: lis[pos] = num # num으로 기존 값을 교체 ..

문제2470번: 두 용액들어가며이분 탐색으로 접근할려고 했는데, 아무리 생각이 안나서 투포인터로 풀었다.코드n = int(input())arr = list(map(int,input().split()))arr.sort()pl = 0pr = n-1result_nums = []best_sum = 10000000000# 끝점 두 개가 음수if arr[pl] 0 and arr[pr] > 0 : print(f"{arr[pl]} {arr[pl+1]}")# 끝점 두 개가 서로 혼합else : while pl 0: pr -= 1 # 합이 정확히 0이라면 최적이므로 종료 else: break print(f"{result[0]} {resul..

문제2110번: 공유기 설치 들어가며정말 머리가 터질 뻔한 느낌을 오랜만에 받은 문제이다.들어가기 전에 이 문제가 이분 탐색이라는 것을 알고 있어서 최대한 이분 탐색을 사용해서 풀려고 했다.근데 아무리 봐도 어디가 이분 탐색인지 안보였다.답답해 미칠 뻔 했다.아직까진 갈 길이 참 멀지 않나 싶다.. 화이팅 코드l = list(map(int, input().split()))n = l[0]c = l[1]arr = []for _ in range(n): arr.append(int(input()))arr.sort()result = 0left = 1right = arr[-1] - arr[0]while left = middle: cnt +=1 last_installed ..