스터디기록일지

개인정보 수집 유효기간 조건 정리today: 오늘 날짜 (YYYY.MM.DD)terms: 각 약관 종류와 유효기간 (단위: 개월)privacies: 수집일자와 약관 종류모든 달은 28일로 고정되어 있으며, 즉 1개월은 28일, 1년은 12 * 28 = 336일로 계산하면 된다. 풀이 접근 방법today 입력을. 을 기준으로 split('.'). map(Number)날짜를 year * 12 * 28 + month * 28 + day 이렇게 변환하는 메서드 calDaystoday = [year, month, day] => calDays메서드로 변환 terms => 객체로 변환 {'A':6}for(let i=0; i let [days, term] = privacies.split(' )days => calDay..

가장 많이 받은 선물 문제 요약두 사람이 선물을 주고받은 기록이 있다면:더 많이 준 사람이 → 선물을 하나 받는다.두 사람 간 선물 기록이 없거나 같다면:**선물 지수(=준 선물 수 - 받은 선물 수)**가 더 큰 사람이 → 작은 사람에게 선물을 하나 받는다.선물 기록도 없고, 선물 지수도 같다면:아무 일도 일어나지 않는다.최종적으로 다음 달에 가장 많은 선물을 받는 친구가 받을 선물 수를 구해야 한다풀이 로직 1. 데이터 구조 설계giveTakeTable: [i][j]는 i가 j에게 준 선물의 수를 저장하는 2차원 배열이다.giftCountTable: 각 친구에 대해 [준 선물 수, 받은 선물 수, 선물 지수]를 저장하는 배열이다.nameToIndex: 친구 이름을 배열 인덱스에 매핑하기 위한 객체이다..

우선순위 큐 문제와 힙 문제는 응용력 또한 중요한 것 같다. 문제https://www.acmicpc.net/problem/13904 풀이접근 방식모든 과제를 점수 기준으로 내림차순 정렬한다.가장 늦은 날부터 1일까지 거꾸로 순회하면서, 해당 날짜에 할 수 있는 과제 중 점수가 가장 높은 것을 선택한다.이를 위해 해당 날짜에 가능한 과제를 저장할 배열이나 자료구조가 필요하다.일정을 관리하는 방식은 배열을 사용해도 충분하다.코드class MinHeap { constructor() { this.heap = []; } push(v) { this.heap.push(v); this.bubbleUp(); } bubbleUp() { let index = this.heap.length - ..

1. 힙이란?힙(Heap)은 완전 이진트리 형태로 구성된 자료구조이다.특징은 부모 노드가 자식 노드보다 항상 크거나(최대 힙), 작아야(최소 힙) 한다는 것!종류최소 힙(Min Heap): 부모 노드 ≤ 자식 노드 → 가장 작은 값이 루트에 위치최대 힙(Max Heap): 부모 노드 ≥ 자식 노드 → 가장 큰 값이 루트에 위치2. 언제 사용될까?힙은 우선순위가 중요한 상황에서 매우 유용해하다우선순위 큐 구현K번째 최솟값/최댓값 찾기다익스트라, A* 같은 그래프 알고리즘실시간 정렬된 데이터 관리최소힙같은 경우는 여러 문제(최단경로 같은 문제)에 많이 적용돼서 응용을 잘했었는데, 최대힙같은 경우는 상대적으로 사용 횟수가 적어서 그런지 예전 문제 풀이를 아쉽게 했던 기억이 있다. JavaScript에서는 직접..

그리디 알고리즘이 뭐야?매 선택에서 지금 가장 좋아 보이는 것만 고르는 방법예를 들어, 동전을 거슬러줄 때 가장 큰 단위부터 주는 방식! 언제 써야 할까?지역적 최적 선택이 전체 최적 결과로 이어지는 경우예외 상황(특별한 조건)이 없다면 거의 항상 빠르고 간단함근데! 모든 문제에 적용되지는 않는다.그래서 문제 풀기 전에 “그리디로 풀어도 되나?” 꼭 확인해야 한다.(문제 조건 잘 읽는 게 핵심!) 문제를 풀어보며 좀 더 자세히 이해해 보자. 문제https://www.acmicpc.net/problem/2839 문제 요약사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다.봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.최대한 적은 봉지를 들고 가려고 한다. 문제를 읽자마자 드는 생각:"그냥 큰 봉지부터..

이제 이전에 학습한 개념을 문제에 적용해 보며 이해해 볼 차례이다. 문제https://www.acmicpc.net/problem/2839 dp [n] = nkg을 만들기 위한 최소 봉지 수dp [i] = Math.min(dp [i - 3], dp [i - 5]) + 1→ 단, i - 3 또는 i - 5가 가능한 경우에만 과정 처음에는 그리디로 풀 수 있을 줄 알았다.단순하게 5로 나눠보고 안 되면 3으로 채우면 되지 않을까? 그러나 음수가 나오는 케이스에서 오류 발생.그때 '아, 이건 단순 반복이 아니라 누적 최솟값을 구하는 문제구나'라는 깨달음. 풀이const fs = require('fs');const filePath = process.platform === 'linux' ? '/dev/stdin'..

DP의 개념을 알아보면 다음과 같다.동적 계획법이란?"복잡한 문제를 작은 문제로 나누고, 그 결과를 저장해서 중복 계산을 피하는 알고리즘 설계 기법" 핵심은 이거다 문제를 잘게 쪼갠다.중복되는 계산은 한 번만 한다. DP는 재귀와 비슷한 개념이지만, 이미 계산한 결과를 메모해 두고 재사용하는 점에서 효율성 면에서 큰 차이가 있다. DP를 적용할 수 있는 조건DP는 아무 문제에나 적용되는 것이 아니다. 겹치는 부분 문제 (Overlapping Subproblems)큰 문제를 해결하는 과정에서 같은 작은 문제가 반복해서 나타나는 경우예시: 피보나치 수열function fib(n) { if (n 만약 fib(5)를 호출하면 호출 트리는 다음과 같다: fib(5) / ..

이번에 백준 여러 문제를 풀며 적용해 보았다.심화 문제까진 완벽히 응용할 정도는 아니지만, 기본과 어떨 때 구간 트리를 사용하면 좋을지를 생각하면서 풀어봤다. Segment Tree를 이용하면 좋을 때 특정 구간의 합, 최솟값, 최댓값을 구하는 연산 (O(log N))특정 인덱스의 값을 갱신하는 연산 (O(log N)) 이제 구간 트리의 기본 구조에 대해 알아보자. 구간트리 클래스 구조class SegmentTree { 생성자: constructor(arr)this.n = arr.length;this.tree = Array(this.n * 4).fill(0n);this.init(arr, 1, 0, this.n - 1);​this.n은 원본 배열의 길이이다.this.tree는 세그먼트 트리 배열이다. 최대..

이전에 배웠던 개념이지만 시간이 많이 지나기도 했고, 되짚어 볼 겸 다시 공부해 본 요소이다.(원래 애매하게 알때가 아예 모르는 것보다 더 안 좋은 것 같다... 하지만 다 애매하게 아는 게 함정...) 데이터를 효율적으로 관리하고 빠르게 쿼리하기 위해 사용하는 자료구조 중 하나가 세그먼트 트리이다.특히 구간의 합, 최솟값, 최댓값 등을 빠르게 계산해야 할 때 매우 유용하다.이번 글에서는 세그먼트 트리가 무엇인지, 언제 사용하는지, 그리고 JavaScript로 어떻게 구현하는지에 대해 살펴보자.세그먼트 트리란?세그먼트 트리는 배열의 특정 구간에 대한 합, 최솟값, 최댓값 등을 효율적으로 계산하기 위한 트리 기반 자료구조이다. 일반적으로 크기가 N인 배열에 대해 기본적인 쿼리(합, 최솟값, 최댓값)를 단순..

최단 경로 문제들을 풀며, 다양한 알고리즘이 있다는 걸 알았다. 다 비슷한 모양의 코드같지만, 개념들을 확고히 다지고 알고 넘어가면 놓을 것 같아 정리해본다.  다익스트라, 벨만-포드, 플로이드-워셜 알고리즘은 그래프에서 최단 경로를 구하는 알고리즘이다.세 가지 모두 그래프 문제를 해결할 때 유용하지만, 각각의 특성과 사용 조건이 다르다. 1. 다익스트라 알고리즘 (Dijkstra’s Algorithm)개념:다익스트라 알고리즘은 하나의 시작점에서 모든 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 가중치가 음수가 없는 그래프에서만 동작하며, 최단 경로를 탐색할 때 우선순위 큐(최소 힙)를 사용해 가장 짧은 경로를 점차적으로 확장한다.어떻게 동작하나?시작 노드에서 출발해, 그 노드까지의 거리를 0으로 ..