728x90 프로그래밍18 [Operating System 운영체제] Computer System Overview 01-1 Cache [Operating System 운영체제] Computer System Overview 01-1 Cache 1. 캐시(Cache) - 128KB 정도로 작음 1) 프로세서(CPU) 내부에 있는 메모리 (L1, L2 캐시 등) - 속도가 빠르고 가격이 비쌈, 레지스터보다 Core에서 멀리 떨어져있다. 멀리 떨어져 있을수록 사이즈는 커지고 속도는 느려진다고 생각하면 된다. 2) 메인 메모리의 입출력 병목현상 해소 - CPU와 메인메모리 간의 속도차가 여전히 존재. 2. 캐시의 동작 - 일반적으로 HW적으로 관리 됨 캐시 히트(Cache hit) : 필요한 데이터 블록이 캐시에 존재 캐시 미스(Cache miss) : 필요한 데이터 블록이 캐시에 없는 경우. 캐시가 메인 메모리까지 접근해 데이터를 캐시로 가져.. 2021. 8. 31. [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 난이도가 매우 낮은 알고리즘 중 하나이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 빠르게 구할 수 있으며 특정한 상황에서는 그리디 알고리즘이 최적의 해를 구할 수 있게 해준다. 예를 들면 거스름 돈 문제이다. 무조건 더 큰 화폐 단위부터 거슬러 주는 것이 최적의 해를 제공한다. 즉, 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기법이 함께 사용되는 경우가 많다. 사실 뭔가 특별한 테크닉이 아니라 그냥 특정 경우에 평소 풀던대로 풀면 되는 듯 하다.. 유튜브 - 동빈나 그리디(Greedy) 알고리즘 [ 실전 알고리즘 강좌(Al.. 2021. 8. 30. [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다. 문자열 출력까지 포함하는 9252번 문제를 풀어보았다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 생각 포인트 다이나믹 프로.. 2021. 8. 27. [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 특징 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다. 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다. 보통 바텀업이 전형적인 형태이다. 다이나믹 프로그래밍 사용 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조 중복 부분 문제(Overlapping Subproblem.. 2021. 8. 27. [WEEK03] 알고리즘_그래프, DFS, BFS [WEEK03] 알고리즘_그래프, DFS, BFS 이번 주는 DFS(Depth First Search) 깊이 우선 탐색, BFS(Breadth First Search) 너비 우선 탐색에 대한 내용을 학습한다. 이 두가지 방법은 그래프의 탐색 기법으로 그래프에 대해 먼저 알아보자. 그래프 그래프는 정점(노드)과 간선(엣지)으로 이루어진 자료구조를 의미한다. 또한 간선의 방향의 유무에 따라 단방향 그래프, 무항향(양방향) 그래프로 나뉜다. 그래프를 표현하는 방식은 인접 리스트, 인접 행렬 두가지로 나뉜다. 일반적으로 인접 행렬이 많이 사용된다. 두가지 모두 익숙해져서 문제에 맞는 방법을 이용할 수 있도록 해야겠다. 1) 인접 행렬 그래프 - 모든 정보를 저장 - 장점 : 직관적, 쉽게 구현 가능 - 단점 :.. 2021. 8. 20. [백준_11279] 우선순위 큐, 최대 힙 [백준_11279] 우선순위 큐, 최대 힙 최대 힙을 이용해 원하는 값을 출력하는 우선순위 큐 문제를 풀어보았다. 내 코드 - 모듈 없이 do it! 책대로 풀었는데 시간초과가 떳다.... 남들은 더 간단하게 했는지 input()만 sys.stdin.readline()으로 고쳐주면 통과 된다는데 이 방식으론 통과가 안된다. 그래서 옆에 친구한테 물어보니 모듈을 쓰면 된단다 =.=;; 그래도 원리 이해한 거에 의의를 두는 걸로 import sys def heap_sort(a): def down_heap(arr, left, right): # left : 기준, right가 n-1 가장 마지막 leaf tmp = arr[left] parent = left #left 뺴고 다 heap 구조 가정 while pa.. 2021. 8. 16. 이전 1 2 3 다음 728x90
