Computer Science

[CSAPP] 7.1 Compiler Drivers(컴파일러 드라이버)

링킹이란 다양한 조각들의 code와 data를 하나의 file에 모으고 결합하는 과정. 이로 인해 이 file은 memory에 load하고 실행 가능해도록 한다. 링킹은 여러 단계에서 실행될 수 있다. at compile-time : source code가 machine code로 번역되는 시간에 at load-time : program이 memory에 로드되고 loader에 의해 실행되는 시간에 at run-time : 응용프로그램에 의해 어떠한 시간에 어떻게 linking해야 하는지는 linker에 의해 자동적으로 수행이 된다. 링킹을 알아야 하는 이유 1.큰 program을 build하는 데에 도움이 된다.(펼치기) 큰 program에서의 에러는 다음과 같다. missing module missin..

[CSAPP] 6.6 Putting It Together: The Impact of Caches on Program Performance(프로그램 성능에 대한 캐시의 영향)

6.6 Putting It Together: The Impact of Caches on Program Performance(프로그램 성능에 대한 캐시의 영향) 프로그램의 성능에 영향을 미치는 두가지 요소를 통해 두가지 요소를 변형해가면서 read throughput으로 확인해보려 한다. read throughput이란? s초 동안 n번 read를 수행한다면 ⇒ s/n의 read throughput을 가진다. 두가지 요소는? cache size cache size가 작을 수록 temporal locality가 증가한다. stride-k k가 작을 수록 spatial locality가 증가한다. 이 두가지 요소를 이용해 다음의 3차원 그래프를 그릴 수 있다.

[CSAPP] 6.5 Writing Cache-Friendly Code(캐시 친화적 코드 작성)

6.5 Writing Cache-Friendly Code(캐시 친화적 코드 작성) 공통의 case에 대해 빠르게 해야 한다. ⇒ 프로그램에는 core function이 있을 테고, 이 함수에서 시간을 대부분 사용하게 된다. 각 inner loop 안에서 cache miss 횟수를 최소화 해야 한다. ⇒ load와 store의 총 횟수를 줄일 수 있음 stride-k pattern과 cache hit 위의 코드가 cache friendly 한지를 살펴보자. 지역변수 i와 sum : 합리적인 컴파일러라면은 register file에 저장하게 할 것이다. 다시 한번 집고 넘어가자면, register file은 memory 계층도에서 가장 높은 레벨에 있는 memory이다. stride-k pattern : 순..

[백준] 1987번: 알파벳_JAVA

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 2 ..

[백준] 11724번: 연결 요소의 개수_JAVA

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 즉 첫째줄은 정점의 수, 간선의 수이고 둘째 줄은 각 점이다. 아래 예시에서 1 2가 이어져 있고 2 5가 이어져 있고 5 1이 이어져 있는 그래프이다. 이런식으로 이해. 또 3 4가 이어져 있고 4 6이 이어져 있는 상태이다. 따라서 연결요소의 개수가 2가 나오도록 코딩을 해야한다. 6 5 1 2 2 5 5 1 3 4 4..