https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제풀이 사고력이 필요한 문제다. 문제를 간단히 요약해보면, N개의 센서가 정수 좌표이 있으며 중복해 있을 수 있다. K개의 집중국이 있고 집중국은 아무데나 놔도 되고 모든 센서를 수신하면서 수신 가능영역이 최소인 위치에 놓아야 한다. 문제 접근은 이런 방식으로 해 보았다. 센서가 이리저리 놓여있을 텐데, 어느 지점 마다 끊어서 집중국을 설치해야 할까? 센서 사이의 거리가..
https://www.acmicpc.net/problem/2195 2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 문제풀이 처음에 그냥 문자열 무지성으로 비교하면 되려나? 시간 초과나지 않을까? 어떻게 푸는거야. 라는 생각을 하다가 결국 다른 사람이 어떻게 풀었나 살짝 봤다. 그런데 진짜 그냥 하나하나 비교하더라. 왜 다 비교하는데 시간초과가 안날까? 일단 풀이 방법을 먼저 보자. bdx 라는 변수를 지정하고, 이 bdx가 p의 길이보다 작을 때 까지 while문을 돌린다. 이 wh..
https://www.acmicpc.net/problem/2785 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 문제풀이 그리디 쉽지않다. 코드는 정말 간단한데 구현 과정을 생각하는게 어렵다. 고려해야 할 점은, 1 1 1같이 주어 졌을 때 하나의 고리만 열면 모든 체인이 연결된다는 점이다. 즉 체인의 고리를 모두 소모하는 경우 연결해야 할 체인이 하나 줄어든다는 점이 핵심이다. 받은 입력을 정렬해서, 가장 짧은 체인의 고리를 하나씩 떼서 가장 긴 두 체인을 연결하는데 사용하는 방법을 생각했다. 만약 가장 짧은 ..
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제풀이 보자마자 딱! MST 를 만들면 되겠구나 라고 생각했다. MST를 만드는 알고리즘은 여러가지가 있는데 그중에 kruskal 알고리즘을 사용하기로 했다. 예전에 해본적이 있어서 이걸 사용했다. union-find 알고리즘을 그대로 사용하면된다. 크루스컬 알고리즘의 핵심을 weight별로 정렬하여 cycle이 발생하지 않는 edge를 추가하는 것이다. union-find 알고리즘으로 cycle 발생 여부를 체크해가며 edge를 추가하면 쉽게 구현할 수 있다. 1. 입력받은 edge..
https://www.acmicpc.net/problem/1337 1337번: 올바른 배열 첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이 www.acmicpc.net 문제풀이 접근 방법이 생각처럼 잘 떠오르지 않았다. 일단 연속되는 수를 찾아야 하기 때문에 정렬을 해 주어야겠다고 생각했다. 정렬한 값을 순서대로 보면서 어떻게 하면 추가해야 할 원소를 구할수 있지 않을까? 라고 고민해보았다. 그 결과 이런 방법이 떠올랐다. 정렬한 배열을 순회한다, 각 순회마다 배열 인덱스 1~4를 더한 곳의 배열 값을 가져와 현재 순회하는 배열의 값과 비교를 ..
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제풀이 처음 문제를 딱 봤을 땐, 어 어려운데? 감이 잘 안오네 라는 생각을했다. 근데 왠지 모르게 본능적으로 스택을 써서 어떻게 하면 풀수 있을거란 생각이 났다. 문제를 많이 풀어보면서 생긴 느낌인가보다. 우선 레이저와 쇠막대기를 어떻게 구분할지 고민했는데, 이건 간단했다. 레이저는 바로 () 닫는 괄호가 나오고 쇠막대기는 그렇지 않다. 그렇다면 쇠막대기를 stack에 넣어주고, 레이저가 나온다면 두동강..
