기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/이론

위상정렬 방향성을 가진 비순환 그래프에서만 사용이 가능 특정한 순서로 실행이 되어야하는 상황에 사용이 적합 위상정렬은 위에서 간단하게 설명한 것 처럼 특정한 순서로 실행이 되어야하는 상황에서 사용을 할때 사용을 하게 됩니다. 게임에서 예를 들어 보겠습니다. 요즘 유명한 게임이죠 리그오브 레전드라는 게임에서 피바라기 라는 아이템을 구매하기 위해 필요한 아이템 목록입니다. BF 대검 + 롱소드 + 흡혈의 낫을 그래프로 나타내면 다음과 같이 나타낼 수 있게 됩니다. B.F 대검과 롱소드 그리고 흡혈의 낫은 피바라기를 가르키고 있고 롱소드는 흡혈의 낫을 가리키고 있습니다. 그 이유는 각각의 아이템들은 피바라기의 선행조건이 되기 때문입니다. 그리고 피바라기를 구매후에는 다시 각각의 아이템으로 바꿀 수 없게 됩니다..

2022. 1. 3.

알고리즘/이론

BFS (Breath First Search) 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다. 너비 우선 탐색으로 모든 Branch의 같은 깊이의 노드들을 번갈아 가며 탐색을 하게 됩니다. FIFO구조인 큐로 구현 가능합니다. 장점 장점 단순검색 속도가 DFS에 비해 빠른편입니다. 깊이에 관계없이 최단 경로를 찾을 수 있습니다. 단점 다음에 탐색할 노드들을 모두 큐에 담아 두기 위해서는 자원이 많이 필요합니다. 과정 ※다음과 같은 그래프의 정점 1에서 모든 노드를 탐색 스택을 이용한 BFS를 하는 과정이고, 한번 방문한 노드는 방문처리가 되어 다시 방문 할 수 없다고 가정합니다. 아래쪽의 큐의 변화와 함께 보시면 이해가 ..

2021. 12. 30.

알고리즘/이론

DFS(Depth First Search) 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다. 깊이 우선탐색으로 한 정점에서 탐색을 시작할때 하나의 Branch를 완전히 탐색 한 후 다음 Branch를 탐색하게 됩니다. 스택과 재귀로 구현이 가능합니다. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적습니다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있습니다. 얻어진 해가 최단 경로가 된다는 보장..

2021. 12. 30.

알고리즘/백준

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 백준 온라인저지 16234번 문제입니다. BFS을 이용해서 풀었습니다. #include #include #include #include using namespace std; int arr[101][101]; bool visited[101][101]; int N, L, R; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; stack stk;..

2021. 12. 24.

알고리즘/백준

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 온라인저지 14502번 문제입니다. 브루트포스와 BFS을 이용해서 풀었습니다. #include #include #include using namespace std; enum { None, Wall, Virus }; int arr[8][8]; int temp[8][8]; int n, m; int sol; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; void ..

2021. 10. 3.

알고리즘/백준

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백준 1182번 문제입니다. DFS와 재귀, 백트래킹을 이용해서 문제를 풀었습니다. #include #define MAX 1000000 using namespace std; int n,s,sum,cnt; int arr[MAX]; void Input() { cin >> n >> s; for (int i = 0; i > arr[i]; ..

2021. 10. 3.

알고리즘/Codility

요약 A배열의 연속된 정수 집합을 slice라고 할때 가장 작은 평균을 갖는 slice의 시작위치를 반환 아이디어 수학적 지식을 요구하는 문제 1. a (a+b+c)/3을 만족한다. 5. 원소가 2개 또는 3개인 케이스만 확인을 한다. 코드 int solution(vector &A) { // write your code in C++14 (g++ 6.2.0) double minAvg = (A[0] + A[1]) / 2.0; double Avg = 0; int sol = 0; for (int i = 2; i < A.size(); i++) { Avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0..

2021. 8. 24.