오늘 한 일
- leetcode
- Smallest String With Swaps (medium)
- 실내 운동
문제 풀이
Smallest String With Swaps (medium)Github
문자열이 주어지고 페어관계가 있는 인덱스 배열이 주어진다. 이를 통하여 만들수 있는 사전적으로 가장 작은 단어를 만들라.
풀이 시도 7
이번 풀이는 바꿀수 있는 그룹을 구분해보았다. 방식은 union find 방식을 차용하였고 주어지는 문자열 길이의 배열을 만들고 내부 요소를 자기자신을 가리키는 index로 초기화 한뒤 주어진 는 페어 관계로부터 자기 자신의 부모요소를 비교하여 그룹나누기를 수행하는 것이다.
위과정으로 그룹이 나누어지면 각 그룹의 문자들을 모으고 정렬 한뒤 각 그룹에 배정된 위치에 순서대로 입력하는것이다. 이는 주어진 조건하에서 가작 작은 문자열을 만들수 있는 방법이다.(그중간에 어떻게 섞는지는 모르지만...)
이러한 방식으로 주어진 36개의 예문중 34개를 풀이하였다.(지금까지의 시도 중에는 최고 기록이다.)
하지만 풀이 실패의 원인은 시간초과, 무지막지한 길이의 문자열로부터 위의 과정을 계산하고 답을 내는데에는 충분한 시가적 효율이 나오지 않는듯하다. 좀더 시간적으로 빠르게 처리할수 있는 방식을 찾아봐야겠다.
풀이중
최적의 행렬 곱셈 (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 학습
우선 DB는 연구프로젝트에서 사용한 mongodb와 mongoose를 사용할 것이고, 그에 맞추어 임시로 잡아두엇던 스키마를 구성해보았다. 정작 스키마를 구성하면서 생각해보니 만들어진 스키마의 데이터가 graphql의 쿼리를 하기위한 스키마 구조와 적용상에 문제점은 없을까하는 생각이 들었다.
해서 예정보다 빠른 graphql의 학습을 시작하였다. 우선은 graphql dml 스키마 구성 resolve 생성 정도를 확인하고 테스트를 하며 학습을 진행하였다.
별외로 홈페이지 프로젝트에서 사용하고자하는 마크다운 문서의 페이지화에는 마크다운 형식을 일일히 해석해서 html화 하는것도 공부할여지는 있어보이지만 그걸 직접 구현하기보다는 이미 구현된 package를 찾아서 적용하는 방향으로 결정하였다. 이제 문제는 어떤 package를 선택하느냐이다..
진행 중단중인 프로젝트
socket.io - chatapp
홈페이지 만들기
pathfinder(미로 길찾기 게임)
