매일 성장하자!!

문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 1 2 3 밖에 존재하지 못하는 수열중, 가장 작은 좋은 수열을 구하면 된다. 즉, 나쁜수열이면 안된다.. 가장 작은 숫자를 구하라 하였는데, 1 -> 2 -> 3 으로 탐색을 하면 자연스럽게 가장 작은 숫자가 나온다. 백트래킹 문제로 나쁜 수열이면 가지치기를 해서 경우를 많이 줄여 주면 간단하게 풀수있다. 즉, 재귀함수로 돌리다가 조건에 맞지않으면 그뒤의 가지들은 잘라버리고 다음 가지로 넘어간다...

문제 https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net 풀이 문제는 너무 단순한데 보자마자 쉽게 어떻게 풀지 떠오르지가 않았습니다. 구래서, 일단 제일 작은수부터 나열해보았습니다. 0 1 2 0 1 2 3 4 5 6 7 8 9 10 20 21 30 31 32 40 41 42 43 50 51 52 53 54 60 61 62 63 64 65 70 71 72 73 74 75 76 80 81 82 83 84 ., 97 98 (세자리) 2..

I/O System이 어떻게 동작하고, OS는 시스템 성능을 높이기 위해서 어떻게 I/O System을 support하는지 알아보자. 또, 디스크는 OS가 어떻게 관리하는 지도 알아보자. I/O System (HW) I/O System은 기본적으로 입력장치라면 데이터를 입력 받아서 메모리에 저장하고 프로세서가 메모리에 저장된 데이터를 사용하여 연산할것이다. 반대로 출력장치라면 프로세서가 연산/명령을 하여 메모리에 저장된 데이터를 출력장치로 내 보낼 것이다. I/O Mechanisms 좀더 세밀하게 어떤 방식으로 I/O를 통해서 데이터가 전송되고 처리하는지를 알아보자. Processor controlled memory access 이름에서 알수 있듯이 I/O로 부터 주고 받는 데이터는 프로세서(CPU)의 ..

문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 백트래킹 문제이다. 적절하게 재귀함수를 이용해서 계란을 칠수있는 모든 경우의 수를 파악해야한다. 어떻게 하면 달걀을 집어서 칠 대상 달걀을 고르는 경우를 생각할수있을까? 일단 어떤식으로 할수있는지 간단하게 생각하자. 달걀 a, b, c, d, e 다섯개가 있다고하자. a 를 들고 b를 칠수있다. 그다음은 한칸 오른쪽 달걀을 들어야한다. 치는 대상은 아무거나 하나를 칠수있으..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 백트래킹 문제이다. 재귀함수를 통해서 탐색하되, 가지치기를 통해 경우의 수를 줄여야한다. 재귀함수에대한 이해가 부족하면 풀기어렵다.(백트래킹 기본 N, M문제를 많이 풀어봐야한다 생각함!!) 2차원 배열로 어떠한 도시에서 어떠한 도시로가는 비용이 적혀있다. 외판원이 어떠한 도시에서 출발하여 모든 도시를 돌고 다시 시작한 어떠한 도시로 돌아오는..

문제 풀이 재귀함수로 풀면된다. 재귀함수로 풀다가, 뽑고자하는 M개를 뽑으면 경우를 만들고, return해서 재귀 끝내주고 다시 그 다음 경우를 계속해서 보면된다. 수열은 중복이 되면 안된다는 것에 유의하자. 나는 두가지 방법으로 풀었다. 1) stack을 이용한 풀이 방문한 숫자의 순서를 기록해야 하므로 먼저 방문한 녀석을 순서대로 스택에 담는 형태로 풀었다. 방문한 숫자를 스택에 넣고, 스택의 크기가 M과 같으면 stack에 들어간 순서대로 출력하고, 다시 스택에서 빼고.. (스택에 해당 수가 있으면 다음 숫자 탐색) 를 반복해서 풀었따. 2) visited boolean 배열과, 결과를 담을 result int 배열 중복에 대한 처리는 visited boolean 배열을 통해 하였다. 그리고 탐색한..

OS가 파일을 어떻게 관리하는지 알아보자. 그렇기 위해선 파일시스템이 뭔지, 파일이 어디에 저장되는지 등을 알아야겠다. 먼저 파일이 저장되는 보조기억장치인 Disk에 대해서 알아보자.(HDD -기준) Disk System 데이터를 영구적으로 저장하는 저장 장치이다. 비 휘발성이라는 특징을 가졌다.(영구적이므로.) 파일은 이 디스크에(보조기억장치)에 저장된다. 디스크는 이렇게 Disk Pack이라는 장치로 이루어져있다. 위에서 Disk Pack을 보면 이렇게 생겼고, 각 섹터(섹터가 뭔지는 바로 아래서 알아볼것!) 마다 번호가 있는 것을 알수 있다. 스포하자면 이 섹터에 데이터가 저장된다. Disk Pack 실제로 데이터가 디스크에 저장되는 하드웨어이다. 어떻게 구성되어 있는지 알아보자. 먼저 원들이 여러..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 제일 작은 수가 되려면 -가 나오고 뒤에 +들이 나오면 -(a + b + c + d +...)만 고려하면 된다. 처음에 나는 split이 생각나지않아, 결과 스택과 버퍼 스택을 만들어서, -가 나온다음 뒤에 +들이 나오면 버퍼 스택에 다 넣고 다시 - 가나오면 버퍼스택의 값들 다 더해서 - 붙인 값을 결과 스택에 넣고.. 이런 복잡한 방법으로 풀려 노력했다. 그냥 문자열 split..

실제로 객체지향적으로 설계를 처음부터 끝까지 해보자. 그리고 객체지향 설계를 세가지 관점에서 바라보아 보자. 커피 전문점 어디서나 볼수 있는 동네 카페에서 손님이 커피를 주문해서 받는 과정까지를 객체지향적으로 설계해보자. 객체 생각하기 큰 시스템을 객체들로 구성되었다 생각하고 객체들로 나누어보자. 손님 - 손님 객체 메뉴판 - 메뉴판 객체 메뉴 - 메뉴 객체 바리스타 - 바리스타 객체 커피 - 커피 객체 객체간 관계 생각해보기 손님은 바리스타에게 주문해야함 : 손님 - 바리스타 관계 O 손님은 주문하기 위해선 메뉴판에서 메뉴를 골라야함 : 손님 - 메뉴판 관계 O 메뉴판에있는 메뉴들중 몇개를 먹을 커피를 골라야하므로 : 메뉴판 - 메뉴 관계 O 바리스타가 손님으로부터 주문받은 메뉴를 커피로 만들어야함 :..

문제 https://www.acmicpc.net/problem/11052 풀이 민규는 N개의 카드를 사는데 최대 가격을 지불해야한다. 최초 시도할때 나의 생각은 N개의 카드를 산다하면 1개가든 팩 N개, 1개가 든 팩 N - 1개 + 2개가 든 팩 1개, 1개가든 팩 N - 2개 + 2개가 든 팩 2개, ... 이런식으로 경우의수를 모두 구해서 최대값을 구해야하나? 즉 브루트포스로 풀어야하나란 생각을 했다. 이렇게 생각하니 어떻게 풀어야할지도 모르겠고 막막했다. 그래서, dp를 통해서 풀자! 라는 생각을 했다. i개의 카드를 사기위해 최대 가격을 지불해야한다. 이미 dp테이블에 1부터 i - 1까지 카드를 살때 최대 가격이 적혀져있다고 가정하자. 그렇다면, i개를 사기 위해 따져봐야하는 경우는 dp[1]..