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

[백준] 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 - 히스토그램에서 가장 큰 직사각형 문제 풀이(파이썬,Python)

문제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- 가장 긴 증가하는 부분 수열 문제 풀이(파이썬,Python)

문제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 - 두 용액 문제 풀이(파이썬,Python)

문제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 - 공유기 설치 문제 풀이(파이썬,Python)

문제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 ..

문제9663번: N-Queen 들어가며대각선에 대해 많은 고민을 하다가 너무 시간을 많이 쓰다 못 푼 문제였다.백트래킹 참 어렵다...  코드n = int(input())ans = 0row = [0] * ndef is_promising(x): for i in range(x): if row[x] == row[i] or (row[x] + x == row[i] + i) or (abs(row[x] - row[i]) == abs(x - i)): return False return Truedef n_queens(x): global ans if x == n: ans += 1 return for i in range(n): ..

문제10971번: 외판원 순회 2들어가며문제의 중요한 점을 뽑자면 다음과 같다1번부터 N번까지 N개의 도시가 있음.특정 도시에서 다른 도시로 이동하는 비용이 2차원 배열로 주어짐.모든 도시를 한 번씩 방문한 후, 다시 출발 도시로 돌아오는 경로 중 최소 비용을 구해야 함.어떤 도시 A에서 도시 B로 갈 수 없는 경우 비용이 0으로 표시됨. ➡ 출발 도시는 정해져 있지 않고, 어떤 도시에서든 출발할 수 있음.➡ 비용 행렬이 주어지며, 이 행렬은 대칭이 아닐 수도 있음(즉, cost[A][B] ≠ cost[B][A]). 돌아오는 경로 중에 계산해야 하므로 백트래킹으로 접근할 수 있다.코드n = int(input())arr = []visited = [False] * nresult = 1000000000for..

문제2468번: 안전 영역 들어가며문제를 잘 읽어봐야 한다.빗물이 차오르는 높이는 딱히 정해져있지 않고, 그 수 많은 빗물이 차오르는 높이 중에서 어느 높이일 때, 만들어지는 안전 구역 개수의 최대값이다.즉, 높이는 0 ~ 최대 안전구역 높이 라고 말할 수 있다.또한 구역의 개수라고 하면 바로 감이 오시는 사람이 있을 것이다. bfs 또는 dfs 문제이다. 코드from collections import dequen = int(input())directions = { (0, 1), (0, -1), (1, 0), (-1, 0) }visited = [[False] * n for _ in range(n)]arr = []arr_max = 0for _ in range(n): numbers = list(map(..