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

문제1707번: 이분 그래프들어가며걸린 시간2시간성공 여부X 꽤 근접하게 접근했는데 더 예외가 있을 줄은 몰랐다..괜히 정답률 25 퍼센트 문제가 아니다.코드package m03.d29;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class 이분_그래프_1707 { private static ArrayList> graph; private static int[] color; // 0: 미방문, 1: 첫 번째 색상, 2: 두 번째 색상 public static..

문제5639번: 이진 검색 트리들어가며재귀적으로 접근해야겠다고 생각은 했는데너무 어렵게 생각해서 오른쪽 서브 트리 처리에서 막혔었다.하지만, 단순하게 보면 풀 수 있는 길이 있었다. 코드import java.io.IOException;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class 이진검색트리_5639 { static List numbers = new ArrayList(); public static void main(String[] args) throws IOException { Scanner scanner = new Scanner(System.in); while..

들어가며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번: 철로들어가며이 문제는 선형 탐색으로 풀면 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번: 뱀 들어가며뱀의 머리를 저장할 생각을 처음부터 왜 못했을까..코드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번: 가운데를 말해요들어가며대충 우선 순위 큐를 쓰는 건 짐작했으나, 두 개를 써야할 줄은 상상도 못했다. 코드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번: 원 영역들어가며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..

문제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으로 기존 값을 교체 ..