손가든 개발일지

오늘은 컴퓨터 시스템과 관련된 CS 정리를 퀴즈 문제와 같이 정리하겠다. 그전에 DP의 행렬 체인 알고리즘을 공부하고 해당 문제를 푸는 과정을 정리하겠다. DP : 행렬 체인 알고리즘 행렬 체인의 연산은 몇번째의 행렬을 먼저 계산하는가에 따라 연산의 횟수가 달라진다. 따라서 주어진 행렬의 체인을 최소로 연산하는 횟수를 구하는 알고리즘을 공부해보자. `Introduction to Algorithm` 책에 해당 로직에 대한 설명이 나와있다. 매우 이해하기 힘들지만, 간단히 정리해 보겠다. 행렬을 쭉 나열하고 그 행렬의 열이 체인형태로 (NxM , MxP) 나열되어 있어서 곱을 순서대로 할 수 있다. Ai = pi-1 x pi 의 차원을 가진다. (이부분이 어려울 수 있는데, A의 i번째가 3x6 매트릭스라면..

BaekJun - #1946 : 신입사원 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 오늘은 신입 사원을 풀었다. 문제 이해가 조금 어려운데 풀어서 얘기해보면 실기, 필기 두개의 시험을 등수로 매기는데, 특정 A 라는 사람이 어느 누군가보다 실기도, 필기도 등수가 낮다면 그사람은 탈락된다. 문제를 이해하는데 시간이 좀 걸리긴 하지만, 문제가 이해됬다고 하면 이제 어떻게 풀어야할지 고민을 해보자..

드디어 어제 마지막으로 2주차 문제를 모두 풀었다 ! 1주차 남겨둔 두문제도 풀고 이번주 여유롭게 넘어가보자. `시간 많다고 농땡이 피우지 말고 운영체제 책 읽기` 일단 오늘은 백준 문제 푸느라 미뤄둔 컴퓨터 시스템 책을 읽으며 시스템에 대해 공부 좀 해보려고 한다. 그전에 알고리즘 공부도 개인적으로 조금 한 것을 정리해보겠다. 누적 합(Prefix Sum) 만약 a1 ~an 까지의 수열을 모두 더하면 시간 복잡도는 O(n)이다. 하지만 특정 구간 q개에 대하여 구간 합을 물어본다면? -> O(qn) 이 시간 복잡도를 O(n)로 처리할 수 있게 하기 위해 누적된 합을 저장하는 누적 합 알고리즘을 수행한다. 특정 구간 i~j 사이의 수열 합을 구할 때, 누적합 P 수열에서는 pj - p(i-1) 만 하면 ..

위상정렬이 정말 쉽지가 않은 알고리즘인 것은 확실하다.. 진입 / 진출 차수를 checking하면서 -1하며 queue 혹은 우선순위 큐인 힙에 저장하는 방식을 주로 활용하는 것 같다. 그보다 더 어려운 것은 위상정렬은 문제를 보고 위상정렬 문제인지 파악하기도 쉽지 않고, 파악하더라도 똑같은 방식이 아닌 유동적인 문제 풀이가 필요하므로 매우 고수준의 이해를 요한다. 어려운 문제를 리뷰하며 조금 더 확실하게 이해해 보자 BaekJun - # 1432 : 그래프 수정 (위상정렬) 방향 그래프의 연결성분을 행렬로 나타낸 행렬 그래프를 제시 한 뒤 더 높은 수의 정점이 더 높은 위상을 가지도록 변경하고 그 변경점을 출력하도록 하는 문제였다. 장장 5시간을 고민하며 코드를 구현해 나갔지만, 내 머리로는 도저히 멍..