손가든 개발일지

3주차 마지막 날이 다가왔다. 남은 문제를 오늘 전부 풀겠다. (도전빼고.) BaekJun - #11053 : 가장 긴 증가하는 부분 수열 (DP) 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제를 처음 접했을 때, DP적 접근이 아니라 문제를 해결하는 방식을 생각하다가 뒤에서부터 result에 append하고 만약에 다음에 append할 수의 값이..

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

오늘의 내용은 어제의 동적 프로그래밍 공부의 연장선인 Knapsack Problem에 대해 알아보고, 컴퓨터 시스템 정리를 간단히만 다뤄보겠다. Knapsack Problem 배낭 문제라고도 하는 kapsack 문제는 정해진 무게 한도가 있는 배낭에다 물건을 담는데, 가치가 가장 높게 담는 경우를 찾는 문제이다. 이는 모든 경우를 다 셀 경우 특정 물건을 담는다 vs 안담는다로 하여 2의 n(물건의 수)승의 탐색이 걸린다. 따라서 이는 효율적인 탐색법이 필요한데 접근법은 다음과 같다. 1. 만약 물건의 무게가 배낭의 한도보다 크다면 continue, 2. 한도보다 작다면 2중 배열(dp)에 세로줄은 담은 물건의 수(i), 가로줄은 배낭의 한도무게(w)로 설정하여 선언한 뒤 그 배열안에 최대의 가치를 저장..

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

오늘은 쪽지 시험이 있는 날이다. 쪽지 시험에 관한 주요한 내용들과 오늘 공부한 내용을 정리하겠다. 강한 결합 요소 ( 강연결성분 : Strongly Connected Component ) 강한 결합 요소란? 그래프의 특정 부분 집합 내의 모든 정점 V 이 집합 내 다른 정점 U로 도달할 수 있으며 반대로 U도 V로 도달할 수 있는 집합 또한 기본적으로 싸이클이 발생하는 경우 무조건 SCC에 해당한다는 특징이 있음. 쪽지 시험 대비 팀원 코어 타임 서로 2주차 내 어떤 키워드가 중요할 지 생각해보고 서로 문제를 출제했다. 화이트보드에 문제를 풀어보며 토론했는데, 다익스트라에 대해 조금 이해가 부족하다고 생각되서 다시 자세히 정리해보자. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 다이나믹 ..

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

오늘은 BFS 문제 풀이를 팀원과 서로 공유하고 DFS 문제 풀이를 시작했다. BaekJun - # 21606 : 아침산책 (DFS) 완전히 하나로 연결된 N개의 노드의 서로 다른 경로의 수를 세는 문제인데, 노드가 실내거나 실외이다. 경로는 반드시 실내에서 시작해서 서로 다른 실내로 끝나며 1 -> 3 과 3 -> 1은 다른 경로로 보는 것이다. 이 문제의 특이한 점은 서브 테스크로 문제 배점을 나눈다는 점이었다. 주목할 점은 N의 최대 제한이 10의 5승이라는 점. (대충 NlogN 보다 높은 시간 복잡도를 가진다면 앙 시간초과 띠~ 라는 뜻) 나는 2번과 5번 테스크에서 시간 초과가 발생했다. 시간 초과가 발생한 로직은 다음과 같다. 코드를 보기 전 말로 설명한다면, 1. 실내인 노드를 하나씩 DF..