손가든 개발일지

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

현재 컴퓨터 시스템을 공부하고 있는 내용은 이해할 내용이기보다는 어셈블리어의 인스트럭션 기호의 정의와 해석적인 파트를 읽고 있어서, 따로 정리하지는 않겠다. 대신 DP 알고리즘을 이용한 간단(?)하지만, 코드화(규칙화)하기 힘든 문제를 통해서 DP 문제 풀이에 조금 더 익숙해져보자. BaekJun - #9084 : 동전 (DP) 동전 0 이랑 비슷해 보이지만 이문제는 DP 문제이다. 동전 단위가 주어지고 해당 값을 만들 수 있는 경우의 수를 출력하는 문제인데, 문제 아이디어를 떠올리기가 역시 아직 쉽지 않다. 처음엔 01타일 문제를 먼저 떠올렸다. 가장 최근에 푼 01타일 문제를 겪은 후에 '베이스케이스를 찾아서, 그 케이스를 통한 확장에 대한 문제가 DP구나.' 라고 생각했었는데, 이 문제를 통해서 ..

오늘은 어제 하던 Greedy를 문제에 적용하면서 경험한 서사와 컴퓨터 시스템 약간을 추가해서 작성해 보겠다. BaekJun - # 11047 : 동전 0 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전 0의 문제를 처음 풀려고 생각했을 때는, 굉장히 쉽다고 생각했다. 거스름돈을 계산할 줄 아는 사람이라면 코드를 짜는 건 어렵지 않다. 하지만 문제는..

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

오늘은 컴퓨터 시스템 공부한 것을 최대한 정리하고, 알고리즘 풀이를 살짝 곁들일 생각이다. CS:APP 책이 영문판을 번역한 번역본이라, 글이 너무 이상하고 낯설게 작성되있다. 최대한 이해하기 쉽게 내 말로 풀어서 작성해 보겠다. 아무튼 그렇게 3주차가 시작됬다. 이번주도 파이팅~ 컴퓨터 시스템 (CSAPP) 정리 1.5 캐시가 중요하다. 프로세서인 CPU는 컴퓨터의 뇌로 역할을 수행하고, 레지스터와 메인 메모리, 디스크 메모리는 CPU에게 수행 명령을 지시 받는데, 파일을 실행 시에 인스트럭션(수행 명령)들이 메인 메모리로부터 CPU로 복사되고, 인스트럭션을 읽고 실행을 수행하라는 명령을 내리는 것으로, 디스크 메모리에 있던 파일을 메인 메모리로 복사하고~ (이때, 바로 디스크의 메모리가 프로세서로 ..

드디어 어제 마지막으로 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시간을 고민하며 코드를 구현해 나갔지만, 내 머리로는 도저히 멍..

오늘은 DFS를 마치고 위상정렬에 대해 공부하기 시작했다. 위상 정렬 위상 정렬이란? 방향이 있는 그래프에서 방향을 거스르지 않고 모든 정점을 잇는 경로를 선형순서로 나열하는 것 이때 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 이때 든 생각은, 알고리즘 문제에서 일단 사이클이 있는지를 판단하고 사이클이 있다면 위상 정렬을 하도록 하는 문제가 있을 거라 생각했다. 사이클이 있는지 판단하는 함수는 Kruskal에서의 노드의 부모를 고정하여 판단하는 방식이 사용될 것 같다. [정방향] 위상 정렬의 동작 예시(경로를 나열하기 위한 진행 순서)는 다음과 같다. 1. 진입차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐에서 POP을 하고 POP한 노드에서 나가는 간선을 제거한다. 3. 제거한 후 진입차..

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