오늘 한 일
- leetcode
- Next Permutation (medium)
- 실내 운동
문제 풀이
Next Permutation (medium)Github
입력된 permutation 배열을 보고 다음 차례의 permutation 배열을 돌려주는 문제.
풀이 시도 1
가장 단순한 케이스는 모든 permutation 배열을 만들고 거기서 다음 차례를 골라내는 것일테지만(시간초과는 예정되겠지만.) 그래도 목표값을 직접 구하는 방식을 찾고 싶어서 다음과 같이 구상하였다. 다음 퍼뮤테이션 배열을 찾는 과정에는 두가지로 나뉘는데 하나는 첫 값이 바뀌는것 과 그이후값이 바뀌는 것이다. 그리고 첫값이 바뀌는 경우는 첫값을 제외한 값이 내림차순으로 정렬 될때이다.(퍼뮤테이션 순서를 오름차순으로 센다고 하였으므로)
따라서 해당 경우에 대해서만 첫값의 변경을 고려하고 그외의 경우는 첫값을 제외한 나머지값에서 내림차순이 오름차운스올 변경되는 지점을 포착하고 해당 지점에서의 값을 바꿔주면 되게끔 코드를 고안하였다. 다만 동일한 값들이 여러개 있는 경우에대해서는 고민하지 못했으므로 해당 예시가 나온시점에서 풀이에 대한 고민을 다시 해봐야겠다.
풀이중
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
-
코드샌드박스를 활용한 서버 배포
학습 진행
오늘은...
휴식 + 다음 작업 기초 잡아보기
새로이 레포지터리 생성하고 어떻게 작업을 진행할것인지 고민해보았다. 고민 결과는 별도의 페이지에 작성하였으며 세부적인 부분은 좀더 고민해봐야겠다.
진행 중단중인 프로젝트
socket.io - chatapp
홈페이지 만들기
pathfinder(미로 길찾기 게임)
