벌써 13일 이라니... 요새 저녁에 너무 늦게자서 그런가 아침에 일어나는 일이 너무 힘겹다... 오늘은 진짜 못일어날뻔...
시간을 너무 버리는 것 같다. 더 효율적으로 쓸 순 없을까...ㅜㅜㅜ
n-queen
알고리즘 끝까지 공부하자...
머릿속으로 공부하고 수도코드 적고 코드를 많이 써보자!
알고리즘이란 주어진 문제를 해결하기 위해 일련의 절차들을 정의한 것.
이번 과제는 n개의 queen을 체스판에서 서로 공격하지 못하게 위치시키는 문제다.
퀸을 구현하기 전에 rooks라는 것 또한 체스판에서 서로 공격을 못하게 위치시키는 것도 추가되었다.
rooks는 가로와 세로방향 어디든지 움직일 수 있다.
Queen은 대각선 방향 또한 움직일 수 있다.
우선 코드를 구현하기 전에 어떤 형식으로 구현을 해야 할 지 전략을 세웠다.
-
충돌의 발생은 같은 행이나 열에 있거나 대각선에 있을 때, 충돌이 발생한다고 한다.
-
깊이우선탐색을 사용하여 탐색을 하다가 백트랙킹을 사용하여 다시 부모 노드로 돌아가게 한다.
백트랙킹이란, 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때만 살펴본다. 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색한다.
우선 이런 식으로 구성을 한 것 같다. 알고리즘의 구현은 내일 마무리 할 것 같다.
4명이서 팀으로 조금 주어진 코드를 분석하는 것과 어떤 식으로 문제를 풀어야 할 것인가에 대한 이야기를 나누었다. 더 적극적으로 참여할 수 있었는데 아쉬운 부분이긴 하지만... 기술적인 것 보다 다들 열정적으로 임하는 모습에 조금 더 리마인드 해준 시간이었다.
반복하지 않는 String
문자열 내에서 최초로 반복하지 않는 문제를 return하는 알고리즘을 작성하였다.
수도코드
1. 전달인자로 들어오는 string을 배열의 형식으로 바꾼다.
2. 초기값을 {}로 설정한 reduce를 사용하여 if(acc[cur])면 1로 할당 아니면 += 1
3. 2번에서 만들어진 객체의 밸류가 1인 것을 return.
코드는 잘 돌아 갔다.
다른방법을 사용하는 방법도 있는데
1. 배열로 만든다.
2. for문을 배열의 크기만큼 돌린다.
3. for of로 배열의 요소를 가져오고 배열의 요소가 있으면 count를 증가시킨다.
4. 최종 count가 1인 요소를 찾으면 즉시 return.
