| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 |
- 알고리즘
- MAC
- es6
- javascript
- 알고리즘 문제
- Algorithm
- web
- c++
- django ORM
- Baekjoon
- CSS
- Django
- react
- AWS
- java
- 장고
- API
- 알고리즘 풀이
- form
- 파이썬 알고리즘
- DRF
- 백준
- 알고리즘 연습
- 파이썬
- django widget
- js
- Git
- HTML
- django rest framework
- PYTHON
- Today
- Total
목록알고리즘 (87)
수학과의 좌충우돌 프로그래밍
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net DFS 와 BFS 를 구현하는 기본적인 문제입니다. #include #include using namespace std; int arr1[1002][1002]; // 그래프를 2차원 배열로 표현 int arr2[1002][1002]; // 그래프를 2차원 배열로 표현 int visite..
세그먼트 트리(Segment Tree)란? 배열에 부분 합을 구할 때 사용하는 개념입니다. 이 때 문제는 배열의 값이 지속적으로 바뀔 수 있기 때문에 매 순간 배열의 부분 길이 만큼, 즉 O(N) 만큼의 시간이 걸리기 때문에 이를 트리로 구현하여 O(logN) 의 시간으로 해결하는 방법입니다. 배열을 세그먼트 트리로 세그먼트 트리 를 사용하기 위해서는 주어진 배열을 이진 트리 구조로 만들어야 합니다. 이 때 트리를 구현하는 알고리즘은 다음과 같습니다. 부모노드의 값은 양 쪽 자식 노드 값의 합 배열의 요소들은 리프 노드에 위치 위 알고리즘을 통해 N = 10 일 때의 세그먼트 트리를 그리면 다음과 같습니다. 이 때 기존 데이터의 배열의 크기를 통해서 트리 배열의 최대 크기를 알 수 있습니다. 기존 데이터..
비트 마스크란? 비트마스크란 컴퓨터의 언어인 이진수를 활용하여 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법입니다. 기본적인 비트 연산 기본적인 비트연산들을 표로 정리해보았습니다. A B ~A A&B A|B A^B 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 0 not 연산을 할 경우 주의해야할 점이 자료형에 따라서 결과가 달라집니다. A = 83 = 1010011(2) 에 대하여 8비트 자료형의 경우 ~A = 10101100(2) 32비트 자료형인 경우 ~A = 11111111 11111111 11111111 10101100(2) 쉬프트 연산 쉬프트 연산은 다음과 같이 부등호 2개로 표현하며 A
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net Union-Find 알고리즘을 사용하여 문제를 해결하였습니다. #include using namespace std; int parent[100]; int Find(int a){ if (a==parent[a]) return a; int b = Find(parent[a]); parent[a] = b;..
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 유니온 파인드 알고리즘으로 문제를 해결하였습니다. 유니온 파인드를 구현하는 기본적인 문제입니다. Union-Find 알고리즘이란? [..
유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다. Find 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화 해줍니다. parent[i] = i 인 경우, 루트노드 임을 의미합니다. int parent[MAX_SIZE]; for (int i=0; i
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 이분탐색 을 활용하여 해결하였습니다. 가장 인접한 두 공유기 사이의 최대 거리 를 구하는 문제입니다. 이 거리를 answer 라고 하면 answer 값을 구해주기 위해서 이분탐색으로 찾아갑니다. 최소값은 1 이므로 left 는 1로 초기화하고, 최대값은 양 쪽 끝의 공유기 거리 이므로 right 는 이 값으로 초기화 해..
https://www.acmicpc.net/problem/2805 불러오는 중입니다... 이분탐색 을 활용하여 문제를 해결하였습니다. 높이 mid를 이분탐색으로 정한 후, 나무의 길이가 높이보다 크다면 잘라서 myTree 에 더해주었습니다. 이 값이 원하는 나무의 길이 M 보다 크다면 left 를 이동시켜 높이를 높여주고, M 보다 작다면 right 를 이동시켜 높이를 낮춰주며 가능한 최대 높이를 찾았습니다. #include using namespace std; int tree[1000000]; int main(){ int N,M; cin >> N >> M; int maxTree = 0; for (int i=0;i> tree[i]; maxTree = max(maxTree, tree[i]); } long ..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분탐색 을 이용하여 문제를 해결하였습니다. 이분탐색을 사용하지 않을 시 이분탐색을 사용하지 않은 오답부터 확인해보겠습니다. 자를 랜선의 길이가 1 일 때 부터 보유하고 있는 랜선 중 최대 길이가 될 때 까지 하나씩 확인하여 개수가..
Divide and Conquer Divide and Conquer 는 분할정복 알고리즘이라고도 하며, 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 문제를 해결하는 알고리즘을 말합니다. 경우에 따라서는 푼 다음에 다시 부분 문제들을 합쳐서 정답을 구할 때도 있으며 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있습니다. Divide and Conquer VS danamic programming 분할정복 알고리즘과 다이나믹 프로그래밍은 문제를 해결하는 핵심적인 전략이 동일합니다. 바로 문제를 작은 부분 문제로 나눠서 해결한다는 점입니다. 하지만 둘은 결정적인 차이가 존재하는데 바로 memorization 입니다. 다이나믹 프로그래밍은 작은 부..