CS (46) 썸네일형 리스트형 메모리 메모리 계층구조 -시간적 지역성(Temporal locality): 최근 참조된 명령어/데이터가 다시 참조되는 경향(반복문 for의 i) -공간적 지역성(Spatial locality): 최근 참조된 명령어/데이터의 이웃 부분이 참조되는 경향(배열, 순차적 실행) -원리: 계층에 데이터가 있음(hit), 없다면(miss) 다음 계층에서 읽어와서 적재 캐시 -CPU와 메모리 속도차를 줄이기 위해 사용 -여러 단계 사용 재귀 재귀란 무엇인가? - 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 문제풀이에서 재귀의 활용방식은? - Base condition에서 가능하고 n-1에서 된다면(가정) n에서도 가능함(귀납적 사고) 즉 위 조건을 확인하였으면 내가 할일은 n번째의 동작을 명시하고 미래의 함수에게 n-1을 맡김 재귀함수의 조건? -특정 입력에 대해서는 자기자신을 호출하지 않고 종료되어야 함 -모든 입력은 Base condition으로 수렴해야 함 메모리 낭비 방지 메모리 낭비 방지 -동적 적재(Dynamic Loading) -프로그램 실행에 반드시 필요한 루틴/데이터만 적재 -실행후 필요하면 그때 해당 부분을 메모리에 올림 cf) 정적 적재(static loading) -동적 연결(Dynamic Linking) -공통 라이브러리 루틴 연결을 실행시까지 미룸 -하나의 공통 라이브러리 루틴만 메모리에 적재되고 다른 실행시 이 루틴과 연결 cf) 정적 연결(static linking) -Swapping -메모리에 적재돼 있으나 사용되지 않는 프로세스를 Backing store(Swap device)로 몰아내기 -swap in / swap out 파이프 라이닝 파이프 라이닝 - 명령어의 데이터 경로를 세분화, 각기 다른 세부 단계를 동시에 수행 -> 여러 명령어 중첩 수행 가능 해저드(결과가 틀림) -구조적 해저드(하드웨어 동시요구 -> 충돌) -데이터 해저드(다음단계에 필요한 데이터 준비 X) -RAR(Read After Read): 문제 없음 -RAW(Read After Write): 선행명령어가 쓰기전에 읽는 문제 -WAR(Write After Read), WAW(Write After Write): 선행명령어가 읽거나 쓰기전에 갱신하는 문제 -명령어 해저드(주로 분기 명령어) 해저드 해결방법 -구조적 해저드 -명령어/데이터 메모리(캐쉬)를 분리하드웨어 추가/분할, 예약표, 입출력포트의 다중화 -데이터 헤저드 -포워딩(forwarding): ALU 출력이 .. DFS DFS란 무엇인가? -다차원 배열에서 각 칸을 방문할때 깊이를 우선으로 방문하는 알고리즘 문제풀이에서 DFS의 활용방식은? -Flood-Fill -그래프 트리 탐색에서 활용 BFS vs DFS(방문 순서) STL #define X first #define Y second int board[512][512]; bool vis[512][512]; int n=7, m=10; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); stack s; vis[0][0] = 1; s.push({0,0}); while(!s.empty()){ pair cur = s.top(); s.pop.. 모니터(monitor) 모니터 큐(상호배타로 블락된 쓰레드) 공유 자원 큐 -wait로 블락된 쓰레드 -notify()로 깨워야함 -세마포 보다 고수준의 개념 -공유자원 + 공유자원 접근 함수 -2개의 큐: 배타 동기 + 조건 동기 -Common Variable 접근 함수에는 최대 1개 쓰레드 -쓰레드가 wait()로 블록되면 새 쓰레드 진입가능 -새 쓰레드는 notify()로 블록된 쓰레드 깨울수 있음 -깨워진 쓰레드는 현재 쓰레드가 나가면 재진입할수 있음 모니터의 용도 -Mutual Exclusion(상호 배타) -Ordering(흐름 제어) 데이터 경로(2) 단일 사이클 vs 다중 사이클 -단일 사이클은 가장 긴 경로를 클락 사이클 시간으로 함(CPI는 무조건 1) -다중 사이클은 각 부분의 경로시간중에 가장 긴 시간을 클락 사이클 시간으로함 -파이프라이닝 기법을 위해 다중사이클을 사용 BFS BFS란 무엇인가? - 다차원 배열에서 각 칸을 방문할때 너비를 우선으로 방문하는 알고리즘 - 그래프라는 자료구조에서 모든 노드를 방문하기 위한 자료구조 문제풀이에서 BFS의 활용방식은? -인접한 칸에 대해서 색칠하는 Flood-Fill, 최단거리 문제 혹은 움직임이 정해져 있는 경우 Code #define X fisrt #define Y second int board[502][502]; bool vis[502][502]; int n=7, m=10; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main(void){ ios::sync_with_stdio(0); cin.tie(0); queue Q; vis[0][0] = 1; Q.push({0,0}); whil.. 이전 1 2 3 4 5 6 다음
