Hanbit the Developer

https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net > 접근 세그먼트 트리의 노드 형식을 [VALUE, INDEX]으로 맞추고 초기화 함수, 업데이트 함수만 구현해주면 된다. 어차피 전체 범위에 대해서만 쿼리를 하므로 쿼리 함수는 따로 구현하지 않고 seg_tree[1]를 참조하기만 해도 된다. + 제목을 보고 무작정 세그먼트 트리로 풀 생각만 했었는데, 전체 범위에서 가장 작은 값을 찾는 것..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net > 풀이 구현만 하면 되는 문제였다. 다음과 같은 사항들을 구현하여 문제를 해결하였다. - C의 값들을 담은 grid를 사전에 계산해둔다. BFS로 방문 가능한 같은 숫자인 좌표들을 set에 담고 마지막으로 set을 돌며 set의 length 값을 넣어주었다. 이 때 좌표를 하나의 정수로 인코딩(ex. (2,3) 2*5 + 3 = 13) 하였는데, 이 set을 통해 중복 방문 체..

https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net > 접근 초기에는 N

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net > 접근 예제 입력 2의 대소관계를 그래프화하면 다음과 같다.(4-5는 생략하였다.) 여기서 결과를 직접 그려가면서 계산을 해본 결과, 한 방향으로의 탐색을 위, 아래로 각각 시도하면 이를 통해 결과를 낼 수 있다는 점을 알게 되었다. 예를 들어 7에서 값을 구한다고 해보자. 이때, 4-5와 더불어 9까지 정보를 알 수 없기에 3이라는 결과가 나오게 된다. 이것은 앞서 말..

https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net > 접근 초기에는 단순히 3차원 DP를 이용하여 다익스트라를 돌리는 식으로 문제를 풀었으나, 더 효율적인 방법이 가능하였다. 바로 3칸 이동을 기본 전제하에 다익스트라를 돌리고, 마지막 칸을 기준으로 2회 이내 도달 가능한 범위에서 결과값을 얻어오는 것이다. 굳이 이렇게 하는 것은, 원하는 최소 시간에 해당하는 루트의 이동 횟수가 무조건 3의 배수일 리가 없기 때문이다. 예제 입..

https://www.acmicpc.net/problem/9015 9015번: 정사각형 각 테스트 케이스마다 가장 큰 정사각형의 넓이를 한 줄에 하나씩 출력한다. 단, 정사각형이 없는 경우 0을 출력한다. www.acmicpc.net > 접근 시간 제한이 10초이고 N이 3000이므로 정사각형 판별을 어렵게 하지 않아도 된다고 생각했다. 우선 정사각형을 어떻게 판별할지에 대해 고민해보자. 위 사진과 같이 정사각형을 이루는 네 점들에서 특정한 패턴이 있다. offset을 계산해보면 위와 같다. 패턴이 보이지 않는가? 현재 오프셋이 offset_x, offset_y라면, 그 다음 오프셋은 offset_y, -offset_x이다. 이 특징을 통해 정사각형을 판별하기 위해선 두 점이 필요하다. 따라서 N^2 반..

https://www.acmicpc.net/problem/23324 23324번: 어려운 모든 정점 쌍 최단 거리 첫 번째 줄에 정점의 개수 $N$($2 \le N \le 100\,000$), 간선의 개수 $M$($1 \le M \le 200\,000$), 정수 $K$($1 \le K \le M$)가 주어진다. 다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$ www.acmicpc.net > 접근 예제 입력 1에서 6이라는 결과가 어떻게 나오는지 일일히 그려본 결과, 2-3으로 분리되는 두 그룹(각각 [1,2]와 [3,4,5])에서의 노드 갯수를 곱하면 정답이 나온다는 것을 알게 되었다. 또한 1-4와 같은 간선이 추가되어 두 그룹 간의 경계가 모호해질 경..

https://www.acmicpc.net/problem/3050 3050번: 집들이 첫째 줄에 아파트의 크기를 나타내는 R과 C가 주어진다. (1 ≤ R, C ≤ 400) 다음 R개 줄에는 C개의 문자가 주어지며, 빈 칸은 '.', 막힌 칸은 'X'로 주어진다. 상근이는 오직 빈 칸에만 식탁을 놓을 수 www.acmicpc.net > 접근 처음 예제 입력 2를 보고, 모든 지점에 대해서 시계 방향 또는 반시계 방향으로 돌아서 직사각형의 width, height를 알아낼 수 있다고 생각했다. 대략 아래와 같이 말이다. 하지만 아래의 레이아웃에 대해서는 전혀 먹히지 않았다는 것을 알았다. 이에 따라 다른 방법을 고안해냈다. 특정 지점을 잡고 그곳에서의 직사각형들을 전부 구해내는 것인데, 사진으로 묘사하면 ..

https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net > 접근 친구들이 위치한 방들의 리스트를 rooms라고 해보자. 모든 노드를 돌면서(for i 1~N) 'i에서 rooms까지 거리들의 총합'을 구하고, 이 값이 가장 작은 곳이 모임 장소가 된다. 이 때 dists[i][room]과 같은 코드가 필요하게 되는데, 이를 위해 '모든 곳에서 모든 곳까지의 최단경로'를 구하는 Floyd Warshall를 사용하게 된다. import sys input ..

https://www.acmicpc.net/problem/20312 20312번: CPU 벤치마킹 윤이는 Uni-COM에서 컴퓨터 부품을 판매하고 있다. 윤이는 다양한 성능의 CPU를 취급하는데, 손님들이 CPU의 성능을 손쉽게 비교할 수 있도록 벤치마크 표를 만들려고 한다. 모든 CPU 쌍을 직접 비교 www.acmicpc.net > 접근 표에서 row 단위로 묶어서 식을 계산할 때, (직전 row + 1) * (현재 row에 해당하는 입력값)를 계속해서 해주는 걸 알 수 있다. import sys input = sys.stdin.readline INF = 1000000007 def solution(): input() res = 0 prev = 0 for n in map(int, input().spli..