손가든 개발일지

오늘은 컴퓨터 시스템 공부한 것을 최대한 정리하고, 알고리즘 풀이를 살짝 곁들일 생각이다. 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..

오늘 팀원들과 아침에 그래프에 대해 발표했다. 상우형은 개괄적인 이론과 종류, 용어들을 설명했고, 의훈님은 성능과 관련하여 접근했다. 나는 그래프를 이해하기 위해 트리에 대해 설명했는데 서로 그래프에 대해 분석하고 잘못된 설명이 있으면 바로 잡으면서 개념을 조금 더 단단히 잡을 수 있게 됬다. 이런식으로 매일 발표를 진행할 텐데 앞으로도 좀 더 적극적으로 발표 내용을 만들어 가야겠다고 생각했다. 오늘은 BFS를 공부하겠다. BaekJun - #2178 : 미로 탐색 (BFS) 미로의 최단 거리가 몇인지 확인하는 문제였다. DFS로 많은 사람들이 푼 것 같은데 BFS가 가장 좋은 방법이라고 난 생각한다. 실제로 정글 커리큘럼 내 BFS 문제로 분류 되었기도 한다. 미로의 시작으로부터 방문을 시작하여 동서남..

새로운 2주차를 맞이하고 조원이 변경됐다. 2주차는 조원들과 매일 1개의 키워드를 정해 공부한 뒤 익일 오전에 발표하는 형식으로 공부하기로 정했다. 그래프 자료 구조 그래프 알고리즘은 코딩 테스트에서 주로 사용되는 풀이 방식의 알고리즘으로, 매우 중요한 만큼 어렵기도 하다. 팀 코어타임 발표를 위해서라도 열심히 준비해보자 구현 방법 그래프 G = (V,E)를 표현하는 두가지의 표준 방법이 있다. 1. 인접 리스트의 집합 2. 인접 행렬 먼저 인접 리스트(Adjacency List)의 집합으로 그래프를 표현하는 방식 이 방식은 낮은 밀도의 그래프에 선호된다. 메모리 양이 세타(V+E) 여서 데이터 사용량측에서 매우 바람직한 특성을 가진다. 인접 행렬(Adjacency Matrix) : 2차원의 배열을 사용..

2주차가 시작 되기 전 아침. 밤에 자면서 아무리 생각해도 방법이 떠오르지 않던 문제를 풀었다. Baekjun - #2504 괄호의 값 (스택 : 상) 처음엔 재귀함수를 써야하나 했다. 괄호의 특성 상 안의 연산들을 전부 기억 한 후 곱연산을 수행해야 했기 때문에 재귀방식이 먼저 떠올랐지만 어떻게 재귀로 풀어내야 할지 도무지 답이 안나왔다. 이 문제는 괄호에 숫자는 없지만 괄호의 종류 별로 값을 부여해 제일 서로 옆끼리 붙어있는 애들은 더하고, 속해있는 애들은 겉에 애가 곱해주는 문제를 수행해야 했다. 각 케이스 별로 따로 처리하려고 했으나 그 방법으론 처리되지 않는 케이스가 너무 많아서 구글링을 하니까 '분배법칙'을 사용하라는 얘기를 듣고 방법을 자세히 들여다 봤다. 2 x ( 2+ 3x(3)) = (..

내일이면 2주차가 시작되서 오늘 안에 알고리즘 문제를 전부 다 풀어내야 한다. BaekJun - #1629 solving (분할 정복 : 중) a를 b만큼 거듭제곱 한 뒤 c로 나눈 나머지를 출력하는 문제이다. b가 10^8값을 넘기 때문에 for문으로 b만큼 곱하여 풀지 말라는 의도이다. 아래 코드로 해결했다. from collections import deque import sys import heapq a,b,c = map(int,sys.stdin.readline().strip().split()) def div_mup(a,b): if b == 1: return a%c elif b%2 == 1: return div_mup(a, b//2)**2*a%c else: return div_mup(a, b//2..