문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1038 감소하는 수 제출 언어: Swift 알고리즘 분류: 브루트포스 알고리즘 백트래킹 풀이 이 문제를 한참 읽어도 이해가 가지 않았는데 이해한 바로는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31.. 등 처럼 자리수가 작아질 때마다 수도 감소하는 수를 감소하는 수라고 한다 즉 10은 10번째 감소하는 수이고, 20은 11번째 감소하는 수이다 알고리즘 설계 일의 자리 숫자중 감소하는 수는 0 9이고 십의 자리 숫자중 감소하는 수는 10, 20, 21, 30, 31, 32, 40 ..이다 백의 자리 숫자중 감소하는 수는 210, 310, 320, 321등이다 내가 생각한 알고리즘은 이중 배열 arr를 만들어서 ..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2667 단지번호붙이기 제출 언어: Swift 알고리즘 분류: 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 그래프 이론 그래프는 정점과 그 정점들을 연결하는 간선으로 이루어진 자료구조의 일종이다 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 조건에 맞는 모든 정점들을 한 번씩 방문한다 DFS(Depth-First-Search) 깊이 우선 탐색 BFS(Breath-First-Search) 너비 우선 탐색 방향이 있을수도, 없을수도 있다 ex) 지하철 노선의 최단 경로 및 선수 과목 등 DFS 최대한 깊이 탐색한 후, 더 이상 깊이 갈 곳이 없을 경우, 옆으로 이동한다 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2294 동전 2 제출 언어: Swift 알고리즘 분류: 다이나믹 프로그래밍 풀이 다이나믹 프로그래밍 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해 Table에 부분문제의 solution을 저장한다 항상 최적의 해를 보장하지만 Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다 알고리즘 설계 해당 문제의 예시로 dp 배열을 생성해보면 다음과 같다. dp[0] = 0 dp[1] = 1 (1) dp[2] = 2 (1+1) dp[3] = 3 (1+1+1) dp[4] = 4 (1+1+1+1) dp[5] ..
컴퓨터 시스템과 구조 1. 전체적인 스토리 I/O Device는 host 컴퓨터에 붙어서 host에 입출력하는 역할을 수행한다 Device Controller는 I/O Device를 통해 데이터를 읽거나 쓰면 local buffer에 저장한다 Device Controller가 CPU에 어떠한 정보를 제공할 때에는 Interrupt를 건다 CPU는 매순간 메모리 레지스터에 있는 PC가 가리키고 있는 메모리에 올라와있는 기계어(Instruction) (보통 4Byte)를 하나씩 읽어와서 실행한다 PC는 다음 Instruction 실행할 위치를 가리킨다. 실행 후 += 4Byte 하지만 항상 순차적인 처리는 아님! If문 해당안하거나 Interrupt 발생 시 메모리 주소를 점프하여 Instruction 수행..
컴퓨터 시스템과 구조 컴퓨터 시스템에서 어떻게 하드웨어가 작동하는가? 프로그램들이 이러한 하드웨어 위에서 어떻게 돌아가는가? 1. CPU CPU는 매 clock cycle마다 instruction (기계어)를 하나씩 읽어서 실행하고 하나의 Instruction을 마치면 Interrupt line을 확인하여 다음 Instruction 수행 여부를 결정한다 메모리 : CPU의 작업 공간 레지스터 : CPU내에 메모리보다 더 빠르고 정보를 저장할 수 있는 작은 공간들이 있다. mode bit: CPU내에서 실행되는 것이 운영체제인지 사용자 프로그램인지 구분해준다. 사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않도록 하기 위한 보호 장치 필요 Mode bit을 통해 하드웨어적으로 ..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2630 색종이 만들기 제출 언어: Swift 알고리즘 분류: 분할정복 재귀 풀이 우선 2차원 배열을 생성하여 입력 값을 넣어준 후에, 다양한 경우의 수로 나누어서 처리를 해주었다 . 분할정복이므로 자를 색종이의 배열과, 현재 배열의 크기를 인자로 받는 재귀함수로 구현하였고, 종료조건을 해당 배열의 크기가 1일 때, 해당 색종이의 색에 따라 count에 1을 더해주고 해당 재귀를 종료하도록 하였다. 이 문제에서 중요한 것은 색종이 한 칸의 개수를 세는 것이 아니고 잘라진 색종이의 개수를 세므로 1씩만 더해주면 된다. func cutConfetti(_ tempArr: [[Int]], _ size: Int) { // 더 이상 자를 색종이가 없는 경우 if..
1. Introduction to Operation Systems 운영체제란? 좁은 의미의 정의 : 커널 (운영체제의 핵심) 운영체제 커널: 컴퓨터 부팅 이후로 항상 메모리에 상주하는 부분 넓은 의미의 정의 : 커널을 포함한 각종 주변 시스템 유틸리티 (window 설치하면 부가 프로그램 같이 설치 - 파일 복사 기능과 같이 커널에 포함되지 않는 것들 포함) 메모리에 상주하지 않는 별도의 프로그램 포함 운영체제의 목적? 컴퓨터 시스템의 자원을 효율적으로 관리하기 위해 프로세서, 기억장치, 입출력 장치 등의 효율적 관리 (CPU, 메모리, I/O Device) 사용자간의 형평성 있는 자원 분배 주어진 자원으로 최대한의 성능을 내도록 사용자 및 운영체제 자신의 보호 프로세스, 파일, 메시지등을 관리 (소프트..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2293 동전 1 제출 언어: Swift 알고리즘 분류: 다이나믹 프로그래밍 풀이 다이나믹 프로그래밍 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해 Table에 부분문제의 solution을 저장한다 항상 최적의 해를 보장하지만 Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다 알고리즘 설계 아래의 그림과 같이 다이나믹 프로그래밍 배열을 하나 생성하여 부분 문제의 해에 해당하는 값들을 넣어주었다 i : 해당 동전까지 사용할 수 있을 때 만들 수 있는 경우의 수 j : 가치의 합을 1원부터 k원까지..
