SLENDER ANKLES's 개발블로그

그래프 문제였다. 

핵심은 이거 였다. 

해당 학생의 키순서의 상대비교를 정확히 알기 위해서는 

내 앞에 있는 학생들과 연결되어있어야 하며

나보다 작은 학생들과도 연결되어야 한다.

dfs한번!

backtracking한번!을 수행하여

visited배열의 갱신되는 부분을 체크하여

모두 방문했으면 이 학생은 상대적인 키순서를 알 수 있는 사람이고

모든 버텍스를 방문하지 못 하는 경우에는 이 학생은 상대적인 키순서를 알 수 없는 사람이다.

이진 트리의 순회에 대한 개념을 알 필요가 있어 적어 둘려고 한다. 대학교 2학년 자료구조 수업에서 다룬것이었는데 거의 다 까먹었다. 뭐라는 것 정도만 알고 있는 정도다. 

트리의 순회를 이용하여 4칙연산과 같은 구현을 할 수 있다고 한다. 스택을 이용한 계산기 연산과 같은 부분에서 활용해봐야겠다. 

트리에는 전위 순회, 중위 순회, 후위 순회가 있다. 

- Pre order(전위)   : Root -> Left -> Right

=> Root로부터 왼쪽 모든 노드 탐색 후 오른쪽

24 15 2 19 28 27 30

- In order(중위) : Left -> Root -> Right

=> 맨 왼쪽 아래 노드부터 Root, 오른쪽 

2 15 19 24 27 28 30

- Post order(후위) : Left -> Right -> Root

=> 맨 왼쪽 아래노드부터 오른쪽 탐색 후 Root

2 19 15 27 30 28 24

완전이진트리의 순회를 이해하였다고 다 이해 한 것은 아니다. 

불균형 이진트리의 순회에 대해서 이해하는 것도 필요하다. 

- Pre Order(전위 순회)

A B D H E I C F G J K

- In Order(중위 순회)

H D I E B A F C J G K

- Post Order(후위 순회)

H D I E B F J K G C A

재귀적으로 호출하는 코드를 작성해보면서 더 정확하게 이해 할 필요가 있을 듯 싶다.

한 붓 그리기에 대한 공식을 명확히 알 필요가 있을 것 같아 정리해둘려고 한다. 

한 붓 그리기란 그래프의 어느 한 점에서 시작하여 모든 간선들을 한 번씩만 지나가는 

경우를 말한다. 

이 것에 대한 조건은 일단 두 가지로 나뉜다. 

1) 모든 정점이 가지는 간선이 다 짝수 개 일 때

2) 두 정점만 간선이 홀 수개를 가질 때 

이렇게 가능하다고 한다. 

한붓그리기의 경로를 뽑아내기 위해서는 dfs의 마지막 부분에 출력을 넣어주면 된다. 

뒤에서부터 출력하면 가능하다. 이 부분은 제대로 이해를 못 해서 직접 손으로 그려봐야겠다

특징

- 오일러 서킷

1) 모든 정점의 간선의 개수는 짝수여야 함(무향)

2) 들어오고 나가는 것이 있어야 됨(유향)

- 오일러 트레일

시작점과 끝점의 간선이 홀수개여야 함(무향)

(방향)

시작점 : 들어오는 간선이 나가는 것보다 하나 더 적어야 함

끝 점 : 들어오는 간선이 나가는 것보다 하나 많아야 한다.

더블릿 - 감 옥(jail)

첫 번째 죄수는 모든 방문을 연다.

두 번째 죄수부터는 자신의 방번호의 배수인 방번호를 열린것은 닫고, 닫힌것은 연다.

,....

데이터가 10만까지 들어온다고 한다. 

각 죄수마다 방문에 장난을 치는 동작을 iterative 하게 구현해도 되고, recursive하게 구현되도 되겠다고 판단했다.

데이터가 10만 까지인 것이 영 찝찝해봤는데

생각해보니까 자기 자신의 방번호의 배수마다 장난 을 치므로

10만개의 죄수 방중에서 5만번째의 죄수까지만 장난치는 것을 연산하고 그 다음부터는 어차피 아무 일도 할 수 없었다.

n/2번의 for문을 돌면서 해당하는 죄수들이 장난치는 결과를 재귀함수를 사용해서 수행해주었다. 

마지막에 한 번 전체 방의 상태를 체크해서 풀려난 죄수의 명수를 계산해주었다. 

더블릿 - 직사각형 면적

사각형 네 개의 좌표가 입력값으로 주어진다. 

문제에서 주어지는 좌표를 2차원 배열의 형태로 바꾸어주고 해당하는 배열의 인덱스에 1을 갱신하고 마지막에 1의 개수를 통해 넓이를 알아내겠다는 식으로 구현했다. 

약간 헷갈리는 부분이 문제에 있는 좌표를 배열화 해주는 부분인데

일단 x축을 기준으로 뒤집고 입력의 y값은 배열의 x(행)으로, 입력의 x값은 배열의 y(열)형태로 바꾸어주고 계산했더니 금방 답을 구할 수 있었다. 

======> (배열의 형태로)

이런식으로 바꾸어서 1의 개수를 계산해주면 답을 구할 수 있다. 

더블릿 - 오일러패스

오일러 패스에 대한 몇 가지 성질을 알고있어야 한다. 나는 외웠다. 

한 붓 그리기가 가능하기 위해서는 정점이 가지는 간선의 개수에 대한 조건이 맞아야 한다. 

한 정점이 연결된 간선의 수에서 홀수개가 연결된 것을 홀수정점, 짝개수가 연결된 것을 짝수정점이라고 하면,

1) 모든 정점이 짝수정점이면 오일러패스(한붓그리기) 가능!

2) 두 개만 홀수정점이고 나머지는 짝수정점이면 오일러패스(한붓그리기)가능!이다.

- 1)은 시작정점과 종료정점이 똑같다. 조건을 만족하는 한점에서 한붓으로 그리고, 종료되는 점이 자기 자신이다.

- 2)은 시작정점과 종료정점이 다르다.

여기까지만 알면 대충 그림이 그려졌다. 그런데 정작 오일러패스의 경로를 구하기가 힘들었다.

우선 dfs를 수행하면서 지나온 경로들을 삭제해준다. 이렇게 하니까 답이 안 나온다. 

내가 생각해낸 방법은 아니고 찾아봤더니, 거꾸로 출력하면 답이 나온다고 한다! 

예를 들어 dfs재귀함수 부분만 써보자면

<span style="color: rgb(51, 51, 51);">void dfs(int vertex){ for (int i = 1; i <= vertex_n; i++){ if (arr[vertex][i] == 1){ arr[vertex][i] = 0; arr[i][vertex] = 0; dfs(i); } } cout << vertex << " "; } </span>

와 같이 출력부분을 dfs수행 마지막에 넣어주면 꺼꾸로 출력이 되게 되는데 이 것이 답이 된다. 

더블릿 - 최단거리미로

bfs를 사용하는 문제이다. 

중요한 문제는 아니나 연속해서 배열 값들은 char 형태로 받아주어야 한다. 

또 배열의 초기화와 관련하여 길이 있는 부분은 0보다는 1이 낳으므로 문제에 주어진 부분에서

0으로 입력되는 부분을 1로 바꾸어주고, 1로 입력되는 부분을 0으로 바꾸어주어서 계산했다. 

그 이후에는 (n,1)에서 출발하여 bfs를 수행해주고 난 후에 (1,m)에 저장된 길이좌표를 알아내어 구현했다. 

더블릿 - 가장가까운조상

우선, 완전 이진 트리가 아니다. 

최대 10000개의 노드를 가질 수 있어 10000*10000배열을 사용하기에도 무엇인가 껄끄럽다.

간단히 계산해보니까 나의 코딩 방식으로는 엄청난 연산 횟수가 필요했다. 

그래서 노드간의 부모 자식과의 관계를 어떻게 저장할까에 대해서 생각해봤다.

다음과 같이 부모, 자식과의 관계를 나타내었다. 

node[버텍스개수] = {자신의부모버텍스, 자신의부모버텍, ....}

이런식으로 나타내었다. 배열의 인덱스는 해당 노드를 말하며, 그 배열의 값은 자신의 부모의 값을 가진다. 이렇게 되면 자신의 부모를 타고 올라가는 재귀적인 명령을 수행을 하는데 충분한 자료를 가지게 된다. 자식에 대한 정보는 필요 없어 저장하지 않는다.

그리고 입력 받은 두 개의 노드 중에 하나를 루트노드까지 재귀적으로 부모를 타고 올라가는 

수행을 하면서 그 리스트를 저장했다.

두 번째 입력 받은 노드를 또 다시 재귀적으로 부모를 타고 올라가면서 앞써 저장된 리스트의 값들과 비교했다. 만약 있으면 그 값을 저장하고 재귀함수를 멈추었다. 

** 시그를 통해 알게 된 것인데 이 문제는 우선 숫자들을 나열해보고, 그 것의 수열에서 나오는

특징에 대해서 파악해보면 공통적인 부분을 찾을 수 있게 된다. 그 것을 통해 답을 아주 간단히 풀 수 있다. 

문제를 보고서 sort의 방법중에 최소시간이 걸리는 방법을 찾으라는 것인가?라고 생각했다.

퀵소트를 구현하는 것인가 했지만, 

2 3 5 4 1

=> 1 3 5 4 2

=> 1 3 2 4 5

=> 1 2 3 4 5

위와 예제를 보면 내가 생각했던 방법은 아니다... ???

** 시그를 통해 알게 된거 swap을 최소로 하는 것은 선택정렬 방법이다. ** 

우선은 선택정렬을 하는 방법으로 구현해 보고 안 되면 퀵소트라던지 힙소트라던지 구현해야 되겠다고 생각했다. 

내가 세운 방법은 이 것이다.

[]은 확정된 값들을 말한다.

2 3 5 4 1 중에 최소값을 첫 번째 배열에 넣는다.

=> 1 3 5 4 2

[1] 3 5 4 2 중에 최소값을 두 번째 배열에 넣는다.

=> [1] 2 5 4 3

[1] [2] 5 4 3 중에 최소값을 세번 째 배열에 넣는다.

=> [1] [2] [3] 4 5

.....

swap되는 카운트를 세는 것이 문제이기 때문에

간단한 조건을 하나 걸어주었다. 

최소값이 자기 자신이면 swap을 하지 않는다는 조건이다.

이렇게 하면 답이 나온다.

- 특정 사이트에서 특정 검색어를 찾고 싶은 경우

site:www.acmicpc.net 점화식

- 마이너스(-)를 이용하여 특정 검색어 제외하기

삼성 -갤럭시

- 특정 파일 형식만 검색하기

슈퍼마리오 filetype:torrent

- 검색어가 타이틀이 아닌 본문 안에 있는 것을 찾아서 리턴해주는 경우

intext: 검색어

- and와 or, not을 사용

* and : “and” 또는 공백(주로 공백)으로 입력

<활용 예시>

1) intext:"APPLE" "iPhone6" → 문서내용에 “APPLE”라는 문자열을

포함하고, 문서의 제목과 내용에 “iPhone6”이라는 문자열을 포함하는 문서 검색

2) intext:"APPLE" intext:"iPhone6" → 문서내용에 “APPLE”라는

문자열과 “iPhone6”이라는 문자열을 포함하는 문서 검색

* or : 대문자 “OR” 또는 “|”를 입력

<활용 예시>

1) intext:"MacbookPro" OR intext:"Retina" → 문서내용에 “MacbookPro”

또는 “Retina”이라는 문자열을 포함하는 문서 검색

* not :“-”으로 입력

<활용 예시>

1) intext:"SmartWatch" -"Samsung" → 문서내용에 “SmartWatch”라는 문자열을

포함하고 있고, “Samsung”이라는 문자열은 포함되어 있지 않는 문서 검색

생각은 쉬운데 코딩하는게 까다로웠다?

생각도 물론 처음은 쉽지 않았다. 

1차원적인 생각으로 큰 사각형에서 작은 사각형을 빼서 답을 구해야겠다고 생각했다.

But, 어떻게 작은 사각형을 구하는지가 난감했다. 

조금 생각을 해보니, 둘레를 반시계방향으로 돈다는 조건을 통해서 작은 사각형을 구할 수 있었다. 

가장 긴 가로변, 가장 긴 세로변의 인덱스를 구한다.

둘 중에 나중에 나오는 변의 인덱스 + 2, 둘 중에 나중에 나오는 변의 인덱스 + 3 번

째의 변들을 곱해주면 작은 사각형을 구해 줄 수 있었다. 

다른 방법들이 많겠지만 나는 이 방법을 택했다. 

솔직히 이상적인 생각인지는 모르겠다. 몇 가지 예외를 처리해주어야 했다. 

1) 가장 긴 가로변인덱스와 가장 긴 세로변인덱스가 첫번째와 마지막인덱스에 배치되어있는 경우가 예외이다.

를 생각해야 한다. 말로 하기가 힘들지만 그림을 그리기는 너무 귀찮아서,,, 

이부분은 나중에 보더라도 이해해야 되는 부분 같다. 아무튼, 단지 인덱스의 크기만을 비교해서는 안된다는 것이다.

인덱스 크기만을 비교해서는 인덱스 크기가 더 큰 변이 우리가 구해줘야 하는 변 같지만 사실은 정반대라는 것이다.

조금 생각을 더 해야 된다는 것이다. 몇 번이고 답이 안 나왔는데 그래서 잘 못 풀었나 생각했는데

적어도 모양에 따라 2~3번 실제로 손으로 써보고 직접 코드를 따라 내려가면서 나의 잘못된 코드를 바로 잡았다. 

어쨋든 좋은 문제인거 같다. 까다로운 문제로서는

정답률이 그리 낮지 않은 문제인데 푸는데 정말 오래걸렸다. 

다른 프로젝트를 하고 있어서도 그랬지만 문제를 풀어가서 답을 구하는데 오랜시간이 걸렸다.

1. 우선 처음에 2차원 배열로 해야되나? 생각했는데 40000 * 40000이라서 이건 아닌거 같애서 이 방법은 넘겼다.

2. 개미의 진행방향과 시간을 인자로 가지는 재귀함수를 호출해서 구하면 어떨까?

=> 구현했더니 예제에 대한 답이 나왔다! 오호

3. But 시간 초과가 났습니다. ㅠㅠ 재귀함수 호출을 무지막지하게 해야 되는 방법이라는 것을 깨달았습니다.

4. 개미가 한 바퀴를 돌고 또 도는 동작이 있다는 걸 발견했습니다. 이렇게 되면 200000000이런식의 수행횟수를 돌아야 하더라도

재귀 호출 횟수를 엄청 줄여 줄 수 있다고 생각했습니다.

그래서 재귀함수 호출을 하는 소스를 사용하면서 위의 사이클을 발견해서 그 부분의 계산량을 줄여주었습니다.

그런데도 시간초과 ㅜㅜ 

시간 초과를 극복 할 수 있는 방법으로 문제를 풀어야 했지만 그에 마땅한 방법이 떠오르지 않아 고생하였다. 

그래서 백준 질문 게시판을 이용해서 약간의 해답을 얻고 답을 풀었다. 

5. 나는 이 문제를 일종의 배열을 한칸한칸 재귀적으로 나가는 방법을 사용했는데, 그 것이 함정이었다. 

x, y 좌표가 이동하는 할 때 벽을 부딪히는 것을 한 번의 재귀수행으로 풀어나가야 했던 것이다. 

간단히 말해 벽해 부딪힐 때까지 한 번에 진행하는 방식으로 문제를 풀어나갔더니 답이 나왔다. 

이렇게 벽을 부딪히는 것을 기준으로 재귀를 수행하게 되면 기존의 방법에 비해 훨씬 더 저렴히, 시간을 쓰면서 답을 해결해나갈 수 있게 된다. 이러한 방법을 생각해내지 못 했던 것이 안타까울 뿐..

물론 소스코드는 간단 명료 하진 않은데 이 부분은 답을 맞췄으니 다른 사람들의 코드를 참고하며 좀 더 보완해야 될 점이다. 

재귀 함수를 수행하는 부분을 간단히 설명하자면, 

void ant_movement(int x, int y, bool garostate, bool serostate, int movehour);

이런 구조를 갖는 재귀 함수를 설계했다. 

garostate와 serostate에 대해서 설명하자면

garostate는 x좌표가 오른쪽으로 이동 상태인지, 왼쪽으로 이동 상태인지를 나타낸다. 

serostate는 y좌표가 위쪽으로 이동 상태인지, 아래쪽으로 이동 상태인지를 나태낸다.

현재 좌표점에서 이동 방향중에 위 아래면을 먼저 부딪히게 되면, y좌표의 상태를 바꾸어주고

현재 좌표점에서 이동 방향중에 왼,오른쪽면을 먼저 부딪히게 되면, x좌표의 상태를 바꾸어준다.

이렇게 되면 재귀를 수행하게 되면서 문제에 제시된 특성을 가지면서 이동 할 수 있게 된다. 

이러한 코드를 작성하면서 간단명료하게 코드를 작성해주진 못 했지만 로직적으로는 문제 없는 코드를 만들어내었다. 

한 가지 더 고려해야 될 점은 

재귀를 수행하면서 다음 벽에 부딪히게 되기 전에 최종 시간이 되버리는 케이스가 있게 되는데 

예를 들어 재귀함수에서 수행하는 부분은 다음 벽까지 이동하는 것인데 다음 벽까지 이동하기 전에 답이 구해져야 된다. 마지막에 꼭 거치는 부분이다. 이 때는 (최종 목표 시간 - 현재까지의 이동 시간)으로 목표점의 좌표를 구할 수 있게 된다.  마지막 재귀를 마무리 하게 되는 basecase가 되는 것이다. 

설명이 길었지만 이런식으로 문제를 풀어나가게 되면 답을 구할 수 있게 된다. 

풀고 나니까 쉬웠지만 쉽게 풀지 못 한 문제였다. 

우선 windows에서 express로 프로젝트를 만드는 것과 우분투 리눅스에서 만드는 것은 버젼이 너무 상이했다. 

호환이 안 되었다. express만 해도 윈도우에서와 다르게 

4.X.X버젼을 사용하는 리눅스 nodejs에서 app.use(app.router)?? 등과 같은 명령은 동작하지 않았다. 

안 쪽의 소스코드를 바꾸는 것은 너무 골치아프고 시간을 낭비하는 느낌이라서 윈도우의 프로젝트 자체를 우분투로

옮기고 mongodb 모듈만 npm install했더니 정상적으로 돌아간다. 

버젼의 중요성과 개발환경에 대한 중요성을 다시 한 번 느꼈다.

로보몽고, 몽고뷰를 아마존에 설치된 몽고디비에 연결하려는 환경세팅이 필요했다.

그런데 연결이 되지 않았다. 구글에서 찾은 방법으로 되지 않아 몽고뷰(mongovue)로 툴을 바꾸어서 시도해보았다.

역시나 안되었다. 그래도 다행히 몽고뷰 사이트에서 이 문제에 대한 원인과 해결방법을 정리해놓았다. 

http://www.mongovue.com/2011/08/04/mongovue-connection-to-remote-server-over-ssh/

여기에 자세히 스텝이 정리되어있다. 

대충 설명해보자면 

AMAZON AWS와 같은 클라우드 인프라에서는 보안 상의 이유로 FTP를 통해 몽고뷰나, 로보몽고에서 바로 연결을 안 되게 해놓았다는 것 이다. 그래서 FTP를 로컬 디비 포트와 서버의 디비 포트를 연결하는 방법을 통해 꼼수(?),,, 인지는 모르겠지만 특정 방법을 통해 연결을 가능하게 했다. 

주의 해야 할 점은 나는 로컬에서 12707이라는 포트로 로컬디비서버를 돌리고 있었으므로 몽고뷰 웹사이트에서 설명하는 다음의 방법을 연결하는데 충돌이 났다. 이 것으로 거의 반나절을 고생했던 듯 하다. 좀 더 원리를 이해하고 했다면 이 같은 문제를 줄일 수 있지 않았을까 싶다. 

Putty를 통해 터널링에서 로컬 디비 포트를 올려주는 방법이라는 설명과 함께 다음과 같은 방법으로 실행이 가능하다.

1. Connection >> SSH >> Tunnels 를 실행하여

2. Source port 를 5151, Destination을 127.0.0.1:27017로 설정하고 IPv4 라디오버튼을 클릭해 놓고

Add버튼을 누른다.

3. Session 탭으로 복귀하여 aws의 IP주소를 입력하고 

ec2에 주어지는 인증키 pem파일을 불러와 putty gen 이라는 곳에서 ppk 파일로 변환하여

ppk라는 파일을 통해 연결에 대한 인증을 수행하고

Session을 Open한다. 

4. 포트번호를 적고 기본적인 정보를 입력(입력 안해도 되는 것 같음, 경고창 뜨면 그 부분만 입력해주면 된다.)

하고 접속을 시작한다. 

5. 연결이 성공하여 몽고db를 GUI로 관리 할 수 있는 mongovue를 실행 할 수 있게 되었다. 

로보몽고도 이 같은 문제가 발생했던 듯하다. 

** 내가 하루종일 안 됐던 이유는 로컬 몽고디비의 로컬 포트와 

위의 동작에서 연결하는 포트가 같아서 충돌이 일어났던 듯 하다. ㅜㅜ

그래서 로컬몽고디비의 포트를 default포트(27017)이 아닌 다른 포트로 바꾸어 주었다. 

로보몽고(robomongo)에서도 같은 방식으로 접근하면 된다는 것을 알았다!!