1. 컴퓨터 구조에 대한 인트로.
왜 하드웨어 배워야 되는가?컴퓨터 기본 구조를 알아야 정확하고 깔끔한 코드를 작성할 수 있다. 컴퓨터란 무엇인가?compute(연산하다) + er(하는 사람,도구)고정된 연산만 제공하면 Calculator연산을 작성하고 저장하기도 하면 Computer 컴퓨터는 3가지로 나뉜다 입출력장치CPU : 연산(program counter, arithmetic l
Category: Computer Science
27. 최소공배수, 최대공약수 (GCD, 유클리드 호제법)
최대공약수, 최소공배수를 다룬 문제가 나오면 GCD나 유클리드 호제법을 반드시 알고 있어야한다!알아보자! GCD 최대공약수를 구하는 알고리즘두 수 중 작은 수가 0이 될 때까지 반복하면 된다.큰수는 작은수가 되고, 작은수는 큰수를 작은수로 나눈 나머지가 된다. 123456789//a>bint GCD(int a, int b){ whil
26. 백준 10799번 쇠막대기
접근 아이디어 스택을 사용해서 “(“이 나올 때마다 push!“)”이 나올때마다 pop하고 나서 스택에 남은 요소 만큼 쇠막대기가 더해지거나 하나만 더해진다.이전에 “(“ 였으면 스택 요소 갯수만큼, 이전에 “)”였으면 그냥 1만 더해진다. 필요한 개념 삼항 연산자에 대해 알아보자.조건문 ? true일 경우 : false일 경우 1int add =
25. 백준 17413번 단어 뒤집기2
접근 아이디어 < >안에 있는 단어를 그렇지 않은 단어와 다르게 처리해야 한다.그러나 언제 < >가 나올지 모르는게 문제다!그래서 “>”를 기준으로 문장을 나누면 < > 문자열의 위치에 규칙이 생긴다.만약 < >가 있으면 항상 뒤 쪽에 있다는 것! 필요한 문법 이번엔 라벨을 사용해서 루프를 빠져 나왔다
24. 백준 1406번 에디터
이 문제는 참 고생 많이 했다 ㅋㅋ… 틀렸던 접근 1 주어진 문자열을 char 배열로 받은 다음, 이 녀석을 ArrayList에 저장하자.그 다음 arrayList를 하나더 추가해서 마치 스택처럼 사용하자.그렇게 모든 명령을 수행하고 나면두 arraylist에 저장된 요소들을 반복문으로 하나씩 출력하자. 123456789101112131415161718
23. 백준 9012번 괄호
문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄
22. 백준 9093번 단어 뒤집기
문제문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다. 입출력입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단
21. 백준 10828번 스택
문제정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty:
20. 백준 1004번 어린 왕자
문제어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다.어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다.하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다.은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에
13. 부팅
부팅컴퓨터를 켜서 동작시키는 절차. 부트 프로그램운영체제 커널을 저장소에서 특정 주소의 물리 메모리에 복사하고, 커널의 처음 실행 위치로 PC를 가져다 놓음ROM : 꺼져도 내용이 기억되는 특별한 RAM 바이오스를 메모리에 올리고 바이오스가 컴퓨터 초기화 저장매체의 MBR(master boot record)에 가서 부트 로더를 메모리로 가져옴부트 로더
12. 파일 시스템
파일 시스템운영체제가 저장매체에 파일을 쓰기 위한 자료구조, 알고리즘 파일 시스템은 왜 만들어졌을까? 비트 단위로 주소를 매겨서 사용하기에는 너무 비효율적!그렇다고 블록 단위(4kb)로 하자니 사용자가 각 블록의 고유번호로 관리하기 힘듬…그래서 추상적(논리적) 객체를 도입 : 파일사용자는 파일 단위로 다루고, 각 파일은 블록 단위로 관리하자! ~ 저장
19. 그래프 깊이우선탐색(DFS)
깊이우선탐색(DFS)현재 방문중인 노드와 연결된 이웃 노드 중 아직 방문하지 않은 노드 있으면, 그 노드를 다음에 방문.재귀함수로 작성, 마치 트리의 preorder방식과 비슷. psuedo code 12345678910DFS(v): mark v as visited node pre[v] = curr_time #pre리스트는 해당 노드에 첫 방
17. Backtracking 활용 - Subste Sum 문제
Subset sum주어진 집합의 부분집합의 원소 합이 특정 값이 되는 조건을 만족하는 집합을 찾아내는 문제.모든 집합을 찾아보는 건 2^n개임 DP로 푼다면?(안좋은 예시) 어떤 숫자가 포함될 경우와 그렇지 않은 경우를 모두 재귀적으로 표현 123456789subsetSum(A, i, S): #A는 배열, i는 포함 여부를 살펴보는 수의 인덱스 , S는
11. 가상 메모리와 페이징 시스템, 세그멘테이션 기법
가상 메모리실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기가 한계가 있음.(리눅스는 하나의 프로세스가 4기가를 차지함) 적은 메모리에서 여러 프로세스를 다루기 위해 등장한 개념이 가상 메모리! cpu가 한 프로세스의 모든 영역을 사용하지는 않는다,프로세스가 모두 4기가 씩을 부여 받더라도, 정작 사용하는 공간은 제한적이다.사용할 영역만 R
16. Backtracking
Backtracking답이 x1, x2, x3… 이런 형식으로 도출되는 문제에서, 유효한 답을 모두 찾는 경우 사용되는 알고리즘 기법 x1부터 차례대로 결정하면서 만약 어느 순간 조건에 맞는 답을 도출 못하는 상황에 마주하면,그 전 단계로 돌아가 다른 선택지로 다시 답을 찾아가는 방법이다. 이 기법은 굳이 더 알아보지 않아도 되는 경우를 확인하지 않도록 설
15. 그리디 알고리즘 활용 - 허프만 코딩
허프만 코딩 문제(Huffman coding problem)아스키 코드 : 알파벳과 문자들을 0~255개의 숫자로 배정한 것. 즉 8bit로 표현.이렇게 표현된 8비트의 비트들을 고정길이코드(fixed-length code)라고 한다.(문자열 100개면 800비트가 필요하게 된다.) 이때 a e i o u 같은 모음들은 빈도수가 높고 q z y는 빈도수가