prefer2 Log

문제 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구..

시험은 2시부터 7시까지 5시간 동안 진행되었다. 나는 c++로 풀었다. 1,2,3,4번 풀었고 6번은 효율성을 통과하지 못했다. 4번까지는 호다닥 풀었는데 이후로는 쉽게 풀리지 않아서 한참 헤멨다. 5번은 이진트리인거 보고 바아로 패스했고, 7번은 7번이니까 안읽었다. 6번이 할만한 것 같아서 한참을 시도했는데 알고보니 6번은 유명한 문제라 쉽게 풀 수 있는 것 같다. 4번까지 푸는 과정에서 1번이 가장 오래 걸렸다. 항상 1번 문제는 문제를 잘 안읽어서 한참 헤메는 것 같다. 초반에는 이상하게 난독증이 생긴다. 문자열 관련된 내용이 많다보니 js나 파이썬으로 split 쓰면 얼마나 좋을까라는 생각을 많이 했다. c++로도 쉽게쉽게 문자열을 다룰 수 있도록 공부해야겠다. 대부분 간단한 for문이나 df..

문제 LZW 압축은 다음 과정을 거친다. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다. 단계 2로 돌아간다. 압축 알고리즘이 영문 대문자만 처리한다고 할 때, 사전은 다음과 같이 초기화된다. 사전의 색인 번호는 정수값으로 주어지며, 1부터 시작한다고 하자. 색인 번호 1 2 3 ... 24 25 26 단어 A B C ... X Y Z 예를 들어 입력으로 KAKAO가 들어온다고 하자. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으..

문제 DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다. cache hit일 경우 실행시간은 1이다. cache miss일 경우 실행시간은 5이다. 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다. 문제조건 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다. cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다. cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다. 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어..

자바스크립트 엔진(Javascript Engine)이란? 자바스크립트 엔진은 자바스크립트 코드를 실행하게 해준다. 엔진은 웹 브라우저 내부 또는 Node.js 안에 구성되어 있다. 엔진의 주요 두 구성요소는 다음과 같다. Memory Heap : 자바스크립트에서 사용되는 메모리 공간. Call Stack : 코드 실행에 따라 호출 스택이 쌓이는 곳. 자바스크립트 엔진은 단 하나의 호출 스택을 사용한다. 가장 대표적인 자바스크립트 엔진으로는 구글에서 개발한 V8엔진이 있다. 이외에도 SpiderMonkey, Rhino, JavaScriptCore등이 존재한다. 자바스크립트 엔진 파이프라인 (Javascript Engine Pipeline) 자바스크립트 엔진은 전통적인 인터프리터일 수 있고, 특정한 방식으로..

프로세스는 동시에 실행될 수 있으며, 여러 개의 프로세스가 협력할 때는 프로세스 사이에 데이터가 동기화되지 않는 문제가 발생할 수 있다. 만약 두 프로세스가 동시에 어떤 변수의 값을 바꾼다면 프로그래머의 의도와는 다른 결과가 나올 것이다. 이처럼 프로세스가 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 경쟁 상태(race condition)라고 한다. 임계구역 (Critical Section) 코드상에서 경쟁 조건이 발생할 수 있는 특정 부분을 임계구역(critical section)이라고 부른다. 임계 구역은 둘 이상의 스레드가 동시에 접근해서는 안 되는 공유 자원이다. critical section problem를 해결하기 위해서는 몇가지 조건을 충족해야 한다. 1. 상호 ..

문제 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다. 위 초기 배치를 문자로 표시하면 아래와 같다. TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ 각 문자는 라이언(R), 무지(M), 어피치(A), ..

문제 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다. 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다. 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다. 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다. 제이지를 위해,..

기본 개념 CPU - I/O 버스트 사이클 (CPU - I/O Burst Cycle) 프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. 프로세스의 실행은 CPU Burst로 시작된다. 뒤이어 I/O Burst가 발생하고, 그 뒤를 이어 또 다른 CPU Burst가 발생하며, 이어 또 다른 I/O Burst 등등으로 진행된다. 결국 아래의 그림처럼 마지막 CPU Burst는 실행을 종료하기 위한 시스템 요청과 함께 끝난다. 선점/비선점 스케줄링 (Preemptive/Nonpreemptive Scheduling) CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생) 프로세스가 실행 상태에서 준비 완료 상태로 전환될..

문제 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다. 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실..