본문 바로가기

분류 전체보기702

[백준 21612] Boiling Water [Python] 풀이 물이 끓기 시작하는 온도(B)를 입력받아서, 기압(P)과 이를 통해 알 수 있는 해수면으로부터의 위치를 출력해주면 된다. 소스코드 소스코드 보기 출처 21612번: Boiling Water At sea level, atmospheric pressure is 100 kPa and water begins to boil at 100◦C. As you go above sea level, atmospheric pressure decreases, and water boils at lower temperatures. As you go below sea level, atmospheric pressure increases, and water boils www.acmicpc.net 2023. 6. 22.
[백준 1647] 도시 분할 계획 [Python] 풀이 N개의 집들에 대해 2개의 그룹으로 나누고, M개의 길에 대해, 유지비가 최솟값이 되도록 집들을 연결해주면 된다. 단순하게 접근해보자. Minimum Spanning Tree 문제를 풀이할 때, N개의 정점에 대해서 가중치를 기준으로 미리 정렬된 N - 1개의 간선으로 모든 정점을 연결할 수 있다는 사실을 알고있다. 그렇다면, N개의 집들을 2개의 그룹으로 나누는 가장 단순한 방법은 무엇일까? 바로, N - 2개의 간선만 이용해 N - 1개의 정점을 연결해주면 된다. 가중치에 대해 오름차순으로 정렬하고, 최소 가중치를 우선적으로 연결하는게 이득인점을 이용한 풀이다. 소스코드 소스코드 보기 출처 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,00.. 2023. 6. 22.
[백준 21631] Checkers [Python] 풀이 흰/검정 색 체커칩으로 탑을 쌓아서 얼룩말 줄무늬를 만들때 검정색 줄의 최대 갯수를 구하는 문제이다. 검정색 줄의 최대 갯수를 구할 때, 연속된 부분은 한 개로 취급한다는 점을 유의하자. 흰 색(a)이 검정색(b) 이상이라면 b개만큼 최대로 만들 수 있다. 만약 그렇지 않다면 검정색은 겹치는 구간이 생길것이고, 결국 흰색(a) + 1 개만큼의 줄무늬만 만들어진다. 소스코드 소스코드 보기 출처 21631번: Checkers The only line of input contains two integers $a$ and $b$ --- the number of white and black pieces, respectively ($0 \le a, b \le 10^{18}$). www.acmicpc.net 2023. 6. 22.
[백준 25192] 인사성 밝은 곰곰이 [Java] 풀이 새로운 사람이 오픈 채팅방에 입장하면 "ENTER" 이라는 문자열이 입력된다. 그 이후로 곰곰티콘을 사용한 사람이 총 몇명인지를 구하면 되는 문제이다. 즉, 새로운 사람이 들어온 후 곰곰티콘을 사용한 사람의 수를 구하면 된다. 일반적으로 채팅한 모든 사람들에 대해 몇 번 채팅했는지 살펴보는 방법은 O(N^2), N이 100,000이기에 시간초과가 발생할 것이다. 따라서 O(1) 만에 이미 채팅이력이 있는지 확인을 해주어야 한다. map과, set을 사용한 풀이들을 소개한다. HashMap 먼저 이름을 저장할 HashMap으로 nameList를 선언해주자. 누가 몇 번을 채팅했든 상관없이, 1번이라도 채팅했다면 곰곰티콘을 사용한 채팅이 아닌 평범한 채팅 기록이기 때문에 횟수를 계산할 필요가 없다. 때.. 2023. 6. 20.
[백준 2096] 내려가기 [Python] 풀이 문제에서 주어진 규칙에 따라 N줄을 내려가면서 최댓값과 최솟값을 구하면 되는 문제다. 주어진 규칙을 살펴보자. 별의 위치에 따라 더하거나 뺄수 있는 칸의 범위가 달라진다. 이번에는 아래 그림을 살벼보자 별이 기준이 아닌, 동그라미를 기준으로 각각 빨,초,파의 선을 그었다. 첫 번째 칸에 위치한 동그라미는 첫 번째와 두 번째의 별에 대해 더하거나 뺄 수 있다는 의미이다. 앞으로 계산해야되는 칸을 각각 max_dp, min_dp에 담아주자. 1번 줄은 그대로 담으면 된다. 2번 줄 부터 N번 줄까지는 위에서 말했듯 동그라미를 기준으로 계산하듯이 계산해주면 된다. 각각 max_dp와 min_dp를 구하는 코드이다. 코드가 너무 길다고 생각된다면 아래처럼 쌍으로 묶어주어 관리해도 된다. dp[0] = [ .. 2023. 6. 18.
[백준 1865] 웜홀 [Python] 풀이 가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서 출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다. 특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다. 때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다. 만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다. 좀 더 빠르게 탐색해보자. 어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 .. 2023. 6. 17.

티스토리툴바