공대생 기록장

1. 컴퓨터 내부에서 프로세서 메모리 사이의 정보 전송에 사용하는 통로는? ① 버스 ② 레지스터 ③ 블록 ④ 보조기억장치 더보기 정답: ①, 시스템 버스는 프로세서와 메모리 사이뿐만이 아니더라도 모든 컴퓨터의 하드웨어들을 물리적으로 연결하여 서로 데이터를 주고받을 수 있게 하는 통로이다. 2. 프로세서에서 사용하는 버스 형태가 아닌 것은? ① 주소 버스 ② 제어 버스 ③ 데이터 버스 ④ 시스템 버스 더보기 정답: ④, 시스템 버스는 데이터 버스, 주소 버스, 제어 버스로 이루어져 있다. 3. 목적이 특수한 값 하나를 저장하거나 연산을 처리하다가 중간 값을 저장하는 프로세서에 위치하는 고속 메모리는? ① 버스 ② 레지스터 ③ 메인 메모리 ④ 캐시 더보기 정답: ② ① 버스는 메모리가 아니다. ③ 메인 메모..

입력장치로 받은 명령어 혹은 데이터를 메모리에 저장함 제어장치에 의해 정보를 인출하여 연산장치에서 처리 결과를 출력장치에 표시하거나 보조기억장치에 저장함 컴퓨터에 유입되는 정보는 컴파일러 등을 이용하여 이진화된 기계 명령어로 변환된 후 처리된다. 이때, 명령어의 구조는 어떻게 되며 어떠한 수행 과정을 거치는지에 대해 알아야 컴퓨터의 동작 과정을 더욱 자세히 이해할 수 있다. 명령어의 구조 연산 부호(오피코드): 데이터 전송, 산술 및 논리 연산, 제어 흐름 변경, 입출력 제어. 연산 부호가 n비트이면 최대 2^n개 연산이 가능 피연산자(오퍼랜드): 연산할 데이터 정보가 저장되기도 하지만 주로 데이터가 저장된 위치가 저장됨, 소스 피연산자와 목적지 피연산자로 구분됨 오퍼랜..

컴퓨터 시스템 = 하드웨어 + 소프트웨어 우리가 흔히 사용하는 컴퓨터 시스템은 하드웨어와 소프트웨어로 구성된다. 하드웨어는 운영체제라는 특별한 소프트웨어를 통해 관리되는데, 그렇기 때문에 운영체제를 이해하기 위해서는 하드웨어가 어떻게 구성되어 있는지에 대해 우선적으로 잘 알고 있어야 한다. 컴퓨터 하드웨어는 크게 프로세서, 메모리, 주변장치로 구성되며, 시스템 버스가 이 장치들을 연결해 준다. 1. 프로세서 중앙처리장치(CPU)라고도 불리는 프로세서는 컴퓨터의 모든 장치의 동작을 제어하고 명령을 실행한다. 제어 부분인 제어장치와 데이터 부분인 연산장치, 레지스터로 구성된다. 프로세서의 수가 많을수록 처리 속도는 빠르다. 탑재된 프로세서의 개수에 따라 싱글코어, 듀얼코어, 쿼드코어 등으로 불린다. 레지스터..

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다. 이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨..

https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 문제 봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열..

https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 ..

0-1 BFS란, 기존 BFS 알고리즘을 응용한 것으로 가중치가 0이나 1로만 주어진 그래프에서 최단 경로를 찾는 알고리즘이다. 최단 경로를 찾는 알고리즘으로는 다익스트라 알고리즘이 대표적이다. 그러나, 다익스트라 알고리즘으로는 O(ElogV) 또는 O(ElogE)의 시간복잡도를 갖지만 0-1 BFS 알고리즘은 O(V+E)의 시간복잡도를 가진다. 0-1 BFS 알고리즘 구현을 위해서는 덱 자료구조를 사용한다. 가중치가 낮은 간선이 우선순위가 높기 때문에 아래의 두 가지 규칙을 추가한다. 간선의 가중치가 0이라면 덱의 front에 정보를 추가한다. 간선의 가중치가 1이라면 덱의 back에 정보를 추가한다. 백준에서 풀 수 있는 대표적인 0-1 BFS 알고리즘이 적용되는 문제에는 13549번이 있다. htt..

순열과 조합의 차이는 순서에 상관이 있는지 없는지이다. 조합에서는 순서가 없기 때문에 시작점보다 작은 위치는 다시 방문하지 않는다. 그러나, 순열은 순서가 있기 때문에 시작점보다 작은 위치 또한 방문해야 한다. 라이브러리없이 구현하는 방법은 dfs 알고리즘을 이용하는 것인데, 그 중에도 재귀를 이용하여 구현할 수 있다. 순열(permutation)이란, 서로 다른 n개 중에서 순서에 상관하여 r개를 뽑는 경우의 수이다. arr = [1, 2, 3, 4] select = [False for _ in range(4)] result = [] def dfs(cnt): if cnt == 3: print(*result) return for i in range(4): if not select[i]: select[i]..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. ..