hjhj97

1085C-Connect Three 격자무늬 상에서 좌표 3개가 주어지고 그 좌표 3개를 모두 이으려고 할 때, 방문해야 하는 격자의 수를 최소로 해야하는 문제이다. 논리적으로 이러이러해서 이렇게 풀어야 한다기보다는, 스스로 여러가지 테스트케이스를 만들어보면서 끄적이다보니 규칙을 자연스럽게 발견하게 되는 문제라서 이런 문제는 참 설명하기가 어렵다. 일단 솔루션을 먼저 설명하고 밑에서 왜 다른 케이스는 정답이 될 수 없는지(최소가 아닌지)에 대해서 설명하겠다. A(1,2) B(4,3) C(5,1) 이 있다고 가정해보자. 1. 세 점 중에서 x좌표가 가장 큰 점과 가장 작은 점을 찾는다.(나는 정렬을 사용했다)2. 그런 다음, 다시 세 점 중에서 y좌표가 중간(가장 크지도 않고, 가장 작지도 않은)점을 찾는..

[BOJ 1826] 연료 채우기​ 우선순위 큐(힙)를 이용해서 그리디로 푸는 문제이다. 우선 주유소를 거리 순으로 정렬한 뒤에, 현재 연료양을 가지고 최대한 갈 수 있는 범위 안에 속하는 주유소들의 연료 양(c)를 모두 최대 힙에 넣는다. 그 다음 힙의 top에서 원소(c)를 하나씩 빼보면서 이 연료를 주입했다면 다음 주유소까지 도달 할 수 있었는지를 확인한다. 만약 불가능 하다면 가능할 때까지 힙에서 원소를 계속 빼서 더해본다. 만약 모두 뺐는데도 다음 주유소까지 도달할 수 없다면 이는 불가능하다는 뜻이므로 -1을 출력하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..

15462-The Bovine Shuffle(Silver) Bronze문제처럼 셔플 규칙 수열이 제시되는데, 이번에는 그 규칙대로 무한히 많이 셔플한다고 가정할 때 소가 항상 위치하게 되는 지점의 개수를 묻고 있다. 이 문제에서 셔플 수열은 같은 수가 등장할 수도 있어서 그런 경우에는 한 지점의 여러 마리의 소들이 위치하게 되고, 그 말은 즉슨 어느 지점은 아무 소도 위치하지 않는다는 뜻이다. 어떻게 풀지 끄적거리다가 셔플이라는 행위 자체를 그래프로 모델링하니 쉽게 와닿았다. 예를 들어 3 2 1 3이라는 셔플 수열의 의미는 다음 번에 1번 지점의 소는 3번으로, 2번지점의 소는 2번으로.... 이런 의미이고, 이를 그래프로 모델링하면 다음과 같다. 위와 같은 그래프가 있다고 가정하고, 각 노드에서 다음..

15460-My Cow Ate My Homework 수열 arr가 주어지고 소는 수열의 숫자를 앞에서부터 최소 1개부터 최대 n개까지 먹어서 없앨 수 있다. 그리고 없앤 뒤의 수열들 중에서 가장 작은 수 하나를 삭제한 뒤 나머지 값들의 평균(합/개수)을 구해서 그 평균의 값이 가장 크게 되도록 하려면 질문을 몇 개 먹어야 하는지를 묻고 있다.(그 개수가 여러개라면 오름차순으로 모두 출력한다)단순 구현문제로, 루프로 1개 없애는 경우부터 n개 없애는 경우까지 모두 살펴봐서 평균값을 계산해보면 된다. 일단 평균을 구하기 위해서는 먹어치운 k개를 제외한 나머지 (k+1)~n번째에서 가장 작은 값을 제외한 나머지의 합을 구한 뒤, 개수로 나눈 값이 평균이 되고, 평균의 최대값을 저장하는 변수와 일일이 비교해서 ..

15465-Milk Measurement(Bronze)(set) 각 날짜마자 소의 우유 생산 변동량이 제시되고, 그동안 우유 생산량이 가장 많은 소는 변동이 총 몇 번 일어나는지 묻고있다. 우선 day를 오름차순으로 정렬한 뒤, 매 변동량을 update해준다.여기서 우유 생산량이 가장 많은 소가 둘 이상일 수도 있다. 그럴 때는 여러 소를 동시에 포함해야 하므로 stl set을 사용했다. 따라서 내가 고려해야할 문제는 매 day마다 set의 원소가 이전 day보다 같은지 아닌지만 확인하면 된다. 처음에 두 set의 원소가 일치하는 지의 여부를 직접 구현했는데, 찾아보니 단순하게 == 연산자를 쓰면 된다고 한다. set(a) == set(b) 는 set인 a와 b의 원소가 모두 일치하면 true, 하나라도..

15464-The Bovine Shuffle(Bronze) 셔플 규칙 수열과 이 규칙을 기준으로 3번 셔플된 후의 order를 알려주고, 이 결과를 바탕으로 셔플 하기 전인 처음 상태의 order를 유추하는 문제다. 3번 셔플된 후를 알고 있으니 거꾸로 거슬러 올라가면서 2번->1번->처음 이렇게 order를 갱신해주면 된다.만약 3번 셔플의 결과가 a b c d e 이고,셔플 규칙이 1 3 4 5 2이면 그 직전(2번 셔플)은 a c d e b가 되는 식이다. 12345678910111213141516171819202122232425262728#include#define SIZE 101int n,arr[SIZE];int order[4][SIZE];int main(){ scanf("%d",&n); for..

임의의 n개의 수 중에서 k번째로 큰 수(혹은 작은 수)를 찾으려면 어떻게 해야 할까? 가장 단순한 방법으로는 n개를 모두 정렬한 뒤 앞이나 뒤에서부터 k번째 있는 수를 찾으면 된다. 아니면 크기가 k짜리의 최소 힙(최대 힙)을 이용할 수도 있다. 그런데 사실 이것들은 조금 꼼수같다는 기분이 든다. 꼼수부리지 않는 정석적인 알고리즘이 바로 Quick Selection 알고리즘이다. 이 알고리즘은 Quick Sort 알고리즘을 약간 변형시킨 알고리즘이다. Quick Sort 알고리즘은 pivot을 하나 정해서 자신의 위치를 찾아서 고정시키고 그 앞뒤로 다시 재귀호출을 통해서 수를 정렬시키는데, Quick Selection은 이때 앞뒤로 2번의 재귀 호출이 아닌 본인에게 필요한 딱 1번의 재귀호출만 하는 함..

1787-문자열의 주기 예측 KMP알고리즘의 실패함수를 활용하는 문제이다. 다만 실패함수를 그대로 사용하는게 아니라 약간의 변형이 필요한데, 이를 위해선 실패함수의 의미에 대해서 정확히 파악해야만 한다.예를 들어 "bbabbab"라는 문자열이 있다고 하자. 이를 실패함수로 표현해보면, 0 1 2 3 4 5 6 b b a b b a b 0 1 0 1 2 3 4 가 된다. 여기서 실패함수의 값이 의미하는 바를 한번 생각해보자. 예를 들어 3번째 인덱스('b')가 의미하는 '1'은 무슨 의미일까? 해당 인덱스에서 txt와 비교를 했는데 만약 일치하지 않았다면 다음으로 비교할 지점은 ptn의 '1'번째 부터 보면 된다는 의미이다. 이것이 실패함수의 표면적인 정의이다. 하지만 이것 말고도 숨겨진 의미가 있다. 그..