8/21 (월) 풀이 제출 후 소요 시간 시각화하기 TIL, TIT

공부한 것

• LeetCode #234. Palindrome Linked List(팰린드롬 링크드 리스트)를 이어서 풀었다.

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

  https://leetcode.com/problems/palindrome-linked-list/description/?envType=list&envId=rus4c4ci

  

  지난 주 두 가지 풀이법은 공간을 O(N)만큼 추가로 필요로 하는 방법이었는데, 오늘 드디어 공간복잡도를 O(1)로 만들 수 있었다.

  • 내 풀이:

    // 공간복잡도를 O(1)로 낮추라고..? 어떻게 뒤집은 리스트도, 배열도 안 만들고
    // 순서를 비교할 수 있지. 일단 포인터를 끝으로 보낸다. 가는 동안 몇 개인지
    // 센다. 다시 앞에서부터 반절 위치 노드로 포인터를 보내서 반절을 자른다. 
    // 뒤 반절을 뒤집는다. 앞 반절과 뒤 반절이 같은지 확인한다...
    // Time complexity: O(N + N/2 + N/2 + N/2) => O(N)
    // Space complexity: O(1)
    function solution3(head) {
    	if (!head.next) return true;
    
    	// 1. 노드 개수를 센다.
    	let pointer = head;
    	let length = 0;
    	while (pointer) {
    		length++;
    		pointer = pointer.next;
    	}
    
    	// 2. 반절을 자를 수 있도록 pointer를 중간 지점으로 보낸다.
    	// 	=> 짝수 개인 경우: 총 길이 / 2 + 1 번째 노드로,
    	// 	=> 홀수 개인 경우; 총 길이 / 2 올림 번째 노드로. 
    	// 	==> 즉, '후 반절'의 시작 노드로 pointer를 이동시키는데 
    	// 예를 들어 총 노드 개수가 6개라면 4번째 노드부터, 7개라면 
    	// 4번째 노드부터 '후 반절'로 삼도록 한다.    
    	pointer = head;
    	for (let i = 0; i < Math.floor(length / 2); i++) {
    		pointer = pointer.next;
    	}
    
    	// 3. 후 반절을 뒤집는다.
    	// (짝수 개인 경우)
    	let lastHalfReversed = null;
    	while (pointer) {
    		let temp = pointer.next;
    		pointer.next = lastHalfReversed;
    		lastHalfReversed = pointer;
    		pointer = temp;
    	}
    
    	// 4. '뒤집은 반절'의 길이를 기준으로 전, 후 반절을 비교해나간다.
    	// 	 	= (총 노드 개수) / 2 를 올림한 수
    	for (let i = 0; i < Math.ceil(length / 2); i++) {
    		if (head.val !== lastHalfReversed.val) return false;
    		head = head.next;
    		lastHalfReversed = lastHalfReversed.next;
    	}
    
    	return true;	
    }

  • 다른 사람의 비슷한 풀이:

    // 다른 해답: Floyd's Cycle Detection Algorithm의 two pointers 응용
    // => '후 반절'의 첫 노드를 찾아 포인터를 위치시키는 방법만 다르고
    //		 나머지는 나와 똑같다. 노드 총 개수를 세느라 도는 한 바퀴를 
    //     절약할 수 있으므로 solution3보다 O(N)만큼 더 시간이 줄어든다. 
    //     그래봤자 결국 시간복잡도가 O(N)인 것은 같지만서도.
    // Time complexity: O(N/2 + N/2 + N/2) => O(N)
    // Space complexity: O(1)
    function twoPointersSolution(head) {
    	let slow = fast = head;
    	// fast 포인터에게 다음 노드가 존재하는 동안, slow는 한 칸, fast는 두 칸씩 이동한다.
    	while (fast && fast.next) {
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	// => fast는 마지막이나 마지막+1번째 노드(null)에서 멈추게 된다.
    	// 총 노드가 1개뿐이면 fast와 slow 모두 그대로 head이며,
    	// 총 노드가 2개 이상이라면: 
    	// 		짝수개일 때 fast는 (총 길이 / 2)번 점프하여 마지막+1번째에, slow는 같은 수만큼 점프하여 (총 길이 / 2) + 1번째 노드에 위치하고
    	// 		홀수개일 때 fast는 (총 길이 / 2) 내림 번 점프하여 마지막 노드에, slow는 같은 수만큼 점프하여 정중앙 노드(= 총 길이 / 2 올림)에 위치한다. 
    	// => 즉, slow는 현재 내가 푼 풀이3의 pointer와 같이 '후 반절'이 되는 첫 지점(총 노드 개수가 6개라면 4번째, 총 7개라면 4번째 노드)에 위치하게 된다. 
    	 
    	// lastHalfReversed라는 이름으로 '후 반절'의 첫 노드를 삼고 '후 반절'을 뒤집는다. 
    	let lastHalfReversed = null;
    	while (slow) {
    		let temp = slow.next;
    		slow.next = lastHalfReversed;
    		lastHalfReversed = slow;
    		slow = temp;
    	}
    
    	// fast와 slow 포인터를 각 반절의 첫 노드에 두고서 뒤 반절의 개수만큼 서로 비교한다. 
    	fast = head;
    	slow = lastHalfReversed;
    	while (slow) {
    		if (fast.val !== slow.val) return false;
    		fast = fast.next;
    		slow = slow.next;
    	}
    	// => 링크드 리스트를 반드시 보존하라는 조건이 없으니 head와 lastHalfReversed를 소비하며 비교할 수도 있지만, fast와 slow 포인터를 이미 만들었으므로 재활용해준다. ...
    	
    	return true;
    }

그림으로 그려보면 두 풀이가 ‘후 반절’의 머리로 삼을 포인터를 같은 곳에 두도록 배치하고 있음을 쉽게 알 수 있다:

내가 푼 해답(solution3)

다른 사람의 풀이(twoPointersSolution)

알게 된 것

• Floyd’s cycle Detection Algorithm (Floyd’s Tortoise & Hare Algorithm)

  어떤 연결 리스트가 순환하는지를 검사할 수 있는 방법이다. 아래 노트에 썼듯이 3가지 방식으로 응용이 가능하며, 다음 블로그에 잘 설명되어 있음: https://fierycoding.tistory.com/45.

  

  1. 어떤 연결 리스트가 null로 끝나는지 순환되는지(=두 개의 노드가 동시에 가리키는 노드가 있는지) 검사할 수 있다.
  2. 순환된다면 순환의 시작점을 찾을 수 있다.
  3. (1)을 응용하여, 어떤 배열에서 두 개의 중복되는 수가 존재하는지 검사할 수 있다.(배열 길이-1 이내의 값만 '수'로 가지는 배열일 때만 연결 리스트로 만들어 확인 가능) 배열에 담긴 수를 pointer로 치환하면 된다.

  근데 사실 저렇게 거창한 활용보다, 포인터 두 개를 하나는 한 칸씩 하나는 두 칸씩 뛰게 해서 중간 노드를 찾는 데까지만 Tortoise와 Hare를 이용하는 것을 더 많이 봤다. 어쨌든 새로운 이론을 알게 되어 좋다.

구상 중

• 문제풀이 코드 제출 후 실행 결과를 여러 개 모아서 시각화하는 방법을 드디어 본격적으로 궁리해보고 있다. 아 근데 글쎄 이런 단순한 작업도 잘 안 풀려서, node.js로 실행하려고 하니 막대 그래프를 이미지 파일로 저장하고 그 파일을 열어서 보는 방식으로밖에 안 되고, 브라우저로 실행하려니 LeetCode url에서 CORS 정책에 막힌다. 서버로 받는 CORS가 막지 않을 테니 일단 Express 서버를 간단히 만들어서 한 번 거쳐서(?) 브라우저로 렌더링을 해주는 방식을 써보려고 한다. 아 글쎄 근데 또 Express를 설치하는 데서도 애를 먹었다는 말씀…

[해결 완료] npm ERR! 502 Bad Gateway ✔️

발생 상황: $npm install express 프로젝트 폴더에서 터미널에 이 명령어를 입력하니 sill idealTree buildDeps 이런 문장이 뜨고 한참 동안 정지 상태이다가, 502 에러가 뜨고 실행이 멈춰버림.

에러 메세지 전문:

> npm i express
[..................] \ idealTree:04.0_test_and_play_모음: sill idealTree buildDep
(한참 후)
npm ERR! code E502
npm ERR! 502 Bad Gateway - GET https://registry.npmjs.cf/express

npm ERR! A complete log of this run can be found in:
npm ERR!     C:\Users\USER\AppData\Local\npm-cache\_logs\2023-08-21T10_19_26_239Z-debug-0.log

시도: 네트워크 연결을 다시 해보고, npm이 잘 설치되어있나 버전을 확인해 보았다. $npm cache clean --force 명령어로 npm 캐시를 지워봤다. 모두 실패였다.

원인: 에러 메세지에 힌트가 있었다. 502에러라는 건 서버쪽에서 응답하는 데 문제가 있었다는 얘기고, 친절하게 어느 url로 요처을 보내고 있었는지도 나왔는데 GET https://registry.npmjs.cf/express 이 주소가 문제였다.

해결: $npm config set registry https://registry.npmjs.org/ 이렇게 npm 레지스트리 url을 재설정해주니 install 명령어가 작동했다.

Uploaded by N2T