티스토리

GaeunLee blog

검색하기

블로그 홈

GaeunLee blog

0923ulee.tistory.com/m

컴퓨터과학전공 19학번 취준ing,,,,,

구독자: 4

방명록 방문하기

주요 글 목록

Monotone Stack, Monotone Queue (단조 스택, 단조 큐) 1. Monotone Stack (단조 스택)- 스택의 원소들을 단조롭게(오름차순 or 내림차순) 유지하는 기법이다. 그림으로 Monotone Stack 이해하기- 아래 그림과 같은 수열이 있을 때, 오름차순으로 단조 스택을 만드는 과정은 다음과 같다. 구현 방법수열을 순회하면서 다음을 수행한다.poptop의 원소를 확인해서 현재 값보다 크거나 같은 값들을 제거한다. (오름차순)push현재 값을 스택에 저장한다. 코드#include #include #include #include #include typedef long long ll;using namespace std;int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int .. 공감수 0 댓글수 1 2023. 11. 6.
포함 배제의 원리 (Inclusion-Exclusion Principle) 포함 배제의 원리 (Inclusion-Exclusion Principle) 포함 배제의 원리는 조합론에서 합집합의 크기를 구할 때 사용하는 공식이다. 그렇다면 합집합의 크기(원소의 개수)를 구하는 방법을 알아보자. 위 그림에서 합집합의 크기를 구하는 방법은 다음과 같다. $$n(A\cup B\cup C) = n(A) + n(B) + n(C) - \{n(A\cap B) + n(B\cap C) + n(C\cap A)\} + n(A\cap B\cap C)$$ 이를 일반화하면 다음과 같은 식이 성립한다. 전체집합의 모든 부분집합의 교집합의 원소를 더하거나 뺄 때, 부분집합의 수가 홀수라면 더하고, 짝수라면 뺀다. 문제 소수의 배수 (BOJ 17436) https://www.acmicpc.net/problem/1.. 공감수 0 댓글수 1 2023. 10. 23.
Network Flow - 네트워크 플로우 (최대 유량 알고리즘) # 최대 유량 알고리즘 (Maximum Flow Algorithm) 이란?그래프에서 두 정점 사이에 얼마나 많은 "유량(flow)"을 보낼 수 있는지 계산하는 알고리즘을 말한다. ex)다음과 같이 방향이 있는 그래프를 파이프 망이라고 생각해 보자.이때 간선은 파이프, 정점은 분기점이다.각 간선은 파이프에 용량만큼, 가중치를 가진다.그때 물이 흐른다면, 파이프 망을 통해 흐르는 물의 양의 최대는 무엇일까? 다음과 같은 파이프에서 A→D 까지 흐를 수 있는 물의 양 최대는?A. 정답은 6! B-C의 용량이 경로에서 가장 적은 용량(6)이기 때문에 병목현상으로 더 많은 물을 흘릴 수 없다. # 용어 유량(Flow)f(u, v)는 정점 u에서 v로의 간선에 실제로 흐르는 유량을 의미용량(Capacity)c(u.. 공감수 0 댓글수 0 2022. 8. 3.
Disjoint set, 분리 집합, Union-Find disjoint set(분리 집합)이란? 분리 집합: 서로 "중복되지 않는 부분 집합들"로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조 집합을 구현하는 방법은 다양하게 있지만, 보통 트리를 이용해서 구현한다.4 분리 집합의 구현 (tree) - 트리 하나가 각각 한 개의 집합을 의미한다. - 자식이 부모를 가리키는 방향으로 저장한다. - 루트 노드의 부모는 자기 자신을 가리킨다. 분리 집합의 3가지 연산 1. Make-set(x) : x를 유일한 원소로 하는 집합을 생성한다. 2. Find(x) : x가 속한 집합의 대표값(root node)을 반환한다. ➔ 서로 같은 집합인지 다른 집합인지 판단할 때에 쓴다. 3. Union(x, y) : x가 속한 집합과 y가 속한 집합을 병합한다. 3가.. 공감수 0 댓글수 0 2022. 3. 8.
탐색 알고리즘(DFS, BFS)과 활용 1. DFS, BFS의 기본 개념 깊이 우선 탐색(DFS) 탐색을 하고자 하는 그래프상에서, 깊이를 우선적으로 탐색하는 기법 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다. *참고 탐색에서는 중복된 상태를 막기 위하여 2개의 리스트를 사용한다. OPEN 리스트: 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트 CLOSED 리스트: 탐색이 끝난 상태들이 들어있는 리스트 closed 리스트: 방문 완료를 나타내는 배열(visited) 사용 open 리스트: 탐색할 대상을 stack에 넣어서 사용 (혹은, 재귀를 활용해서 구현) void dfs(int node) { visited[node] = true; cou.. 공감수 0 댓글수 0 2022. 3. 5.
냅색(Knapsack) 알고리즘 무게 제한이 걸려있는 가방에 가치를 최대로 하게끔 물건을 넣는 방법을 알아보자! 대표 문제: 12865 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 가치를 최대로 하는 문제이니, dp에 가치를 저장해서 해결한다. Value(i,w)란 i번째 물건까지, w무게만큼 골랐을 때 최대가치를 말한다고 가정한다. (단, i는 물건의 index, w는 현재 가방에 담겨있는 무.. 공감수 0 댓글수 0 2022. 3. 4.
모든 쌍 최단 경로 알고리즘(플로이드 와샬) 가중치 그래프의 두 정점 사이의 거리 중 가장 최단거리는 어떻게 찾을 수 있을까? 이 문제를 해결하기 위해서는 모든 시작점으로부터의 최단 경로 정보가 필요하다. 그렇다면 다익스트라 알고리즘을 v번 호출하면 풀 수 있다. https://0923ulee.tistory.com/entry/%EB%8B%A8%EC%9D%BC-%EC%8B%9C%EC%9E%91%EC%A0%90-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C 단일 시작점 최단 경로 알고리즘 (다익스트라, 벨만 포드) 가.. 공감수 0 댓글수 0 2022. 3. 3.
단일 시작점 최단 경로 알고리즘 (다익스트라, 벨만 포드) 가중치 그래프에서 시작 정점 s에서 다른 정점들 사이의 최단 경로를 구해보자! 일단, 시작 정점 s에서 어떤 정점 v사이의 거리를 배열(distance[v])로 나타내 보자. 그러면 distance[s] = 0이라고 표현할 수 있다. *최단 경로를 구하기 위한 완화 작업(Relax)이란?* 시작 정점 s에서 v로 가는 경로에서, 간선 u->v를 사용하는 것이 이득인지 판단하는 검사이다. 즉, 시작 정점 s에서 v로 가는 기존 경로와 시작 정점 s에서 정점 u를 지나 v로 가는 경로 중 더 짧은 거리를 선택한다는 의미이다. (더 짧아지는 경우 갱신한다.) distance[v] = min(distance[v], distance[u] + weight(u->v)) //u를 거치는 방법으로 갱신이 일어난 경우 ".. 공감수 1 댓글수 1 2022. 3. 2.
[BOJ 17626] Four Squares 백준 17626 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. 주어진 수와 같거나 작은 가장 큰 제곱수를 우선으로 그리디하게 풀면 틀린다. 더 작은 경우가 존재 ex) 11339 = 106^2 + 10^2 + 1^2 + 1^2 + 1^2 (5 : 오답) 11339 = 105^2 + 17^2 + 5^2 (3 : 정답) 2. dp를 이용해 min을 갱신하면서 찾는다. dp[n] = 합이 n이 되는 제곱수의 개수라고 하자.. 공감수 0 댓글수 0 2021. 10. 8.
[BOJ 20047] 동전 옮기기 백준 20047 www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 손가락으로 짚은 두 동전을 편의상 Fcoin이라고 하자. 1. 문자열 S(Fcoin을 제외), T의 인덱스를 증가시키면서 비교하고, 달라지는 경우에 T와 Fcoin을 비교했다. 그럴 경우 반례가 생긴다. -> 문자열 S(Fcoin을 제외)에서 비교할 문자와 와 Fcoin이 같은 경우 어떤 경우로 체크해줘야 하는지 고려하지 않았다. 3 xxo xox 0 2 ans : .. 공감수 1 댓글수 0 2021. 10. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.