BOJ 1261

알고스팟이라는 문제인데... 음 처음에는 그냥 bfs로 다 탐색하면서 벽을 뚫을 때마다 벽을 뚫은 개수를 d[i][j]에 기록하면서 나가면서, 더 적게 뚫은 경우가 있으면 update해주고 큐에 넣는 식으로 풀었는데, 4ms라는 시간이 나왔다.

다른 분들을 보니 0ms에 푼 분들도 많았다. 그래서 백준님의 풀이 설명을 보니 큐를 2개 이용하거나 덱을 써서 벽이 없는 부분으로만 갈 수 있는 경로와와 벽을 하나 뚫고 갈 수 있는 경로로 나눠서 단계별로 bfs를 실행 시켰고, 그렇게 단계별로 실행함으로 인해, 내가 원래 풀었던 방식에서 있었던 중복된 방문과 update가 없어도 되는 것 같다. 한번 씩만 방문하게 되어 더 시간이 절약되고...

덱을 사용해서 내가 다시 풀어봤는데.. 정말 덱을 이렇게 쓸 수 있다니... 감탄이 나왔다. 덱이 처음에는 별 사용도 안될 필요없는 자료구조인 줄 알았는데 오늘 알고스팟 문제를 풀면서 덱의 멋짐, 아름다움을 느꼈다...
그리고 이 덱을 사용한다는 풀이를 하는 분들도 정말 대단하신 것 같다.

여튼 그래서 0ms에 풀었다. 근데 아직 이해가 안되는 것은 복잡도가 O(n^2)이 나온다는 것인데, 이것이 무엇을 뜻하는지 잘 모르겠다. 한번 메일로 질문해볼까 생각중이다.
-> 백준님게 답장이 왔는데, O(nm)을 뜻하는 거라고 하신다. 내 추측이 맞은 것 같다.

BOJ 4963

섬의 개수 문제를 풀려고 했는데... 일단 탐색으로 연결된 것들을 탐색해야되는 것은 알겠는데 어떻게 개수를 세지? ..개수를 어떻게 셀지 떠오르지 않았다... 그래서 연결 요소 문제(11724)를 찾아보고 나서야 알게되었다... 아 이것을 기억 못하다니... 정말 많이 부족하다. 풀어봤던 문제라도 또 풀어보고, 복습하고, 그리고 생각하는 연습 계속 하자
힘내자.

BOJ 1932

처음에는 무슨 그래프로 완전 탐색하는 건가 생각했다... 그러다가 문제 분류를 봤는데 dp라고 되어있어서... 아 난 정말 너무 부족하다...휴 여튼 dp로 접근하려고 생각해보니 작년 2학기 알고리즘 시간에 비슷한 dp문제를 푼적이 있다는 게 기억이 났다.
그래서 어떻게 풀어야할지 감은 왔는데... 문제는 입력 값인 삼각형 형태의 숫자들을 어떻게 담을 것이며 dp로 풀기위해 삼각형을 트리라고 보면 child가 parent가 누구인지를 알아야 하는데... 이걸 배열에 담으면.. 어떻게 index를 구분하지..부터... 그냥 복잡해졌다...
어떻게 풀어야할지는 알고 있는데.. 저것을 어떻게 받을지 어떤 자료형을 쓸지... 어떻게 표현할지 전혀 감이 안왔다...

아 정말 난 실력이 너무 부족하고 너무 못하는데... 말로만 그러고 실제로는 자만심에 빠져있다. 너무 오만하다... 그러다보니 여유부리고.. 벌써 4월 20일... 휴...
자신이 나약한지 알아야 강해질 수 있다는데 난 내가 나약하다고 입으로만 말하지 실제로는 잘한다고 생각하고 절실히 느끼지는 못하고 있다...

열심히 하자...

여튼 그래서 구글링을 해서 다른 사람의 코드를 참조했다.
그래서 2차원 배열에 넣고 쉽게 풀었다.
그리고 맞은 사람 목록에서 다른 사람의 코드를 봤는데.. 그냥 일차원 배열로도 풀 수 있었다... 그리고 나는 맨 끝에 있는 숫자의 경우 자신의 parent를 찾을 때 parent가 하나 밖에 없으므로 조건을 걸어줬는데, 그럴 필요가 없었다. 어차피 index를 1부터 시작하면 0부분은 비어있고, 끝 부분+1부분도 비어있다.. 아마 0으로 초기화 되있을 것이다. 0으로 초기화 하면된다. 이게 최대값을 구하는 것이므로 0으로 초기화 해놓으면 다른 조건 필요없이 parent를 2개로 생각하고 그 중 최대값을 얻으면 된다...

최소값을 구하는 거라면 엄청 큰 수로 초기화 해놓든가 하면 될 것이고...

열심히 하자.

강해질 수 있는 방법은... 자기 자신이 얼마나 나약한지 아는 것이다. (드래곤사쿠라)

BOJ 1654

랜선 자르기 문제는 이분 탐색으로 비교적 쉽게 풀 수 있는 문제인데,
음... 자료형이 문제였다...

일단 입력값 범위는 2의 31제곱 -1로 int범위이다. 그런데 랜선의 개수를 세는 과정에서
int형 범위를 넘을 수도 있을 것 같아 그 부분은 long long으로 바꿨는데, 그래도 틀렸다고 나와서 전부(입력부터 모두 다) long long으로 바꿔 버렸더니 맞다고 나오길래...

처음에는 문제가 잘못된건가 했다. 그래도 혹시 몰라서 질문을 뒤져봤는데 그리 명쾌한 답변은 없어서, (물론 나중에 이유를 알고 생각해보니 그런 답변이 있었는데 지나친 것 같다.) 게시판에 직접 질문을 올렸는데, 거의 바로 답변이 달렸다.

orange4glace님의 감사한 답변이다.


mid값을 구하는 과정에서 l+r이 int범위를 초과할 수 있다.
그래서 순간 아하! 깨달음을 얻었다 생각했는데 더 생각해보니
음 그래도 l+r이 초과하는거지 (l+r)/2는 결국 int형 범위를 초과하지 않게되는데...

그래서 직접 실험해봤다.

이렇게 해보니 값이 출력되지 않는다... 으흠 그래서 막 바꿔서 이것저것 해보았는데,
결국은 l, r을 long long으로 바꾸니 제대로 나왔다.

정확히는 모르겠지만, long long범위가 되는 연산을 하려면 l, r도 long long이여야 하는 것 같다. (물론 시스템 차이라던가, 아니면 내가 모르는 무언가로 인해 다를 수 있기 때문에 일단 이렇게 기록해두고 정확한건 나중에 공부하면서 알아가자.)

그래서 이번에는 l, r만 long long으로 바꾸고, mid, ans는 int형으로 해보았는데..
이번에는 런타임 에러가 떴다. 직접 실험해보니...
while문 조건 중에 while(l <= r)이라는 조건이 있다. 참고로 l < r로 할 경우 모든 수를 다 볼 수 없다. 여하튼 이 조건 때문에 l값이 int형 범위를 넘어갈 수 있고, 그로인해 mid값도 int형 범위를 넘어가게 될 수 있다. (예 : l : 2,147,483,648(int범위 초과) r : 2,147,483,647)

아 그리고 추가로 long long을 쓸 때와 int를 쓸 때 속도나 메모리 차이가 좀 날 것이다.
이 문제에서는 속도차이는 큰 차이 없었는지 보이지 않고 4ms로 나왔지만 메모리 차이는 확실히 나왔다. 
이 문제를 통해 이분 탐색 외에도 많은 것을 배웠다.
-----------------------------------
오랜만에 다시 봤더니 재채점이 되어있고 원래 AC를 받았던 코드가 런타임에러를 받아서 살펴봤는데... 원인은 이분탐색에서 l, r값 설정이었다. l을 0으로 설정해놨는데, 이러면 mid값이 0이 될 수 있고, 랜선의 개수를 계산할 때 0으로 나누는 연산이 실행되어 런타임에러가 난 것 같다.

BOJ 9202를 풀다가...?

Trie를 공부하면서 BOJ 9202를 풀려했지만 도저히 엄두가 안나서 바로 풀이를 봤지만 그래도 잘 모르겠고... 계속 보고 따라 쳐보니 이해는 되는듯 하지만 여전히 구현하려니 엄두가 안난다. 데이터를 담을 자료형, 자료구조 부터 시작해서..C++ 문법적인 부분도 그렇고... 완전탐색, 재귀 부분도... 점차 여태 임시방편 이었던 내 C++실력이 드러나는 것 같다. C++문법과, STL에 대해서 따로 공부를 할 필요성을 느끼고 있다. 공부하자. 조금씩이라도..

그리고 내 코딩력이 많이 부족함을 느낀다. 고작 100문제 정도라 그런가... 최대한 다양한 문제를 많이 풀자. 이론 공부를 하더라도 하루에 5문제는 풀 수 있도록 하자. 제출을 하든 안하든 코딩을 많이 하는 노력을 하자. 매일 꼭 5문제 이상 코딩하자.

1. C++문법, STL 공부 필요
2. 코딩력 향상을 위한 꾸준한 코딩 필요. (다양한 많은 문제 풀이 필요)

BOJ 7785

랭커들의 코드를 보니 C에서 qsort, C++에서 set을 많이 쓴 것 같다.
확실히 내 방법으로는 속도에 한계가 있다.
내가 문법적으로 많이 부족한 것 같다.
그리고 qsort, set에 대해 전혀 모르다보니 생각조차 못했다.
아는 만큼 보인다는 것을, 아는 만큼 생각할 수 있다는 것을 절실히 느꼈다...

qsort는 그렇다치고.. set은 공부해 볼 필요가 있어 보인다.
나중에 다시 풀어보고 공부해보자.

BOJ 9996

엄청 쉬워보이는 문제였는데...
막상 해보니 내가 문자열 처리를 엄청 못한다는 것을 알 수 있었고...

결국 우여곡절 끝에 완성했지만... 맞은 것 같은데도 계속 틀려서 혼자 예시들을 쳐보다가
우연히 반례를 찾게 되었다.

abc*cd
abcd

바로 이것이다.
이 경우를 다루지 못했다...
그래서 마지막에 prefix단어의 끝이, suffix단어의 앞보다 앞에 있어야하는 조건을
넣어서 해결했다.

열심히 하자.