안녕

0. 문제 링크 https://www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net 1. 풀이 방법 눈 씻고 봐도 쌩구현 문제 (+정정, 구현 아니고 탐색 관련 문제였음) 가장 중요한건 인접한 키를 찾는 로직이 가장 중요하다. 이때 Linear로 인접한 키를 구하는 순간 시간 초과가 난다. 따라서 다른 방법으로 탐색해야 한다. 나는 이진 탐색을 골랐다. 아마 더 좋은 방법이..

0. 문제 링크 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 1. 풀이 방법 우선순위 큐를 3개나 사용해서 풀었음 첫 번째는 시작 시간 순서대로 정렬한 리스트 - A 두 번째는 끝나는 시간을 기준으로 정렬한 리스트 - B 세 번째는 자리의 번호를 정렬한 리스트임 - C A에서 시간을 뽑음 그리고 B에 넣고, C에서 가장 작은 자리의 번호를 추출함 그 다음에..

0. 문제 링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 풀이 방법 우선 빙산의 녹음을 구현한 함수인 melt()와 그룹화하는 함수인 group() 함수를 구현했다. 그리고 빙산 근처에 바다의 개수를 세는 adj도 따로 만들어서, 빙산 근처에 몇 개의 바다가 있는지 셌다. melt() 함수를 사용하고, 다시 인접한 바다의 개수를 셌다. 만약 특정 빙산이 모두 녹았다면 해당 빙산은 adj 딕셔너리에서 pop 하였다. group(..

0. 문제 링크 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 풀이 방법 해당 문제에서 물고기의 값과 이동 방향은 복소수로 하나로 묶었다. 근데 딕셔너리를 쓰면 더 간단하게 풀 수 있을 것 같긴했는데, 이미 복소수로 묶어놔서 그냥 복소수로 풀었다. 우선 물고기의 움직임을 구현함 함수인 fish_move() 함수와 상어가 갈 수 있는 좌표를 반환하는 can_shark_move() 함수를 구현했다. maps는 물고기와 상어..

0. 문제 링크 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 1. 풀이 방법 비트마스킹으로 문제를 풀었음 특별한 점은 없음 주석 처리를 자세히 해놓았으므로, 코드를 보면 이해할 수 있음 2. 코드 import sys def goto_board(*args): # 넣을 수 있는 자리를 찾는 함수 max_cnt = 7 for i in range(6): for val in args: if val & 1 = 1 for color in [g..

0. 문제 링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 풀이 방법 의외로 방법은 심플하다. 그냥 row, col, 3 * 3 구역 내에서 넣을 수 있는 숫자를 찾으면 된다. 그리고 그 방식으로 DFS를 했다. 근데 문제는 이런 방식으로 했을 때, 스도쿠가 전부 채워지지 않으면 다시 넣을 수 있는 숫자를 찾아야 하는 것... 분명 다른 방법이 있을텐데, 나는 해당 방법 말고는 딱히 떠오르지 않았다. 아무튼 이렇게 하니까 시간 초과가..

0. 문제 링크 https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 1. 풀이 방법 해당 문제의 알고리즘은 구현이지만, 사실 가만 보면 분할 정복 문제와 다를 것이 없다. 방법은 별거 없다. 맨 왼쪽 빵보다 왼쪽에 있으면 패티가 없다. 중간 패티라면 왼쪽 패티 갯수를 넣는다. 왼쪽 빵과 중간 패티 사이라면 분할 정복으로 왼쪽만 분할 정복으로 넣는다. 오른쪽 빵과 중간 패티 사이라면 왼쪽 패티 갯수를 더하고 오른쪽을 햄버거를 분할 정..

0. 문제 링크 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 1. 풀이 방법 우선 배열을 돌린다, 회전한다 뭐 이런거는 너무 오래 걸릴 것 같았다. 그래서 12시 방향을 시작점으로 하고, 그 좌표를 저장하는게 좋아보였다. 그래서 결국엔 다 풀었는데, 뭔가 마지막 예제가 계속 안 됐었다. 알고보니까 인접한 모든 애들을 없애야 하는 것이 있었다. 여기서 다시 BFS로 풀자니 푼 시간이 아깝고, 다시 구현하기도 귀찮았다. 그래서 ..

0. 문제 링크 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 1. 풀이 방법 딱히 어려운 점은 없었음 클래스를 이용해서 각 말에 대한 인스턴스를 생성하여 처리하였음 굳이 클래스를 이용하지 않아도 될 것 같은데, 뭔가 클래스로 하는게 직관적일 것 같았음 클래스를 쓰지 않았으면 코드를 더 줄일 수 있었을 듯, 그래도 더 직관적임 2. 코드 from collections import deque class Chess: def __init__(sel..

0. 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. 풀이 방법 사실 구현은 그냥 하라는 대로 하면 돼서 크게 어렵지는 않은 것 같다. 먼지를 분산시키고, 이후에 바람을 불었다. 다만 바람을 부는 과정이 조금 쉽지 않았는데, 방향을 전환하면서, 현재 값은 이전 값이 저장된 변수로 대체하고, 현재 값을 변수에 넣는 과정을 반복하면 해결되었다. 2. 코드 r, c, t = map(int, input().split()) maps =..