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

[백준] 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 ..

벌써 들어온지 2주일이 되어간다..0 주차 땐, 미니 프로젝트를 만드는 것이 주된 내용이었다.1주차부턴 매주 바뀌는 팀들과 함께 알고리즘 및 CS 학습을 진행한다.그리고 CS와 백준 문제 시험으로 1주일을 마무리한다. 앞으로 이렇게 좋은 팀이 있을까?자리에 딱 앉아서 이야기를 하는데, 나이가 서로 다 같았다.여기서 99즈를 만들 줄은 정말 몰랐지만, 신기했었다.그리고 관심사도 비슷비슷하고 열정은 강의실 전체에선 최고라고 말해도 될 정도였다.언제나 새벽 1~2시 정도까지 강의실에 남아서 자습을 같이 할 정도였다.주 100시간 공부는 무슨 110시간 넘게 도달했었다.정말 체력적으로 힘들었지만, 강의실에 우리 팀만 남아있는 모습을 보며 더 열정을 불태웠었다. 밤 샌 덕분에 오랜만에 눈도 보고 눈사람도 만들고 ..

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