본문 바로가기

전체 글

(117)
Memory system 간단하게 CS:APP의 연습문제 9.4번을 풀면서 메모리, 캐시, 가상 메모리에 대해 정리해보려 한다. 문제에서 주어진 것 처럼 Virtual address가 0x03d7일 때 시스템이 어떻게 가상 주소를 물리 주소로 번역하고, 캐시를 접근하는지를 보겠다. 주어진 가상 주소를 bit 형태로 써보면 00 0011 1101 0111 이고, 여기서 TLB에 접근하기 위해 태그와 인덱스를 구해보면, 주어진 문제에서 4개의 집합을 가지니, VPN(0x0F)의 2개 하위 비트들이 집합 인덱스(TLBI)(0x03)로 사용되고, 나머지 6개의 상위 비트들은 태그(TLBT)(0x03)로 사용된다. 여기서 VPO(0x17)는 페이지의 크기가 2^6 =64바이트 이기 때문에, 하위 6비트에 해당하고 PPO 또한 물리 메모리..
Red–black tree 오랜만의 글, 자가 균형 이진트리의 한 종류로 색을 나눠서 그 균형을 잡는다. 내가 구현한 방식은 이 분의 영상을 기반으로 작성하였다. https://www.youtube.com/user/leejaku Jake Lee Digital Dynamics ~ http://ddmix.blogspot.com C++로 배우는 알고리즘, 스케치업 등의 동영상 강의를 싣고 있습니다. www.youtube.com 구현 과정이 다른 방식과 다른 점은 노드를 삽입하거나 삭제 하는 과정에서 RB 트리의 조건에 맞게 맞춰가면서 진행 한다는 점이다. 자세한 과정은 위의 강의에서 참고 할 수 있다. 또한 다른 접근은 밑의 페이지에서 확인 할 수 있다. https://en.wikipedia.org/wiki/Red%E2%80%93bla..
백준 2098 외판원 순회(python) 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 2 문제와 다르게 시간과 메모리 조건이 달랐기 때문에 비트 마스크 개념과 dp개념을 사용하여 접근한 문제입니다. 순회하면서 방문하는 노드의 상태를 비트의 형태로 표현해 주었습니다. 과정은 다음과 같습니다. 순회하면서 메모이제이션할 값들을 현재의 노드와 상태를 기준으로 저장해 주었습니다. 순회하면서 기존에 저장한 값이라면 dp 리스트에 저장된 ..
백준 22239 가희와 읽기 쓰기 놀이2(python) 문제 https://www.acmicpc.net/problem/22239 22239번: 가희와 읽기 쓰기 놀이 2 결과 리스트가 [2, 1, 2, 2, 3, 4, 2, 3]으로 주어졌다고 생각해 보겠습니다. [그림 1] 유효한 결과 리스트 결과 리스트에서 두 번 이상 등장한 수는 2, 3입니다. 2가 등장한 횟수는 4번, 3이 등장한 횟수 www.acmicpc.net 구현하기 까다로웠던 문제였습니다. DFS 방식으로 접근하여 풀었습니다. 주어진 제약 조건에 맞게 카드와 사람들 간에 관계를 연결하여 푸는 문제였습니다. 과정은 다음과 같습니다. 주어진 제약들과 카드 값들을 입력받고, 제약에 맞게 카드값들에 플레이어 번호를 넣어 줍니다. 탐색하는 함수에서는 만들어내야하는 결괏값이 있는지 확인하고, 있다면 값을..
백준 11049 행렬의 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP로 접근해서 해결한 문제입니다. 점화식이 쉽게 생각나지 않아서 도움을 많이 받았습니다. 이 문제는 주어진 행렬의 곱셈 순서에 따라 연산 횟수가 달라지는데 그중 최소 연산 횟수를 찾는 문제입니다. 과정은 다음과 같습니다. 값을 저장할 dp 리스트를 이차원으로 만듭니다 dp [i][j] = i행렬부터 j행렬까지의 최소 연산 행렬 간의 곱을 여러 경우로 만들어 낼 수 있어서 시작 ..
백준 20119 클레어와 물약(python) 문제 https://www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 문제에서 느꼈던 중요한 포인트는 물약을 만들 수 있는 레시피가 여러 개 존재할 수 있다는 점이었습니다. 만들 수 있는 레시피들의 포션의 존재 여부를 파악하면서 해당되는 레시피가 하나라도 완료되면 포션을 만들 수 있기 때문에 결과에 넣어주었습니다. 과정은 다음과 같습니다. 물약 데이터 클래스를 만들어서 연결될 점들과 레시피들, 필요한 포션의 개수들, 만들 ..
백준 2638 치즈(python) 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net BFS 방식으로 접근하였습니다. 문제의 접근 자체를 공기를 기준으로 할지 치즈를 기준으로 할지 정해서 풀 수 있었습니다. 저는 치즈를 기준으로 밖의 공기와 내부 공기를 나눠서 풀었습니다. 과정은 다음과 같습니다. 먼저 처음 주어진 상황에서 모든 공기를 돌며 외부 공기를 파악해줍니다. 다음으로 치즈를 찾아 외부 공기의 개수를 세줍니다. 조건에 맞게 접촉한 면이 2개 이상이면 지워져..
백준 14226 이모티콘(python) 문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 주어진 경우에 맞게 연산들을 진행해 나가며 목표 개수에 도달하는 문제입니다. BFS 방식으로 접근하였습니다. 과정은 다음과 같습니다. 각 경우로 조건을 나누어서 연산을 진행해 줍니다. 연산된 결과를 통해 이전에 접근했는지를 확인해줍니다. 가보지 않은 경우라면 큐에 넣어주고 과정을 진행합니다. 최종적으로 목표 개수에 도달하면 시간값을 출력해 줍니다. 확인 리스트를 2차원으로 한 이유는 화면에 있..