Algorithm

1. 문제 2. 아이디어 0. 이 문제의 답은(전체 학생수 - 잃어버린 학생수)로 구하자. -> lost 배열의 원소를 제거하는 방식으로 풀어가자. 1. 도난당한애 == 여벌있는애 일 경우부터 삭제하고 시작하자. ∵ 어차피 여벌있으면서 도난당한애는 다른애한테 빌려주지 못한다. 2. 앞번호 먼저 검사 뒷번호 후검사를 하자. // Mistake 3. 주의사항 for(index in lostList.indices) { // 잃어버린 애, 가져온애가 같으면 양쪽 리스트에서 둘다 삭제 if (reserveList.remove(lostList[index])) lostList.removeAt(index) } for loop에서 index를 활용하여 '정순'으로 순환하면서 컬렉션의 원소를 제거하는 경우 원소가 제거된 ..

1. 용도 Graph에서 All pairs Shortest Path 구하기 == 그래프 내의 모든 노드쌍에 대한 최단거리 구하기. Input Directed-weighted Graph Output All pairs Shortest Path (ex. Adjacency Matrix) 2. IDEA 점화식으로 부터 이 알고리즘이 'Dynamic Programming' 류의 알고리즘임을 알 수 있다. 3. Pseudo Code 4. Time Complexity Pseudo Code에서 알 수 있듯이 최초의 Adjacency Matrix를 형성하는 2중 for Loop은 O(n^2) Shortest Path를 갱신하는 3중 for Loop 은 O(n^3) ∴ O(n^3) 참고 자료 https://ko.wikipe..

1. 문제 https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 www.acmicpc.net 2. 설계도 3. Flowchart 이 순서도는 정답은 도출하나 시간복잡도에서 털렸다. 4. 핵심 전략 수식 세우기 A + B..

1. 필요한 개념 Dynamic Programming https://m-falcon.tistory.com/118 피보나치 수열 2 (Memoization, Dynamic Programming ver) 이전 포스팅! https://m-falcon.tistory.com/84 피보나치 수열 0. 문제 코드업 1855 피보나치 수열 https://codeup.kr/problem.php?id=1855 [기초-재귀함수] 재귀로 n번째 피보나치.. m-falcon.tistory.com 2. 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 3. 핵심..

0. 사전 지식 Undirected Graph DFS Traversal makes Forest// Undirected Graph는 시작점이 어디든 Tree 개수 일치 Directed Graph는 시작점 따라 Tree 개수가 다름. 1. 정의 Strongly Connected => 모든 쌍에서 길이 다 있음. 2. 특성 가질 수 있는 Edge 3종류 Cross, Back, Forward Edge Leaf Node에서 좌-> 우 Cross Edge가 불가능 한 이유는 DFS Traversal알고리즘 상 더이상 인접 노드가 없을 때 까지 깊이 들어가는데 좌->우 Cross Edge 존재 시 우측 노드를 이미 추가했었어야 한다. ∴ DFS Traversal Algorithm에 모순. 3. 알고리즘 1. DFS ..

1. 개념 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환..