BOJ 1948

임계경로 문제...
메모리초과가 3번이나 뜨고 틀렸습니다도 3번이나 떴다.

많이 어려웠다.
백준님의 강의자료에 수록된 문제가 아니라 백준님의 코드가 없어서... 아 물론 백준님께서 따로 설명해주시긴 하셔서 어느정도 방향을 잡고 코드를 짰고, 예제는 가볍게 통과해서 제출을 했는데... 틀렸습니다가 나오길래... indegree를 쓰면 안된다는 것을 깨닫고 indegree를 빼고 bfs로 했더니 메모리초과... 메모리초과에 대해 검색해보니 대부분 bfs문제에서 발생하는 것 같았다.

큐에 너무 많은 데이터가 들어가서 그런건가... 그래서 다시 indegree를 쓸까 생각해보았는데, indegree를 쓸 경우 .. 그러니깐 indegree가 0인 경우만 큐에 넣을 경우에는.. 만약 1에서 시작하는데 1에서 시작해서 갈 수 없는 곳이 있다면 그리고 그 곳에서 최종 목적지나 그 전을 향하고 있다면, 가리키고 있다면 최종 목적지까지는 도달할 수 없게된다...
물론 이게 문제 조건에서 이런 경우를 배제하고 있다면 괜찮겠지만 내가 보기엔 아닌 것 같았다.

그런데 내가 메모리초과에 대해 생각하다가 싸이클이 원인이 아닌가 해서 싸이클에대해 엄청 고민했는데... 생각이 안나서 문제를 다시 읽어보니 싸이클이 없다네...

여튼 그래서 최대값 구하는 bfs에서 최대값을 구할 때 즉 기존 최대값보다 더 큰 값이 있어서 기존 최대값을 갱신해줘야할 때마다 큐에 탐색할 노드를 넣어주는 걸로 바꿨다. 이정도로도 그냥 매번 큐에 넣어서 똑같은 곳을 계속 탐색하는 것에서 많이 줄일 수 있는 것 같다.
물론 최대값이 매번 갱신되버리면 똑같을 수 있지만....

여튼 그렇게 하니 메모리초과는 사라졌지만 여전히 틀리다고 나옴...
음 그래서 뭘까 생각하면서 다른 예제들을 만들어서 넣었더니... 지나야하는 간선의 개수를 구하는 부분에서 틀렸다는 것을 알게됨.

내 코드는 지나야하는 간선을 중복해서 세고있었다... 그래서 체크어레이를 만들어서 한번 방문한 노드는 어차피 또 방문해도 경로는 같고 카운트도 같아버리니 또 방문해서 카운트할 필요가 없기때문에 방문하지 않은 곳만 방문해서 카운트를 하는 식으로 했다.

그리고 ... 드디어 맞았습니다... 근데 다시 짜라고 하면 헷갈려서 못짤듯... 그래서 지금부터sublime text, dev c++ , vim에 각각 연습으로 짜보고 다시 제출해봐야겠다.

그리고 위에서 indegree를 활용한 경우도 한 번 제출해볼까... 여튼... 다시 연습해야겠다.

오늘 이 한문제말고는 아무것도 못했다. 열심히 해야겠다.

BOJ 1107

리모컨이라는 문제이고, 수업시간에 완전탐색 부분에서 배운 문제이다.
리모컨에는 0~9, +, -  버튼이 있고, 0~9버튼 중에 몇개가 고장 나있을 수 있다.
그리고 현재 채널은 100이다.
자 이제 여기서 원하는 채널을 입력받고 그 채널까지 가는데 버튼을 눌러야하는 최소 횟수를 구하는 것이 문제이다.

이것을 풀기위해서 일단, 버튼을 최소로 누르기 위한 규칙을 살펴보자면
1. 숫자 버튼을 누르고 +, -버튼을 누르고 또 숫자 버튼을 누르면 이전에 누른 버튼들은 아무런 의미가 없게 된다. 그러므로 항상 버튼을 눌러야하는 횟수를 최소로 하려면 숫자부터 누르고 +, -를 눌러야한다.
2. 그리고 +와, -를 같이 쓰는 것은 아무것도 안한 것과 같을 수 있다. 그러므로 버튼을 눌러야하는 횟수를 최소로하려면 +, -중 하나만 써야한다.

그리고 마지막으로 숫자 버튼을 아예 누르지않아도 되는 경우와도 비교해봐야한다.
100에서 더 가까우면 +, -중 하나만 누르면 될 것이다.

자 일단 그래서 원하는 채널과 가장 가까운 채널을 찾아서 그 차이의 절대값만 구하면 될 것 같은데, 문제는 가장 가까운 채널을 어떻게 찾을 것이냐?
난 일단 고장난 버튼을 제외하고 원하는 채널과 같은 버튼이나 가장 가까운 수의 버튼을 선택하는 방식을 택했다.
예를들면 1234 가 있다면 1, 2, 3, 4로 분해해서 1과 가장 가깝거나 같은 버튼을 선택한다
만약 1이 고장 나있다면 0 혹은 2가 선택된다. 그다음은 2혹은 2와 가장 가까운 버튼을 선택한다. ...이런식으로 하면 4자리 수인 경우 2의 4제곱 개의 수가 나오는데, 원하는 채널과 가장 가까운 수를 그 수들 중에서 고르는 방식으로 하려고 했다.

근데 막상 해보려니 내 실력부족으로 인해... 겨우 구현은 했고, 주어진 예제는 맞았지만 결국 틀렸다.
어디서 틀렸을까?
생각해보고, 다른 예제들을 내가 만들어보았는데, 내 알고리즘에는 허점이 있다.
원하는 채널과 가장 가까운 채널을 찾는것에 허점이 있었다.

나는 각 자리별로 수를 분해해서 그 수와 같거나 가장 가까운수를 선택하는 방식으로 가장 가까운 채널의 수를 찾으려고 했는데, 이럴 경우 어떤 문제가 발생하는지 한번 예제를 보자.
19768
3
3 5 9
이렇게 19768이라는 채널이 주어지고, 고장난 버튼은 3, 5, 9 이렇게 3개라고 하자.
자 내 알고리즘에 따르면 1, 9, 7, 6, 8 각각에 대해서 가장 가깝거나 같은수를 선택할 것인데,
그렇다면 1, 8, 7, 6, 8이 선택될 것이다. 그러고보니 9와 가까운 수를 선택할때 0은 선택을 안하고 8만 선택하게 만들어놨네... 지금 글 쓰면서 깨달았다. 여튼...
19768에 대해서 18768이 가장 가까운 수로 선택되었는데... 확실히 아니다. 18768보다 가까운 수가 더 있다. 18868도 있고, 18888도 있고.. 아마 가장 가까운 수는 20000일 것이다.

백준님 강의자료와 강의에 따르면 아마 백준님은 가장 가까운 수를 모르기때문에 어떻게 구할 것인가 하시면서 문제에서 주어진 조건이 이동하려는 채널은 0<= N <=500,000 이므로 50만개를 다 보면된다고 하시는 것 같다. 그리고 이게 완전 탐색이고... 또 시간제한이 무려 2초라.. 50만개를 다보는 건 전혀 문제 될 것 없다.(참고 : 대충 1초 = 1억번 연산으로 간주...)

휴... 처음부터 풀이를 안보고(아 물론 몇주전에 풀이 수업을 듣긴했지만 어느정도 기억이 안나는 상태에서 풀어서 ...) 내가 풀어보고 이렇게 풀이를 보니까 확실히 문제에 대한 이해도가 높아지고 풀이 하나하나가 진짜 마음에 와닿는다.

셜록홈즈의 말에 따르면 천가지 정도의 범죄만 외우고 있어도 웬만한 범죄는 해결할 수 있다고...(확실하진 않지만 이렇게 말한 것 같다) 그래서 나도 알고리즘 문제를 최대한 많이 접하기위해 풀이를 먼저 보고 여러번 반복해서 숙달할까 생각했는데, 이것도 좋은 것 같고, 고민을 오래하는 것도 좋은 것같고 그래서 지금 두 방법을 섞어서 하는 중이다.

아직 100문제도 못풀었는데, 한달에 400문제씩 풀고 이런 사람들 보면 참 난 휴학까지 해놓고 뭐하는 건가 이런 생각도 들지만 아직 얼마 안되기도 했고, 초반이기도 하고 꾸준히 내 방식대로 가봐야겠다. 일단은.

크로스핏

크로스핏

1. 주먹쥐고 팔굽혀펴기 20
2. 뒷(옆)차기 왼 10 오 10
3. 아령 15키로 어깨에서 머리 위로 올렸다 내리기 20
4. 버피테스트 20

==>1~4를 쉬지 않고 5세트 반복하면 끝.
-> 오늘 해보니까 1세트만 했는데도 엄청 힘들다...
일단 오늘은 첫날이고 밤도 늦어서 1세트로 끝내고,
다음부터는 3세트로 하고
기록이 단축이 된다 싶으면 세트를 늘리든가, 개수를 늘리든가, 추가를 하든가 해서 하자.


항상 정자세로 빠르게 하려고 노력하자.
할 때마다 시간 측정하고
기록 향상을 위해 노력해보자. 

공부할 것들

1. 영어(duolingo, Teps, Toeic 단어 및 문제 풀기-Hackers site에서 매일)
2. 알고리즘
3. Buffer Overflow, Linux Kernel
4. 운동(크로스핏)


1. 영어
duolingo 매일 30xp
Hackers site에서 Teps, Toeic 1일치 문제 풀기
Hackers site에서 Teps 5일치 단어 테스트
Hackers site에서 Teps무료 적중 예상 특강 듣기(일주일에 최소 3번 문제 풀고 듣기)

2. 알고리즘
백준 + JM book

3. Buffer Overflow, Linux Kernel
Hacker school site에서 Buffer Overflow 기초 공부
달고나님의 Buffer Overflow 문서로 공부
그 외 블로그 및 Hacker school 참조해서 Lord of BOF연습
+ Web Hacking 공부
해킹대회 문제 및 풀이 찾아보고 공부

4. 운동(크로스핏)
3가지 운동을 15분간 쉬지 않고 반복해서 일주일에 최소 3번
일주일에 최소 2번은 턱걸이, 평행봉, 계단 오르기

BOJ 1722

이 문제 때문에 거의 하루를 날렸다...

여러가지 오류들이 있었지만 지금 기억나는 건 크게 2가지가 있다.
일단 첫번째 오류의 원인은
factorial값을 수용할 변수가 int형이 였던 것.. 그래서 long long으로 바꿨다.

두번째 오류의 원인은...
배열 a를 초기화하지 않았던 것이다.
근데 visual studio2010에서는 되는데, ubuntu gcc에서는 안되는 것도 참 이상하다.
원래 linux에서는 초기값을 따로 설정안해도 0아닌가?
여태 그렇게 알고 있었는데...

어쨋든 a[20]; -> a[20]={0, }으로 수정하니까 제대로 나왔다.

혹시 어레이 주소를 함수의 parameter로 넘겨서 그런 것인가? 아니 그럴리가...
휴 일단은 이 문제는 꼭 다시 풀어봐야지...
그리고 백준님의 풀이를 이해하도록 하자.

그리고 0으로 초기화되는지 아닌지에 대해 한 번 여쭤보자.
그리고 앞으로는 항상 0으로 초기화 해놓고 시작하자.

BOJ 10973

이전 순열 문제...
한 번 백준님의 피피티에 나와있는 다음 순열 문제 알고리즘 처럼
나도 한번 써보겠다.

물론 이건 내 생각이라 맞는지 아닌지는 잘 모르지만
일단 써보고 문제를 풀어보겠다.

다음 순열 문제 알고리즘과 비슷하다.

1. A[i-1] > A[i] 를 만족하는 가장 큰 i를 찾는다. (가장 긴 오름차순을 찾는다. ->최소값으로 이루어진 지점을 찾는 것임 바로 이전으로 돌아가기위해서 swap을 해줘야하니까...)
2. i-1 < j를 만족하고 A[i-1] > A[j] 를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.

좀 어렵고 헷갈린다.
Practice makes perfect!

자 이제 한 번 코드로 옮겨보겠다.
다음 순열과 비슷해서 코드로 옮기는 것은 수월할 것 같다.

맞았습니다! 가 떴다.
혼자 힘으로 푼 건 아니지만 일단 지금은 배워가는 중이고, 또한 이해를 어느정도 하고 풀어서 기분이 좋다.

BOJ 9466

오늘 백준님께 시간초과에 대해 여쭤보고 완전히 납득은 안되었지만
그래도 자세한 설명과 문제해결에 관한 실마리 덕분에
불과 몇시간 전만해도 꽉 막혀있던 생각이 시원하게 뚫린 느낌이다.
이런 걸 정말 우물안 개구리라고 하나보다... 불과 몇시간 전만해도 꽉 막혀서
잘못된 방향으로 굳게 믿고 혼자....휴
정말 열심히 하자!


본론으로 들어가서 맞는지 틀린지 모르겠지만 일단 내 생각은 이렇다.
여태까지 난 싸이클이 형성이 된 것을 확인한 후 그 것에 대해서만 visit했다고 check를
true로 바꿔줬었는데, 싸이클이 형성이 안된다면 그 싸이클의 시작점은 바로 true로 바꿔주고 더이상 탐색할 필요가 없다는 것을 깨달았다. 그 점을 지나봤자 싸이클이 형성될 수가 없다!!! 그러니 바로 false로 해줘야한다.

지금 고민중인건 아예 그 점부터 시작해서 방문한 모든점을 (싸이클이 없을 시에) 다 true로 바꿔주는 것도 고민중인데, 그 점을 포함해서는 싸이클이 아니더라도 그 점을 빼고는 싸이클이 있을 수 있으니.. 무작정 true로 만들어버릴 수는 없는 노릇이다.

그래서 일단은 그 시작점만 true로 바꿔보도록 하겠다.
근데 여전히 시간초과...
음 그럼 싸이클이 안될 경우 전부 true로 할 수 있게 싸이클 판별 조건을 수정해야되나...

아 보니깐 내 cycle함수에서 방문해도true로 안바꿔버리는 것도 있고해서... 싸이클을 포함하는 싸이클이 아닌 것의 경우 무한반복이 될 수 있을 것 같다...
수정해야겠다...

생각해보니 .... 음.. 이게 어차피 한 노드에서 여러갈래가 나오는 게 아니므로...
방문한 점을 1로 해놓고, dfs하던 중 방문한 점을 또 만나게되면 싸이클이 있는 것이고..
그렇다면 여기서 구하고자하는 싸이클에 포함안된 점은 어떻게 구하냐?
싸이클이 생기면 즉 방문한 점을 또 만나게 되면 거기서 부터 dfs를 다시 해서 1씩 더해줘서 싸이클에 속해있는 점은 체크값을 2를 갖게 하는 것이지.. 그렇게 구별하는 거지..
한번 해보자.

음 아니구나 방문한 점을 만난다해서 싸이클이 있는게 아니지... 휴...
일단 싸이클은 그럼 첫 출발점과 같으면 있는 것으로 하고, 싸이클이 있을 경우
체크값을 2를 갖도록 해버리자.

음 역시 또 다른 문제가....
그래도 계속 고민하다보니 문제에 대한 이해도가 올라가고
풀릴 것 같다...

BOJ 2178

1, 1부터 시작하라고 했는데, 그리고 n, m까지 가는 거라고 했는데...
이걸 배열은 0, 0부터 이용하면서
이걸 진짜로 1, 1 과 n, m으로 사용하니 결과가 잘못된 것이었다.

0, 0 과 n-1, m-1로.. 다시 해보자.
 

BOJ 2331

그래프를 위한 vector의 크기를 전역변수로 잡으려고 하는데, vertex의 최대 개수가 주어지지 않아서... 어떻게 해야하지 생각하다가 일단 풀이먼저 하자는 생각으로 있었는데...
입력값이 9999가 최대이고, 지수가 5가 최대이므로...
9^5 * 4 = 59049 * 4 =236196..... 헐
음 그래프를 평소처럼 잡으면 안되려나.. 일단 엄청난 공간 낭비가 예상되는데...
2^5 + 3^5 + 6^5 + 1^5 + 9^5 + 6^5 = 32 + 243 + 7776 + 1 + 59049 + 7776 = 74877

74877 -> 50421 + 1024 + 32768 = 84213
84213 -> 243 + 1 + 32 + 1024 + 32768 = 34068...음 일단 236196 보다 커지지는 않을 수도 있을 것 같긴하지만..음 확실치 않아보인다.

그래서 그래프 표현방식을 edge를 표현 해주는 방식((예), a[9999]=236196, a[236196]=9999, 9999 vertex와 236196vertex의 연결이다)으로 하면 안될 것 같다는 생각을... 음 풀이를 일단 봐야겠다.

문제 풀어봐야겠다. 

백준님의 풀이를 보고 알게됨...
일단 내가 풀어본 그래프 문제들 처럼 그래프를 위한 자료구조를 할당할 필요가 없다. 
어차피 한방향으로 꼬리 물듯이 이어지는 그래프 모양이기 때문에
방문했는지 아닌지를 체크하는 check 배열만 있으면 된다. 
그리고 check배열에는 0 아니면 이 숫자가 몇번째인지 정보를 넣어주고(구하고자 하는 것이 반복되기 전 vertex의 개수이므로...) ...

그런데 왜 check배열을 1000,000만큼 선언했는지 잘 모르겠다.
한번 34068부터 해봐야지
34068 -> 3^5 + 4^5 + 0 + 6^5 + 8^5 = 243 + 1024 + 0 + 7776 + 32768 = 41811
아 근데 난 프로그래밍을 배운 사람인데 왜 이걸 손으로 하고 앉아있지...
프로그램을 짜서 돌려보겠다.

돌려보니... 



 
일단은 84213으로 다시 돌아가는것과..
음 그리고 236196이 가장 크네..
하지만 모든 경우의 수에서.. 예를들어 9998로 시작하면 236196보다 더 큰 수가 나올수 있다든가... 어떻게 예상하지..한번 질문해봐야겠다...
 

BOJ 10451

이 문제에서 말하는 순열은 1부터 n까지 중복없이 이루어진 수열, 즉 1부터 n까지가 한번씩만 나오는 거임...

그러다보니 결국 cycle이 생길 수 밖에 없는 것 같다.
그리고 cycle로 이루어져있는 그래프가 되어버리기 때문에 결국은 연결요소를 구하는 문제(BOJ 11724) 와 풀이법이 같아지는 것 같다.