흙금이네 블로그

자바스크립트는 자료의 타입은 있지만 변수에 저장되는 값의 타입은 언제든 바꿀 수 있는 동적 타입 언어다. let message = 'hello'; message = 123; 숫자형은 정수 및 부동소수점 숫자를 나타내며, 대표적인 관련 연산으로 곱셈(*), 나눗셈(/), 덧셈(+), 뺄셈(-)이 있다. 일반적인 숫자 외에 Infinity, -Infinity, NaN과 같은 특수 숫자 값도 숫자형에 포함된다. alert(1/0); // 무한대 alert(Infinity); // 무한대 NaN에는 어떤 추가 연산을 하더라도 NaN이 반환된다. alert('문자열'/2); // NaN alert('문자열'/2+5); // NaN 숫자형은 2^53-1(9,007,199,254,740,991)보다 크거나 -(2^5..

아이디어 최소 공통 조상을 찾을 때까지 번호가 큰 노드를 부모 노드로 이동한다. 풀이 K가 1인 경우 두 노드의 거리는 노드 번호의 차이이므로 x와 y의 차이를 출력한다. K가 2 이상인 경우 함수 find을 호출하여 두 노드의 거리를 출력한다. 함수 find는 while문에서 두 노드 중 번호가 큰 노드를 부모 노드로 이동하고, 최소 공통 조상을 찾는다. 최소 공통 조상을 찾는 동안 while문이 돌면서 거리를 증가시키고, 그 거리를 반환한다. (노드 번호-2)//K-1의 식을 통해 해당 노드의 부모 노드 번호를 계산할 수 있다. import sys input = sys.stdin.readline def find(x, y): d = 0 while x != y: if x < y: y = (y-2)//K+..

자바스크립트에서는 변수 선원과 값 할당을 한 줄에 작성할 수 있다. 그러나 권장하는 방법은 아니며, 가독성을 위해 한 줄에 하나의 변수를 작성하는 것이 좋다. let name = 'John', age = 27, message = 'Hello'; let name = 'John'; let age = 27; let message = 'Hello'; let name = 'John', age = 27, message = 'Hello'; 변수를 두 번 선언하면 에러가 발생한다. let message = 'OK'; let message = 'Error'; // SyntaxError: 'message' has already been declared let message = 'OK'; message = 'No Error..

지난 12월 20일 수료식이 있었고, 12월 30일 부로 SSAFY 7기의 모든 일정이 끝났습니다. 이번에는 싸피 2학기까지 모두 마치고 수료한 후기를 작성해보려 합니다. 성과 1일 1알고리즘 프로젝트를 진행하며 바쁜 와중에도 매일 한 문제씩은 알고리즘 문제를 풀려고 노력했습니다. 바쁘다는 핑계로 쉬운 실버 문제를 위주로 풀었더니 감이 많이 떨어진 것 같습니다. 요즘에는 다시 골드 이상 난이도의 문제에 도전해보고 있습니다. 1일 1커밋 깃허브에 매일 푼 알고리즘 문제 코드를 올렸습니다. 이제는 잔디 강박이 생길 정도입니다. BOJ, 프로그래머스 각각 600문제, 100문제 이상 해결 주로 BOJ는 파이썬, 프로그래머스는 자바스크립트로 문제를 풀고 있습니다. 프로젝트 우수 2학기에는 공통, 특화, 자율 이..

아이디어 희소 배열을 이용하여 쿼리 수행 시간을 단축한다. 풀이 희소 배열 f의 첫 행에 입력 받은 값들을 저장하고, for문을 돌면서 동적 계획법으로 희소 배열의 행을 추가해 나간다. 희소 배열의 행 크기는 n이 범위를 넘지 않도록 19로 설정했다(2^19 = 524,288 > 500,000). 차례로 n을 1과 AND 비트 연산하여 각 자리값에 따라 희소 배열 f에서 계산된 값을 찾아 나가도록 한다. import sys input = sys.stdin.readline m = int(input()) f = [[0]+list(map(int, input().split()))] for i in range(1, 19): f.append([]) for j in range(m+1): f[-1].append(f[-..

아이디어 최소 공통 조상 알고리즘을 이용해 가장 가까운 공통 조상을 알아낸다. 풀이 너비 우선 탐색 함수 bfs에서는 트리를 탐색하며 현재 노드의 깊이, 부모 노드를 저장하도록 한다. 최소 공통 조상을 찾는 함수 find는 두 노드의 깊이를 일정하게 맞춘 뒤, 공통 조상을 찾아 반환한다. 딕셔너리 memo에는 이미 조상을 찾았던 두 노드의 최소 공통 조상을 저장해두어 find 함수를 재호출하지 않도록 한다. 입력 받은 간선들을 2차원 리스트 graph에 추가한 후, 함수 bfs를 호출하여 노드 깊이와 부모 노드 정보를 저장한다. M개의 두 노드에 대한 최소 공통 조상을 찾아 출력하고, 메모이제이션을 통해 실행 시간을 단축한다. import sys input = sys.stdin.readline def b..

아이디어 투 포인터로 좋은 수의 개수를 센다. 풀이 리스트 numbers에 입력 받은 숫자들을 정렬하여 저장한다. for문에서 현재 수를 numbers에서 제외한 후 search 함수를 호출하여 반환값을 결과값 res에 더한다. search 함수가 종료되면 제외했던 현재 수를 다시 numbers에 추가하는 식으로 for문을 반복한 후 결과값을 출력한다. search 함수는 numbers의 두 수를 더해 찾고자 하는 수를 찾으면 1을 반환한다. 시작 인덱스 s와 끝 인덱스 e에서 s가 e보다 작은 동안 반복하며, 현재 수를 찾지 못하면 0을 반환한다. def search(num): s = 0 e = N-2 while s temp:..

아이디어 크루스칼 알고리즘을 사용한 최소 신장 트리로 집을 모두 연결한 최소 비용을 전체 비용에서 뺀다. 풀이 최소 신장 트리를 구현하기 위해 집합을 찾는 find 함수와 두 집합을 합치는 union 함수를 정의한다. 집의 수는 M, 길의 수는 N으로 입력 받고, while문은 집의 수 M이 유효한 동안 반복된다. 길에 대한 정보를 거리 순으로 정렬한 road 리스트를 만들고 유니온 파인드로 두 집이 연결되지 않았을 때 연결한다. road 리스트를 만들 때 전체 비용 합을 res에 저장해두고, 두 집이 연결될 때마다 res에서 해당 비용을 뺀다. 연결된 횟수(간선 개수) cnt가 M-1이 되면 for문을 종료하고 결과값 res를 출력한다. import sys input = sys.stdin.readlin..

아이디어 최소힙과 최대힙의 두 가지 우선순위 큐를 사용하여 중앙값을 찾는다. 풀이 최대힙 left와 최소힙 right를 빈 리스트로 생성하고, 처음 입력 받는 값을 중앙값 mid로 저장한다. 이후 중앙값과 비교해 작거나 같은 값은 최대힙 left에, 큰 값은 최소힙 right에 push한다. 두 힙의 크기가 2 이상 차이나는 경우 현재 중앙값은 크기가 작은 힙에 push하고, 크기가 큰 힙에서 루트 노드를 pop하여 중앙값을 새롭게 바꾸고 힙의 균형을 맞춘다. 홀수 번째 입력 때마다 중앙값을 결과값에 숫자를 문자열로 추가하고, 조건에 따라 개행 문자를 추가한다. import sys, heapq input = sys.stdin.readline T = int(input()) for t in range(T):..

아이디어 투 포인터로 두 수의 차이가 M 이상일 때를 찾는다. 풀이 값의 차이만 알면 되므로 셋으로 입력 값들의 중복을 제거한 후 정렬된 리스트 A로 변환하고 그 길이를 N으로 저장한다. 투 포인터로 두 수의 차이와 M을 비교하며 M을 초과한 경우에 결과값과 비교해 더 작은 값으로 갱신해 나간다. 차이가 M인 경우는 더 이상 탐색할 필요가 없으므로 결과값을 M으로 저장 후 반복문을 종료한다. import sys input = sys.stdin.readline N, M = map(int, input().split()) A = set() for _ in range(N): A.add(int(input())) A = sorted(A) N = len(A) s = e = 0 res = A[-1]-A[0] while..