Algorithm/알고리즘 문제 해결 전략

동적 계획법 메모이제이션 패턴 (C++)

동적 계획법.. 다이나믹 프로그래밍과 같은 말이다. 동적 계획법은 개념 자체는 쉬워서 알고리즘의 기본 난이도는 낮은 편이다. 하지만 메모이제이션을 몸에 익히고 문제를 보고 동적계획법을 떠올리며 어떤 정보를 메모이제이션할지 바로 찾아내는 내공을 가지려면 엄청난 노력이 필요하다고 생각한다. 다른 알고리즘과는 비교가 안될정도로 많이. 이 책에는 약 25개 정도의 큼직한 알고리즘 파트가 1000페이지 조금 넘게 기술되어있다. 그 중에서 동적계획법은 160페이지 가량 되는데 비중이 정말 크다고 볼 수 있다. 쉬우면 너무 쉽지만 어려우면 말이 안나올정도로 어려운 동적계획법의 가장 기본이 되는 탑다운 메모이제이션 패턴을 알아보자. 패턴 코드 // 전부 -1로 초기화 int cache[2500][2500]; int F..

근거리 네트워크 (LAN)

algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 최소 스패닝 트리 문제 설명 더보기 N개의 정점의 좌표가 주어지고 가중치 없이 연결할 수 있는 정점의 번호가 주어진다. 양방향 간선이지만 u에서 v로 가는 간선 하나만 저장해주면 된다. (u < v) 2중 for문을 통해서 모든 정점끼리 연결될 수 있는 가중치가 포함된 간선을 구해준다. 크루스칼 알고리즘을 적용하기 전에 주어지는 정점들을 Union해버리면 가중치 없이 정점을 미리 연결해줄 수 있다. 그리고 나머지 정점들을 크루스칼 알고리..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, www.algospot.com 플로이드-와샬 문제 설명 더보기 플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다. 이 과정에서 경유하는 정점을 1번부..

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다. 하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다. 타잔 알고리즘 1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자. 타잔 알고리즘에서는 방문할 때마다 임의의 sta..

단어 제한 끝말잇기 (WORDCHAIN)

algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 www.algospot.com DFS, 오일러 서킷, 오일러 트레일 1. 문제 해결 아이디어 끝말잇기에 사용되는 단어들이 주어진다. 주어진 단어 모두를 사용해서 끝말잇기를 만들면 된다. -> 오일러 회로임을 알 수 있다. 단어를 모두 사용해서 다시 시작점으로 돌아올 수도 있고, 시작점이 아닌 지점에서 끝날 수도 있다. 다시 시작점으로 돌아오는 경우는 오일러 서킷이라고 할 수 있다. 모든 간선을 한 번씩 통과하지만 시작점이 아닌 다른 정점에서 끝나는 경로를 오일러 트레일 이라..