목록2024/08 (18)
tlov
문제: boj.kr/2156날짜: 08/30 (금)성공여부: X n = 1 or 2일 때는 무조건 1을 먹고 1, 2를 먹는게 최대값이다. 그럼 진짜 로직의 시작은 n = 3일 때부터이다. n이 3일 때부터 보면 3가지의 경우의 수로 나뉜다. n을 먹지않고 이전(n-1)까지 먹은 것을 선택하거나, n-2까지의 먹은 것을 선택하고 n을 먹거나, n-3까지의 먹은 것을 선택하고 n-1, n의 와인을 먹는 것이다. 이를 식으로 나타내면 Math.max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n]) 문제가 계단 오르기 문제와 유사해서 dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n] 식으로만 생각했는데, 꼭..
문제: boj.kr/1463날짜: 08/29 (목)성공여부: O (00:37:07) 실버3의 DP 문제이다. x가 3으로 나누어 떨어지면 3으로 나눈다.x가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다. 정수 x에 대해서 적용할 수 있는 3가지 연산인데, 뭔가 연산의 순서가 있는 것처럼 보여서 순서를 지켜서 풀려고 하면 틀린다. 위의 3가지 연산은 3가지 경우의 수이고 정수 x에 대해서 각각 모두 적용시켜서 모든 경우의 수를 찾아서 푸는 문제이다. 라는 생각을 가지고 완탐으로 풀 수 있을까? 라고 생각해보아야 한다. 그럼 시간 복잡도는 100만개의 숫자에 대해서 3개의 연산을 하므로 3^100임을 알 수 있다. 근데 문제에서 주어진 시간이 0.15초이므로 무조건 시간 초과가 날 것이다.. 그럼 어떻게 풀..
문제: 1859. 백만 장자 프로젝트날짜: 08/28 (수)성공여부: O(댓글힌트) 그리디 문제이다. 그리디에 대한 준비가 안되어있어서 좀 어려웠다. 결론부터 말하면 배열을 뒤로 반복해서 풀면 풀리는 문제이다. 무조건 배열을 앞에서부터 반복할 필요가 없다는 생각을 해야한다.. 이게 참 쉬운데 어려운듯하다. 처음 풀이는 앞에서부터 반복하면서 현재 값에서 바로 뒤에 자기보다 작은 값이 나오면 현재 값을 기준으로 지금까지 산 물건들을 팔아 그 차액을 ret 변수에 더했다. 예제만 놓고보면 해당 로직에 문제가 없다. 그런데 아래 반례가 있다.1 2 3 5 2 4 7 11 2 3 5 2 4까지 모두 산다음에 7에서 팔면 최대 이익!그러나, 위의 로직대로 한다면 1 2 3 까지 산 후 5에서 모두 팔고, 다시 2 ..
문제: boj.kr/2632날짜: 08/25 (일)성공여부: X 이 문제 너무 어려웠다. 처음으로 생각해낸 로직은 그냥 무식하게 모든 경우의 수 구해서 원하는 값 되는 거 찾으면 되지 않을까? 하고 문제 범위를 봤는데, 3 이다. 1000C1, 1000C2, 1000C3 .... 이걸 A, B 두 번 구해서 A, B에 대해 다 for문 돌린다면 무조건 시간 초과날 것이 뻔했음.. 근데 이거 아니면 아무 로직도 생각나지 않아서 해설 봤다. 정리하면 다음과 같은 로직으로 구성된다. 원형을 선형 자료구조로 만들기나오는 값에 대해서 A, B 각각 경우의 수 개수를 구하기구한 개수를 이용해서 ret 값 만들기 1. 원형을 선형 자료구조로 만들기해당 문제는 피자를 연속해서 팔기 때문에 피자가 원형이라 한바퀴 돌아..
문제: boj.kr/17143날짜: 8월 24일 (토)성공여부: X 가까운 상어를 잡는다. 그리고 상어가 움직인다.상어가 움직인 후 같은 자리에 상어가 있으면 크기 비교 후 둘 중 하나 죽음 구현해야 될 로직낚시왕 move낚시왕의 상어 잡기상어 move상어끼리 잡어 먹기⠀여기서 가장 어려운 것이 상어의 움직임을 구현하는 것이다. 상어의 움직임에서 생각해볼 것이 있다. 상어는 speed를 가지며 1초에 speed만큼 움직인다. 그리고 움직이면서 벽을 만나면 방향을 바꾸고 진행한다. 이런 움직임은 0부터 speed까지 증가시키며 한 번에 한 칸씩 이동하면서 구현할 수도 있지만, 강의에서 사용한 모듈러 연산을 이용하면 시간을 좀 더 단축할 수 있다. 모듈러 연산을 이용하면 어떻게 구현을 하는 것일까?강의를 ..
boj.kr/17406 푼 과정배열의 이동 연산이 K개 주어지면 그 K개를 모두 1번씩은 사용한 후 배열의 최솟값을 구하는 것이다. 배열의 회전 연산 K개를 어떤 순서로 하느냐에 따라 최종 배열의 모습이 달라지게 되므로 처음 생각해낸 아이디어는 '순열'이었다. 그래서 주어진 이동연산들을 2차원 배열에 담아 인덱스를 순열로 뽑는 알고리즘을 생각했다. 그렇게 K개가 뽑히게 된다면, 회전 연산을 수행하면 될 것 같았다. 회전 연산의 경우 이전에 풀었던 boj.kr/17144 문제에서 아이디어를 얻어 해당 구역들을 담으려고 했으나... 구역을 어떻게 담는지 생각하는 것보다 그냥 4번의 for문을 돌리는 것이 훨씬 빠르게 구현이 되는 것 같아서 4번의 for문으로 직접 회전 연산을 구현했다. 회전 연산을 수행할 ..
이화여자대학교 (반효경, 2014) - 운영체제 Computer를 Host라고도 함. 여기에 붙어 host에서 처리된 결과를 내놓거나 디스크를 읽는 등의 작업을 한다. 해당 i/o device의 작업 수행을 위해서 device controller 라는 것이 붙어있고 이 controller는 작업을 처리하면서 생긴 결과를 local buffer에 저장한다. 그리고, CPU에게 완료된 작업을 알려주기 위해 인터럽트를 건다. CPU는 메모리에 올라와 있는 기계어 명령 4바이트를 하나씩 계속 수행한다. 메모리 어디 있는 기계어를 읽냐면 CPU 내의 레지스터에서 Program Counter라고 하는 것이 있는데 얘는 실행할 명령어의 메모리 위치를 가지고 있음. CPU가 해당 명령어를 수행하면 PC는 다음 명령어..
이화여자대학교 (반효경, 2014) - 운영체제 이번 챕터는 컴퓨터 시스템에서 하드웨어가 어떻게 동작하고 프로그램들이 하드웨어 위에서 어떻게 돌아가는지 설명하는 것이 목표이다. 컴퓨터 시스템 구조- Computer [CPU, Memory]- I/O Device [Disk, Keyboard, Printer, Monitor] 메모리는 CPU의 작업 공간이다. CPU는 매 쿨럭마다 메모리에서 기계어를 하나씩 읽어 실행한다. I/O 디바이스들은 별개의 디바이스들이다. 키보드, 마우스 같은 것은 두드리면 전기 신호가 들어가므로 input device, 프린터 같은 것은 결과를 출력하므로 output device이다. Disk는 input/output device 역할을 둘 다 수행한다. i/o device는 각..