결국 유용함

문제 출처: https://www.acmicpc.net/problem/11571문제 간단한 요약분자 n과 분모 d가 주어졌을 때 해당 분수 $\frac{n}{d}$를 소수로 바꾸는 문제이다. 이때 소수점 아래에 반복되는 값이 생기면 ()로 묶어서 표시한다.1 / 3 → 0.(3) 1 / 2 → 0.5(0)위 처럼 나누어 떨어지더라도 (0)을 묶어주어야 한다.문제 접근순환소수라고 언제 판별할 수 있게 되는지 찾는 게 어려웠던 문제.n을 d로 나누고 나머지를 가져가면서 n을 다시 10을 곱해주고 d로 나누고 n을 다시 d로 나눈 나머지로 가져면서 10을 곱하고 d로 나누고를 반복하는 일반적인 나눗셈을 진행하는 식으로 소수를 표현할 수 있는데 순환소수는 이전에 나누게 되었던 n을 다시 나누게 되는 순간 순환소..

문제 출처: https://www.acmicpc.net/problem/2294문제 간단한 요약동전 1 이랑 비슷하게 동전의 종류가 n개 있고(중복 가능) k원을 딱 맞춰야 하는데 동전 1과 다른 점은 해당 문제는 최대한 적은 동전을 사용해서 k원을 딱 맞춰야 한다.각 종류의 동전은 개수에 상관없이 사용할 수 있다고 할 때 k원을 맞추기 위해서 사용해야하는 최소 동전은 몇개인지 구해야 한다.문제 접근일단 동전 1과 마찬가지로 dp문제라는 것을 쉽게 알 수 있다. 왜냐하면 동전의 종류가 n개(100이하)개 존재하기 때문에 k원을 맞추는 모든 조합을 찾을때 전수 조사를 사용하면 연산량이 너무 많아서 시간초과가 난다.따라서 dp를 사용해서 이전의 값을 사용하는 방식을 택해야 한다. DP(Dynamic Progr..

문제 출처: https://www.acmicpc.net/problem/1865문제 간단한 요약n개의 월드가 있고 m개의 각 월드를 연결하는 양방향 도로가 있다. 각 도로는 t만큼의 시간이 걸린다. 추가적으로 w개의 단방향 웜홀이 있는데 해당 웜홀은 가중치만큼의 시간을 역행하게 된다.임의의 월드에서 출발해서 다시 출발지로 돌아왔을 때 출발 했을 때 보다 시간이 과거인 경우가 존재하면 YES를 출력하고 아니면 NO를 출력해야 한다.문제 접근일반 도로를 양의 가중치를 갖는 간선으로 보고 웜홀을 음의 가중치를 갖는 간선으로 보면 결국 가중치가 있는 방향 그래프에서 음의 사이클이 존재하는지 찾는 문제라는 것을 알 수 있었다.따라서 해당 문제는 음의 사이클이 존재하는지 확인하는 벨만-포드 알고리즘을 사용하는 문제이..

문제 출처: https://www.acmicpc.net/problem/10986문제 간단한 요약수 N개 $A_1,\,A_2,\,...,\,A_N$이 주어진다. 이때, $A_i+A_{i+1}+...+A_j$ (i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.첫째 줄에 N과 M이 주어진다.$(1\leq N\leq 10^6,\,2\leq M\leq10^3)$둘째 줄에 N개의 수 $A_1,\,A_2,\,...,\,A_N$이 주어진다. $(0\leq A_i\leq10^9)$첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.문제 접근일단 N개에 대해서 누적 합 배열 sum[]을 만들고 모든 (i, j) 쌍에 대해서 M으로 나누어 떨어지는지 확인하는 거..

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?벨만-포드 알고리즘(Bellman-Ford Algorithm)은 가중치가 있는 방향 그래프에서 단일 출발점에서 모든 정점까지의 최단 경로를 계산하는 알고리즘입니다. 이 알고리즘은 다익스트라(Dijkstra) 알고리즘보다 느리지만, 더 범용적이라는 장점이 있습니다. 특히 음의 가중치가 포함된 그래프에서도 동작 가능 하다는 점에서 활용도가 높습니다.역사1955년 Alfonso Shimbel 이 처음 제안함.1956년과 1958년에 각각 Lester Ford Jr. 와 Richard Bellman 이 논문을 발표하며 정식으로 알려짐.1959년 Edward F. Moore 가 변형된 알고리즘을 발표하면서 Bellman-Ford-Moore 알고리즘..

문제 출처: https://www.acmicpc.net/problem/1005문제 간단한 요약1번부터 n번까지의 건물이 있는데 특정 건물을 짓기 위해서는 먼저 지어야 하는 건물이 있다.각 건물이 지어지는데 걸리는 시간이 주어진다.최종 적으로 w번 건물을 지어야 할 때까지 걸리는 시간을 구하라문제 접근특정 건물을 짓기 위해서 다른 건물을 먼저 지어야 한다는 부분을 보고 바로 위상 정렬이 떠올랐다. 위상 정렬(Topological Sort)위상 정렬(Topological Sort)이란?위상 정렬(Topological Sort)은 방향 비순환 그래프(Directed Acyclic Graph, DAG)에서 정점들을 방향을 거스르지 않도록 순서대로 정렬하는 방법입니다. 작업 간에 순서가 정해eventually-u..

위상 정렬(Topological Sort)이란?위상 정렬(Topological Sort)은 방향 비순환 그래프(Directed Acyclic Graph, DAG)에서 정점들을 방향을 거스르지 않도록 순서대로 정렬하는 방법입니다. 작업 간에 순서가 정해져 있는 경우에 그 순서를 정해주는 방법이라고 생각할 수 있습니다.대표적으로 대학 선수과목(prerequisite) 구조가 있습니다.위와 같이 선이수를 해야 들을 수 있는 과목이 섞여있는 커리큘럼이 있다고 하자. 이때 전기기기를 듣기 위해서는 전자기학2와 회로이론2를 수강해야 한다. 또한 각각의 2과목을 듣기 위해서는 1과목을 들어야 하고 가장 먼저 미분적분학을 들어합니다.따라서 미분적분학 → 전자기학1 → 회로이론1 → 전자기학2 → 회로이론2 → 전기기기..

DFS(Depth First Search)로 위상 정렬이 가능한 이유위상 정렬은 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 선행 관계를 지키면서 순서대로 정렬하는 문제입니다.이때 DFS의 기본 동작 방식이 위상 정렬과 자연스럽게 맞아떨어지게 되는 데 그 이유는 다음과 같습니다.DFS의 후위 순회(Post-order Traversal)가 위상 정렬의 순서와 동일하다.DFS는 다음과 같은 방식으로 진행됩니다.아직 방문하지 않은 노드를 선택해서 탐색을 진행한다.해당 노드에서 갈 수 있는 모든 노드를 재귀적으로 탐색한다.더 이상 탐색할 곳이 없다면 현재 노드를 스택에 추가(=처리 완료) 한다.이 방식은 위상 정렬과 동일한 원리로 동작하게 됩니다.위상 정렬에서는 "선행..

Kahn’s Algorithm이란?Kahn's algorithm은 위상 정렬(Topological Sorting)을 수행하는 대표적인 방법 중 하나로, 진입 차수(In-degree) 를 활용하여 방향 비순환 그래프(DAG, Directed Acyclic Graph)의 위상 정렬을 구하는 방식입니다.작동 방식모든 정점의 진입 차수(in-degree)를 계산진입 차수(in-degree): 해당 정점으로 들어오는 간선의 개수진입 차수(in-degree)가 0인 정점을 큐에 삽입큐에서 정점을 하나씩 꺼내면서 연결된 간선 제거연결된 정점들의 진입 차수를 감소시키고,감소 후 진입 차수가 0이 되면 큐에 삽입모든 정점을 방문할 때까지 반복✅ 시간 복잡도: $O(V + E)$ → 모든 간선과 정점을 한 번씩 처리진행 ..

프로토타이핑 모형(Prototyping Model)이란?프로토타이핑 모형(Prototyping Model)은 사용자의 요구를 보다 명확하게 파악하기 위해 시제품(Prototype)을 먼저 개발한 후, 이를 기반으로 개선을 반복하는 소프트웨어 개발 모델입니다.사용자와 개발자가 초기에 프로토타입을 통해 피드백을 주고받으며 시스템을 발전시킬 수 있기 때문에, 요구사항이 불확실하거나 자주 변경될 가능성이 있는 프로젝트에 적합합니다.특징프로토타이핑 모형은 아래와 같은 여러 성질 및 특징을 갖고 있습니다.최종 결과물이 만들어지기 전에 사용자가 최종 결과물의 일부 또는 모형을 볼 수 있다.개발자는 시제품을 빨리 완성하기 위해 효율성과 무관한 알고리즘을 사용해도 되며, 프로토타입의 내부적 구조는 크게 상관하지 않아도 ..