hw.dev

https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 📌 해결 과정 우체국은 마을에 설치 하는 것이고, 우체국과 각 마을까지의 거리가 아니라 각 마을에 사는 사람들과의 거리 합을 기준으로 설치 할 위치를 정해야함에 유의해야 한다. 따라서, 설치 할 위치에 영향을 주는 것이 거리가 아닌 사람 수 임을 알 수 있다. 핵심은, 현재 마을의 양 옆에 마을 사람들의 수가 가장 ..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 📌 해결과정 정말 삽질을 길게 했던 문제다,, 우선 탐색을 하기 전 구멍이 뚫린 영역을 찾아서 그 영역을 2로 바꾼다. 그 다음 탐색을 하는 과정에서 4방향 중에 공기와 닿는 치즈가 있으면, 즉 4방향 중에 0인 좌표가 있으면 녹이려고 했다. 하지만 이 과정은 문제가 많다. 구멍을 뚫린 영역만 찾아서 2로 바꾸는게 정말 쉽지 않다. 그래프의 각 좌표를 방문 하다가, 값이 1인 좌표를 만난다 -> 방문해서 ..

https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 📌 해결과정 우선 문제를 읽고 문제를 풀기위해 필요한 조건들을 정리했다. 학생들의 질투심을 최소화 한다 = 한 학생이 갖는 같은 색상의 보석의 갯수를 최소화 한다 1. 모든 보석을 남김없이 학생들에게 나누어 줘야한다. 2. 한 학생은 같은 색상의 보석만 가질 수 있다. 3. 보석을 갖지 못하는 학생이 있을 수 있다. 어떻게 풀어야 할지 감을 잡지 못하다가 두번 째 예시를 통해서 힌트를 얻고 풀었다...

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 📌 시간을 많이 쓴 이유 시간초과를 해결하느라 시간을 좀 많이 썼다.. pypy3 으로 제출해도 시간초과가 나서 음..큰일났네 생각하고 문제점을 찾기 시작했다. 시간초과 해결순서 iceberg_melts() 라는 함수를 만들어서 1년마다 그래프를 돌면서 상하좌우에 0이 있으면 -1 을 해준다 -> visited 2차원 배열을 만들어서 중복해서 녹일수 없도록 한다 -> year를 1증가지키고 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 📌 해결 과정 heap 자료구조의 장점을 정말 잘 느낄수 있는 문제이다. 먼저, 그리디 방식으로 이 문제에 접근해보면 비교횟수의 최솟값을 구해야 하므로 언제 비교횟수가 크게 증가하는지에 대해 생각해볼 필요가 있다. 카드 수가 많은 묶음일수록 최대한 마지막에 비교할 수 있도록 해야한다 예를 들어서, 묶음의 수 : 6 각 묶음에 속한 카드 : [20, 30, 40, 50, 60, 80]..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 📌 해결 과정 https://hwdev.tistory.com/15 [백준] 파이썬 1697 : 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동 hwdev.tistory.com 이 문제와..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 📌 해결순서 회의실 배정 [백준] 파이썬 1931 : 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실.. hwdev.tistory.com 신입사원 [백준] 파이썬 1946 : 신입사원 https://www.a..

https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 시험기간이지만 알고리즘을 풀고 싶었다,, 사실 CS 재미도 없고 하기 싫어서 풀었다 ㅎㅎ,, 죄송합니다 출처 다 읽고 해결과정 노트에 적고 '어.. 이거 쉽게 풀겠는데? 왜 골3이지' 이 생각 했는데 시간초과 📌 해결순서 2번째 예시를 이용하면 파란색 동그라미를 친 7 + 24 + 38 = 69 가 토끼가 먹을수 있는 당근의 맛 최대 합이다. 토끼는 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📌 해결순서 이번에 풀 때도 마찬가지로 times 배열을 만들어서 방문 표시와 걸리는 시간의 표시를 같이 묶어서 하려고 했는데 이 문제에서는 그렇게 하면 안된다. 5에서 첫 번째 이동을 예시로 들면 (4, 6, 10) 으로 이동할 수 있는데 4, 6 은 시간이 +1 되기 때문에 상관이 없지만 10은 방문 했음에도 불구하고 +0을 하기 때문에 여전히 방문하지 않은것..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 복잡해 보이는 것 같지만, 사실 이전에 풀어봤던 안전영역과 유기농 배추 등등,, 의 기본 그래프 탐색 문제와 비슷하다 근데 좀 오래 걸렸는데 변명 아닌 변명을 좀 해보자면.. 1. 문제에서 좌표를 주길래 2차원 배열을 만들 때, 행과 열에 주어진 m, n에 각각 + 1 을 했음 2. 하지만 만든 배열의 인덱스만 사용해도 되는 문제였다,, 좌표가 아닌 영역을 묻는 문제이기 때문에..