무니화니

생각보다 너무 어려웠던 DFS 문제이다. DFS알고리즘은 계속 배워도 쉽지않은 것 같다. 저번에 풀었던 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제와 유사한 것 같다. 코드는 다음과 같다. import sys input=sys.stdin.readline def dfs(v,i): visited[v]=True w=data[v] if not visited[w]: dfs(w,i) elif visited[w] and w==i: result.app..

이번 문제는 사실상 조금 어이 없게 틀린 문제여서 적어보고 싶었다. 사실 알고리즘 구현은 매우 쉬웠는데, 반올림을 생각을 안 해서 틀렸다. import sys sys=sys.stdin.readline n,k=map(int,input().split()) data=[float(input()) for _ in range(n)] data.sort() jeol=(sum(data[k:n-k]))/(n-2*k) print("%.2f" %(jeol+1e-8)) bo=(sum(data[k:n-k])+data[k]*k+data[n-k-1]*k)/n print("%.2f" %(bo+1e-8)) 코드는 다음과 같이, 절사평균은 양 쪽을 제외한 평균, 그리고 보정평균은 남은 양 끝의 값을 변경시켜서 넣었다. 하지만 계속 틀려서..

'베낭 문제'라는 알고리즘이 있다. 문제의 예시를 그려봤다. 분홍색 하이라이트가 정답이 나온 Path이고, 하늘색이 들고갈 수 있었던 짐을 들고 갔을 때를 의미한다. 지금 위치하고 있는 '들 수 있는 무게'가 짐의 무게보다 크다면, 짐의 무게를 들 수 있다는 뜻이기 때문에, 전 예시에서 현 위치만큼 '들 수 있는 무게'와 새로운 짐을 더한 무게 중 더 가치가 큰 것을 고른다. 분홍색 화살표를 따라서 보자. 4라는 무게일 때, 무게 4, 가치 8인 물건을 들 수 있다. 그래서 전까지 4라는 무게에서 들었던 가치와, 새로운 물건을 들었을 때의 가치를 비교한다. 그래서 0과 8을 비교해서, 8이라는 값이 나오는 것이다. 또한, 8에서 14가 될 때는, 7이라는 무게일 때, 무게 3, 가치 6짜리 물건을 들 수..

Dynamic Programming 문제인 LCS이다. 굉장히 웰-노운 문제인 것 같은데, 아이디어를 떠올리기 힘들었다. 극한의 시간 제한 때문에, 일반적인 반복문으로 구할 수 없었다. 내가 사용한 DP 알고리즘은 다음과 같다. 우선 모든 칸을 0으로 채우고, 만약 두 문자열에서 같은 문자가 나오면, '해당 문자 전까지 찾았던 문자열의 공통 부분'에서 1을 더해준다. 예시를 들면, ACA와 CA가 겹치는 부분을 보자. (좌표 (3,2)) AC까지와 C까지 겹치는 부분이 1이였다. ('C') 근데 이제 ACA와 CA가 겹치기 때문에, AC까지와 C까지 겹치는 부분인 1에 1을 더한다. ('ACA와 CA'가 겹치는 부분이 2니까...!) 만약 두 문자가 같지 않다면, 전까지 비교했을 때 중에서 더 겹치는 부..

import sys input=sys.stdin.readline import heapq n=int(input()) data=[list(map(int,input().split())) for _ in range(n)] location,p=map(int,input().split()) heapq.heapify(data) possibleGas=[] answer=0 while p

오늘의 문제는 책 나눠주기라는 문제이다. 알고리즘은 그리디를 사용했다. 생각보다 쉬워 보였는데, 많은 시도를 통해 정답을 찾았다. 문제는 다음과 같다. 알고리즘 설명 문제의 예시와 같은 그림이다. (1부터 2까지 중에 책을 원하는 사람이 3명인 경우) 이 모든 데이터를, 끝나는 지점이 일찍 나올수록 앞쪽으로 오게 sorting을 했고, 그리고 그 중 더 빨리 시작하는 숫자로 다시 sorting을 하여, 데이터들을 보면서 맨 앞 번호부터 나열을 시도했다. '왜 뒤부터 나열을 하였는가? 앞에서부터 해도 사람들이 책을 받지 않나?'라는 질문이 생길수도 있는데, 해당 경우를 보자. 3명의 사람들 중 1부터 4까지 원하는 사람 2명, 2만 원하는 사람 2명인 경우이다. 왼쪽 경우는, sorting을 시작부터 한 ..

굉장히 직관적인 문제라고 생각했는데, 너무나도 어려운 Dynamic Programming 문제였다. 가방의 개수, 그리고 각 가방에 담을 수 있는 무게가 정해져 있다. 최대의 value를 가지는 보석들을 가방에 넣어서 훔치는게 목표이다. 출력은 총 훔친 보석들의 value이다. import sys import heapq input= sys.stdin.readline n,k=map(int,input().split()) weightandvalue=[list(map(int,input().split())) for _ in range(n)] maxweight=[int(input()) for _ in range(k)] weightandvalue.sort() temp=[] answer=0 for bag in maxw..

골드 2의 난이도를 자랑하는 '가운데를 말해요'라는 문제이다. 문제의 내용은 간단하다. 모든 input이 들어올 때 마다 아직까지 들어온 input들의 중앙값을 출력해주면 된다. 하지만 정말 큰 문제는 해당 문제의 시간 제한이 0.1초이라는 점이다. 그렇기 때문에, 단순히 input이 들어올 때 마다 sort를 해서 중앙값을 출력해주면 너무너무 느려진다. 그래서 최소 및 최대 힙을 사용해서 이 문제를 풀어보았다. import heapq import sys input=sys.stdin.readline maxHeap=[] minHeap=[] n=int(input()) for i in range(n): num=int(input()) if len(maxHeap)==len(minHeap): heapq.heappu..

Heap이란? 최소 힙의 예시이다. 위에 있는 부모 노드보다 밑에 있는 자식 노드가 더 큰 노드이다. 맨 위에 있는 수를 제외하고는 자식이 부모보다 큰 조건을 만족 시키면서, random하게 sort 되어 있는 모습이다. 그렇기에 '반정렬' 상태라고 명한다. 최대 힙은 부모보다 자녀의 크기 작은 경우이다. heapq 라는 module을 통해 구현할 수 있고, 일반적인 배열 형태로 heap을 구현하기에 단순한 list에 heapq의 함수들을 사용하면 heap으로 이용할 수 있다. 코드 import sys import heapq input=sys.stdin.readline n=int(input()) data=[int(input()) for _ in range(n)] heapq.heapify(data) ans..

이번 문제는 공유기 설치라는 문제이다. 이 문제 또한 집의 개수가 매우 많을 수 있고, 좌표의 범위도 매우 넓다. 그렇기에 이중 for 문을 써서 풀 수도 있지만, 2초라는 시간 제한에 걸려서 시간 초과가 뜰 것이다. 알고리즘 해설 이분 탐색을 통해 풀었다. 코드 n,c=map(int,input().split()) data=[int(input()) for _ in range(n)] data.sort() l,r=0,data[-1]-data[0] res=0 while l=mid: answer+=1 curr=i if answer