더블링(doubling, binary lifting, 희소배열,sparse table)에 대해 배우기

https://deepdata.tistory.com/972 희소 배열(sparse table) 자료 구조 배우기https://cp-algorithms.com/data_structures/sparse-table.html Sparse Table - Algorithms for Competitive ProgrammingSparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its trdeepdata.tistory.com 희소 배열(sparse table)로도 알려진 더블링(doubling) 기법은 어떤 횟수 K를 2의 거듭제..

  • format_list_bulleted 알고리즘/희소배열(더블링)
  • · 2026. 1. 1.
  • textsms

순열 사이클 분할에 대해 알아보기

1. 순열 사이클 1부터 n까지 정수 n개로 이루어진 배열을 순열이라고 부른다. 예를 들어 [3,2,4,5,1]은 길이가 5인 순열이다. 배열의 인덱스를 '현재 위치', 배열의 값을 '다음에 갈 곳'으로 생각하고 인덱스 > 값으로 향하는 방향 그래프를 만들 수 있다. 즉, [3,2,4,5,1]은 1 > 3, 2 > 2, 3 > 4, 4 > 5, 5 > 1로 간선을 이으면 다음과 같이 방향 그래프를 만들 수 있다. 위 그래프는 2개의 사이클 1 > 3 > 4 > 5, 2 > 2가 있다. 이 사이클들을 순열 사이클이라고 부른다. 전체 순열을 여러개의 독립적인 순열 사이클로 분할하는 것을 '순열 사이클 분할'이라고 부른다. 길이 n인 순열에는 반드시 사이클이 생긴다. 왜냐하면 먼저 1부터 n까지 1개씩만 ..

  • format_list_bulleted 알고리즘/순열 사이클 분할
  • · 2025. 12. 19.
  • textsms

O(1)에 스택의 최솟값을 찾는 min stack 기법?

https://www.acmicpc.net/problem/8858 은행원이 현금 보유액 S를 가지고 있다. 고객이 입금을 하러 온다면, 입금 금액을 기록하고 고객이 가져온 현금을 새 봉투에 넣은 다음, 이전 입금 봉투 위에 쌓는다. 입금 봉투는 이처럼 스택 구조로 쌓이게 된다. 고객이 X원을 출금하러 온다면, 봉투 스택이 비어있는 경우 전액을 현금 보유액 S에서 지급 봉투에 든 금액들 중 가장 작은 금액보다 X가 작다면, 전액을 현금 보유액 S에서 지급 그렇지 않다면, 봉투 스택의 맨 위에서부터 하나씩 꺼낸 다음, 필요한 금액을 충당 마지막에 꺼낸 봉투에서 일부 금액만 사용하면, 남은 돈은 현금 보유액 S로 넣는다. 만약 모든 봉투를 다 사용했는데 X를 다 지급하지 못하면 남은 금액은 현금 보유액 S에..

  • format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
  • · 2025. 11. 27.
  • textsms
MYSQL은 FULL OUTER JOIN이 없다고?

MYSQL은 FULL OUTER JOIN이 없다고?

SQL 코딩테스트 보는데 당황했던 것이 LEFT OUTER JOIN, RIGHT OUTER JOIN은 되는데 FULL OUTER JOIN이 안되더라고 대신 FULL OUTER JOIN은 LEFT OUTER JOIN과 RIGHT OUTER JOIN의 합집합이므로, UNION을 이용해 다음과 같이 구현 가능하다. SELECT *FROM table1LEFT JOIN table2 ON table1.id = table2.idUNIONSELECT *FROM table1RIGHT JOIN table2 ON table1.id = table2.id; 이것도 시도하긴 했는데 에러나더라고 왜 에러나나 봤더니 SELECT *FROM table1LEFT JOIN table2 ON table1.id = table2.id; #..

  • format_list_bulleted 프로그래밍/SQL
  • · 2025. 6. 13.
  • textsms
MYSQL 그룹별 최댓값 구할때 주의해야할 점

MYSQL 그룹별 최댓값 구할때 주의해야할 점

코딩테스트 연습 - 즐겨찾기가 가장 많은 식당 정보 출력하기 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 음식 종류별로 즐겨찾기 수가 가장 많은 음식점을 조회하는 간단한 문제 -- 코드를 입력하세요SELECT food_type, rest_id, rest_name, max(favorites) as favorites from rest_infogroup by food_typeorder by food_type desc; 단순히 group by하고 max(favorites)하면 될줄 알았는데 그냥 틀리더라고 group by하는 순간 임의의 한 행으로 묶어버리더라고? select * from..

  • format_list_bulleted 프로그래밍/SQL
  • · 2025. 6. 12.
  • textsms
그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

1. 문제 정확히 하나의 사이클을 포함하는 무방향 연결 그래프(connected undirected graph)가 주어진다. 각 노드 번호가 0부터 n-1까지 n개의 노드를 가진다. 노드 a와 b 사이 거리가 a에서 b로 가기 위해 필요한 최소 간선의 수 노드 i = 0,1,2,..,n-1에서 이 그래프에 존재하는 사이클에 있는 임의의 노드까지의 최소 거리를 구한다면? 당연히 사이클에 포함된 노드는 사이클 까지의 거리가 0이다.   위 그래프는 1,2,3,4가 사이클을 이룬다. 1,2,3,4는 각각 사이클까지 거리가 0이고, 0번 노드는 사이클 까지 거리가 1 5번 노드는 사이클 까지 거리가 1, 6번 노드는 사이클 까지 거리가 2이다.  2. 풀이 사이클에 포함된 노드는  위상정렬에 포함되지 않는다는 ..

  • format_list_bulleted 알고리즘/위상정렬
  • · 2024. 11. 13.
  • textsms