BOJ 11378 열혈강호4

음... 이번 문제는 유량 그래프를 제대로 그리긴 했으나
이분 매칭 코드를 활용하는 과정에서 잘못 생각했다.

일단 나는 예제는 다 맞게 나오고, 시간초과가 나길래 틀렸을 거라고는 생각 못했는데...
백준님의 코드를 보니 아예 내 코드자체가 틀렸었다.
만약 시간이 넉넉했다면 시간초과가 아닌 틀렸습니다를 받았을 것이다.


일단 나는 간략하게 말해서 각 사람에 대해 k+1번을 돌리면서 count하다가.. coutn가 n+k가 되면 break하는 방식인데...

백준님은 일단 1번씩의 매칭을 하고, 그 다음에 k번을 추가로 돌려주는 방식...

내 방식에서는 그냥 이분매칭을 했을 때 n번의 매칭이 되었다는 것이 보장되어야 하는데, 그렇지 않다.그냥 이분매칭의 경우 최대 n번인데, n번이 안나올 수도 있다.
그래서 처음부터 n+k번을 돌리게 되면 한사람이 최대 k+1번을 넘게 일하는 경우를 답으로 출력할 수 있는 것이다...

그래서 틀렸습니다...가 나온다.

BOJ 11657 타임머신을 풀다가 궁금한 점

벨만 포드 알고리즘에서는 음수 사이클이 있으면 그냥 다른 경로들도 clear를 해버리는 데,
만약 음수 사이클이 다른 경로들에는 영향을 안끼치는 그런 경로들이라면 그런 것은 어떻게 구분해야할까?

음수 사이클이 일부만 있으면 음수사이클의 영향을 받지 않는 다른 경로들은 구할 수 있어야하는데, 어떻게 구하지?

구하는 거야 clear안해버리고 그 배열을 그대로 쓰면 되긴하는데, 문제는 음수 사이클이 영향을 미치는 경로와 영향을 안 미치는 경로가 어디인지를 구분해야 써먹을 수 있다는 것인데... 음...

BOJ 1948

다른 고수님들의 코드를 보니...(alohajm, baactree.. 등등)
역으로 올때 그냥 parent 배열을 사용해주는 것 같았는데, 이럴 경우 겹치는 것을 어떻게 처리하냐.. 아마 map으로 중복을 방지하거나, indegree를 이용해서 중복되서 큐에 들어가지 않도록 indegree가 0이되면 큐에 넣도록 하는 것 같다...
정말 대단하다... 나중에 위의 방식으로 다시 풀어봐야겠다.

BOJ 1916

다익스트라 알고리즘으로 푸는데, 종만북 + 백준님의 check배열... 을 이용했고,
처음에 틀려서 방황하고 있다가 질문 검색을 보고... INF크기를 너무 작게 한 것이 원인이었단 것을 알게 되었다. 휴 생각하면서 하자!

BOJ 2352 반도체 설계 - lis, lowerbound, upperbound

lower, upper bound,
lis logN...-> 이유까지...
팬윅 트리도 공부해볼까..

Longest Increasing Subsequence (가장 긴 증가 부분수열), 줄여서 LIS를 구하는 문제이다.
KOI 지역본선 초등부 문제 중에서 '전봇대'라는 문제와 매우 비슷하다.

LIS는 dp로 풀어왔었고, 그 경우 시간 복잡도는 O(N^2) 이었다. 이 반도체 설계라는 문제는 N이 40000이라... N^2 의 알고리즘으로는 TLE(Time Limit Exceeded)를 받는다.

다행히 NlogN의 알고리즘을 잘 정리해 놓은 블로그가 있었다!
http://dyngina.tistory.com/16


4 2 6 3 1 5 라는 수열이 있다고 하자.

1. 배열에 4가 들어간다. {4, }
2. 배열에 있는 4를 2로 바꾼다. {2, }
3. 배열에 6이 들어간다. {2, 6}
4. 배열에 있는 6을 3으로 바꾼다. {2, 3}
5. 배열에 있는 2를 1로 바꾼다. {1, 3}
6. 배열에 5 가 들어간다. {1, 3, 5}

배열의 길이인 3이 가장 긴 증가 부분수열의 길이이다.
이 방법의 경우 배열안의 값들은 가장 긴 증가 부분수열을 이루는 값들이 아닐 수 있다.

위의 블로그에 따르면, 배열에 들어가있는 값들의 의미는 이렇다.
예를 들어, 값 x가 배열에 들어가있다면, x를 마지막으로 포함하는 LIS의 길이가 x까지의 배열의 크기라는 것이다.
{1, 3, 5}를 보면 LIS를 구성하는 값이 1, 3, 5 라는 것이 아니라, 5를 마지막 수로 포함하는 LIS의 길이가 배열의 크기인 3이라는 것이다.

그리고 구하는 과정을 보면, 더 작은 값들로 바꿔지는 과정이 보이는데, 그래야 뒤에 올 수 있는 값 후보들을 최대로 해서 가능한 모든 경우를 다 볼 수 있다.

예를 들어 1, 3, 7, 5, .... 이렇게 있는데, {1, 3, }을 선택한 후 , 5를 선택하는 것이 7을 선택하는 것 이상의 답을 구할 수 있다.

이 방법이 greedy방법 같아보이는데...(여태 LIS는 dp로만 푸는 줄 알고 있었다.) 정확히는 모르겠다.

그런데, 여기서 하나 알아야 할 것이 lower bound이다. 위에서 새로 들어온 수로 바꿔주는 과정에서 바꿀 위치를 찾는 데 lower bound가 필요하다.

lower bound는 http://blog.naver.com/jwoo619/220704620584 이 곳에 잘 설명되어 있는데,
찾고자 하는 값 이상이 처음 나타나는 위치로 볼 수있고, 쓰고싶다면, 이분탐색을 이용해서 구현하거나, C++ STL에서 <algorithm>을 include하면 사용할 수 있다. 이 함수를 사용하면,
lower bound의 경우, val보다 작지 않은 값 즉, val이상의 값이 처음 나타나는 위치(index)를 가리키는 iterator를 반환해주는데, 모든 값이 val보다 작다면 제일 마지막 위치를 가리키는 iterator를 반환해준다.
참조 : http://www.cplusplus.com/reference/algorithm/lower_bound/
upper bound의 경우, val보다 큰 값이 처음 나타나는 위치(index)를 가리키는 iterator를 반환해준다.

1 1 1 2 2 2 3 3 3 이란 수열이 있고, val=2이면,
val의 lower bound는 2가 처음 나오는 index 3을, upper bound는 (2보다 큰)3이처음 나오는 index 6을 반환할 것이다. (index는 0부터 시작)

근데, 이렇게 써놓고 보니 lower bound대신 upper bound를 써도될 것 같은데...?
일단 코드를 짜봐야겠다.

해보니 upper_bound도 역시 된다! lower_bound를 써야하나, upper_bound를 써야하나..에대해서는 나중에 그런 고민을 할 문제가 나오면 고민해보도록 하자.
이제 이분탐색과, 그냥 linear(?)로 구현해보고 마무리해야겠다.

//추가 - linear(?)로 풀다가 생각난건데, 만약 가장 긴 감소하는 부분 수열을 구하는 것이라면, 물론LIS를 거꾸로 해도 되겠지만, LIS에서 val 이상이 처음 나타나는 위치를 찾아서 더 작은 값으로 바꿔주었다면, val 이하가 처음 나타나는 위치를 찾아서 더 큰 값으로 바꿔주는 식으로 하면 될 것 같다. lower bound 를 못쓰겠지만, 이분 탐색으로 하면 속도도 빠르게 할 수 있을 것이다.

//추가 - BOJ Slack에서 doju님의 관련 답변

lis와 상관없고 길이만을 구하기 위한 그 배열에 들어가있는 수의 의미는 x번째 숫자로 나올 수 있는 최솟값...!! 왜냐하면 최대길이를 구해야하니까, 그 위치에 올 수 있는 최소값이 들어가야한다! 음 나도 이해는 했지만 확실히, 완벽하게 이해한 것은 아니었던 것 같다.

마지막으로, 이 방법말고도 index tree를 이용하는 방법도 있다고 하는데, 그 방법의 경우 배열의 요소까지 구할 수 있다고 한다. 공부해봐야 겠다.

BOJ 1977 그리고 내림과 버림의 차이 (floor와 int casting의 차이)

나는 문제를 풀 때 올림과 내림을 이용해서 풀려고 했는데... 실수를 정수로 올림하는 것과 내림하는 것을 직접 구현하려 했지만... 음 어렵다.. 못했다... 일단은 int casting을 쓰려고 하는데, 찾아보니 int casting (int)과 floor(내림)의 차이는 int casting은 버림인데, 이 버림이란 것은 0을 향하고 있는 것이고, 내림은 음의 무한대를 향하고 있는 것으로 볼 수 있다.

즉 양수에서는 둘 다 같은 결과를 보여주지만, 음수에서는 예를들어
(int)-3.2 => -3.0
floor(-3.2) => -4.0

이런 차이가 있는 것이다.

BOJ 2631

구글 블로그가 에러가 나서 계속 안 들어가진다.
 

그래서 BOJ 2631를 워드에 임시로 적어놓는다.

이 문제는 고민하다가 처음에는 어떤 순열에서 어떤 순열로 변하는 최소의 수를 가지고 동적계획법으로 하면 어떨까 생각했는데 일단 최대 입력만 해도 무려 200… 게다가 순열을 어떻게 상태로 표현할 것인지도..음 그래서 고민하던 중 하늘이 도우신 것 같다. 갑자기 가장 긴 증가 부분수열이 떠올랐다.!!! LIS(Longest Increasing Subsequence)!!!

그렇다!! LIS의 길이를 구하고 그 길이를 빼면 되는 것이다. 한 번 해보겠다.

정답이다! 열심히 하자!