오늘 한 일
- leetcode
- Next Permutation (medium)
- 실내 운동
문제 풀이
Next Permutation (medium)Github
입력된 permutation 배열을 보고 다음 차례의 permutation 배열을 돌려주는 문제.
풀이 완료
풀이방법을 바꾸어 보았다. 현재값과 다음값을 비교하는것은 동일하다. 다만 이과정을 재귀함수적으로 사용하는 방식으로 수정 하였다.
우선 재귀함수를 통하여 현재 배열의 크기를 재고 2이상이면 앞의 값을 떼어낸 배열을 재귀함수에 넘겨 준다. 크기가 2이하 일때까지 내려가고 크기가 2가 되면 앞의 값과 뒤의 값을 비교한다.
앞의 값이 크면 true를 반환하고 뒤의값이 크면 두 값의 위치를 바꿔준뒤 false를 반환한다. 2이상의 재귀함수에서 해당 결과를 받으면 우선 결과가 true 이면서 잘라낸 앞의 값과 나눠진 뒤 배열의 첫값을 비교한 결과가 뒤의 값이 큰경우에 대해 현재 앞의 값다음으로 큰수를 찾고 나머지 값들을 오름차순으로 정렬한뒤 순서대로 배열의 값을 대체하게 한다.
위 경우가 아닌경우 재귀함수의 결과가 true와 일치하는 경우에만 true를 반환하게 한다. 이후과정은 동일하다. 재귀함수의 최상단에 도달하여 결과가 나왔을때 결과가 true라면 입력된 배열의 모든값이 내림차순으로 정렬 되었다는것을 의미한다.
이 경우 다음 permutation은 오름차순으로 정렬된 첫번째 permutation이다. 따라서 주어진 배열을 오름차순으로 정렬한다.(현재문제는 결과를 받지 않고 입력된 배열의 순서만을 바꾸기를 요구한다. javascript의 sort는 대상을 수정하는 정렬 방식이기에 문제에 유효하다.)
풀이중
Smallest String With Swaps (medium)Github
문자열이 주어지고 페어관계가 있는 인덱스 배열이 주어진다. 이를 통하여 만들수 있는 사전적으로 가장 작은 단어를 만들라.
최적의 행렬 곱셈 (Level 3)Github
주어지는 행렬 크기 배열을 행렬 곱을 진행하여 연산횟수를 구하였을 때 최소의 연산횟수를 돌려주는 문제.
문제가 되는 예문
// 테스트 2
입력값 〉 [[7, 1], [1, 6], [6, 6], [6, 5], [5, 8], [8, 9], [9, 9], [9, 2], [2, 1], [1, 9]]
기댓값 〉 349
풀이과정 :
1. [7, 1]
2. [[1, 6], [6, 6], [6, 5], [5, 8], [8, 9], [9, 9], [9, 2], [2, 1]] 279
3. [[7, 1], [1, 1], [1, 9]] => 7*1*1 + 7*1*9 =70
4. 279 + 70 = 349
// 테스트 3
입력값 〉 [[3, 9], [9, 5], [5, 2], [2, 2], [2, 7], [7, 4], [4, 5], [5, 9], [9, 4], [4, 6]]
기댓값 〉 498
풀이 과정 :
1. [[3, 9], [9, 5], [5, 2]], [[2, 2]], [[2, 7], [7, 4], [4, 5], [5, 9], [9, 4], [4, 6]] 로 나누어 나누니것끼리 우선 계산.
2. [[3, 2], [2, 2], [2, 6]] 을 얻을수 있으며 이때의 연산횟수는 450이다.
3. [[3, 2],[2, 2]]을 먼저 연산하고 나머지를 연산한다. 이 경우 12 + 36 으로 총 48의 연산 횟수를 얻게 된다.
4. 따라서 최종적으로 498의 현산횟수를 가지게 되며 이는 예측된 최소값과 일치한다.
추후 진행 예정인 작업
-
socket.io 서버로 하는 단순한 멀티 룸 채팅.
-
위의 결과를 server-side로 구현해보기.
-
코드샌드박스를 활용한 서버 배포
학습 진행
오늘은...
graphql 학습
클라이언트의 wireframe을 구성하고, client에서 사용할 graphql의 스택을 확정하였다. 또한 임시적으로 서버와 클라이언트를 구동하여 서버와 클라이언트의 연결을 확인하였고, db와 qraphql을 연결하는 방법에 대한 reference를 확보할수 있었다.
graphql을 보면서 DB와 는 어떻게 연결하는가에 대해 궁금했었는데 reference를 통하여 해당 궁금증을 해소 할수 있었다.
진행 중단중인 프로젝트
socket.io - chatapp
홈페이지 만들기
pathfinder(미로 길찾기 게임)
