본문 바로가기

전체 글

(186)
백준 [11054] 가장 긴 바이토닉 부분 수열 이 두 문제를 풀었다면 쉽게 풀 수 있다. www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A..
백준 [9251] LCS 여기에 설명이 진짜 잘 돼있다. ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하 ko.wikipedia.org 문자열 A, B가 있을 때LCS함수는 다음과 같이 정의한다. i = 0 또는 j = 0 일 때 -> 0 A[i] == B[i] 일 때 -> LCS[i][j] = LCS[i-1][j-1] + 1 A[i] != B[i] 일 ..
백준 [12865] 평범한 배낭 유명한 배낭 문제 영문판 위키에 자세하게 나와있지만, 그림 설명은 없다. en.wikipedia.org/wiki/Knapsack_problem Knapsack problem - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Problem in combinatorial optimization Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the o en.wikipedia.org 캐시의 크기를 다음과 같이 ..
백준 [2580] 스도쿠 이전 백트래킹 문제들이 일차원 배열을 이용해, 한 줄씩 처리하는 게 가능했다면, 이 문제는 이 방법이 먹히지 않았다. 특히, 입력을 2차원 배열의 스도쿠 판만 받아야 한단 생각을 해서 많이 꼬이고 헤맸다. 이 문제에서 우리가 고려해야 할 사항은 3가지다. 1. 가로줄 2. 세로줄 3. 3*3 정사각형 맨 처음에 스도쿠 판에 저장된 데이터만 가지고 올바른 값이 들어가있는지 검증하는게 무척 어려웠다. 이전에 풀었던 N-Queen 방식대로하면 세로줄까진 어찌어찌 해결해도, 3*3 정사각형에서 매번 헤맸다. 해결방법은 생각보다 간단했다. 입력을 받고나면, 해당 위치의 가로, 세로 3*3 칸에 입력받은 숫자가 사용됐다는 것만 표시하면 된다. 그림으로 설명하자면 이렇게 입력을 받는다면 가로의 정보를 저장하는 배열엔..
백준 [9663] N-Queen 백트래킹을 이용한 문제. 생각한 방법은 3가지였다. 3번째 방법이 내가 적용한 풀이다. 1. 2차원 배열을 선언해, 퀸이 배치 될 때, 퀸의 경로에 1을 더해서, 다음 퀸이 이 자리에 오지 못하게 한다. 만약, 다른 퀸의 경로하고 겹치는 경우 1을 또 더해준다. 아래 그림이 예시다. 하지만, 이렇게 되면, 퀸 배치를 옮길 때, 복구 작업도 해줘야 하기 때문에, 시간이 오래걸리고, 코드도 깔끔하게 나오진 않았다. 2. 매 탐색마다, N 크기를 1씩 줄이기 어떤 자리에 퀸이 들어왔단 것은 해당 행과 열엔 퀸이 들어오지 못하니, 다음 재귀함수에선 (N-1 * N-1)만큼의 크기를 검사하는 방식 여기서 문제는 위의 그림에서 보듯이, 2번째 퀸이 3번째 열에 배치되면, 2번째 열에 퀸을 배치할 수 있음에도 불구하..
6. Elliptic curve 보호되어 있는 글입니다.
Control Flow cpu는 한 번에 하나의 명령어만 수행할 수 있음 이 명령어의 순서를 Control Flow라고 한다. Control Flow의 전환 프로그램 상태 changing - branch로 점프 - return call 시스템 상태의 changing - 디스크나 네트워크로부터 데이터가 왔을 때, - 0으로 나눌 때 - 사용자가 커맨드에서 ctrl+c를 누를 때 - 시스템 타이머 만료(일정주기 마다 만료됨) 이런 예외를 처리하기 위해, 프로그램은 OS에 제어권을 넘긴다. (시스템 상태 변화는 usermode에서 해결이 불가능하다.) Exception 위에서 시스템 상태의 chaingin이 일어나는 상황을 예외(Exception)이라고 한다. 에러가 처리되고 나면, 원래 실행했던 다음 명령어로 이동시킨다. Arm에..
21 디스크 접근 시간 A : 트랙 B : 섹터 C : 트랙 A의 섹터 D : 클러스터 (섹터의 집합) 탐구 시간(seek time) : 디스크 실린더에 헤드를 놓는 시간 지연 시간(Rotiaion time, latency) : 헤드가 트랙 내에서 원하는 섹터까지 가는 시간 블록 전송 시간(block ransfer time) : 원하는 섹터를 읽는데 걸린 시간 실린더의 개수 : 원판의 동심원(트랙) 개수 한 실린더에 들어가는 트랙 수 : 원판의 개수 * 2 ( 앞 뒷면 다 쓰니) -> 원판이 여러 개일 때, 같은 위치에 있는 트랙들 수를 말하는 거임 예시를 보자 예시 1 Block size B : 512 Bytes, Gap size G : 128 Bytes 이고, 한 트랙에 존재하는 블록이 20개, 한 표면에 존재하는 트랙이 ..