파일명 정렬 문제 소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다. 파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다. HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다. NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다. TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다. 파일명을 세 부분으로 나눈 후, 다음 기준..

압축 문제 LZW 압축은 다음 과정을 거친다. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다. 단계 2로 돌아간다. 주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라. 제한사항 입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1 글자 이상, 1000 글자 이하이다. 풀이 처음에는 재귀로 구현했다가 너무 느려서 반복문으로 바꿨다. 사전에 존재하는 가장 긴 배열을 찾는다. (w) 나머지 글자 한 개를 더한 값을 사전에 등록한다. (w + ..

방금그곡 문제 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라. 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다. 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다. 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다. 음악이 00:00를 넘겨서까지 재생되는 일은 없다. 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간..

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

네트워크 보안 Confidentially : 메시지를 교환할 때 해당 내용을 다른 사람이 확인할 수 없어야 함 authentication: 내가 메시지를 주고 받는 상대방에 대한 검증 message intergrity: 메시지 내용이 변하지 말아야함 access and avaiablity 대칭키 = 개인키 암호화 (Symmetric Key, Private key) 암호화와 복호화에 같은 암호키를 사용하는 알고리즘이다. 장점 동일한 키를 주고 받기 때문에 매우 빠르다. 단점 대칭키 전달 과정에서 해킹 위험에 노출 될 수 있다. 사용자의 증가에 따라 관리해야할 키의 수가 상대적으로 많아진다. 공개키 (Public key) 암호와 복호화에 사용되는 암호키를 분리한 알고리즘이다. 자신이 가지고 있는 개인키로만 ..

프렌즈4블록 문제 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라. 제한 사항 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다. 2 ≦ n, m ≦ 30 board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다. 풀이 제거할 블럭 묶음 찾기 BFS를 하면서 어떤 (i, j)가 왼쪽 위에 위치하는 2x2 묶음이 있는지 확인한다. 있다면 출발점을 제외한 나머지 3개 블럭을 큐에 넣는다. 지워야하는 블럭들은 모두 checked에 넣어서 반환해줬다. 블럭 내리기 행, 열을 바꿔서 0을 제거한 후 앞에 빈 공간만큼 0을 채워서 다시 리스트로 바꾸고 행, 열도 바꿔줬다. 한 턴을 진행할 때..

교착 상태 (Dead Lock) 교착 상태란 2개 이상의 프로세스들이 서로의 자원을 얻지 못해서 진행할 수 없는 상황을 말한다. 프로세스에게 한정된 자원이 할당되었을 때 프로세스들의 자원 부족으로 더 이상 실행할 수도 없으며, 종료 후에 다른 작업을 시작하는 것도 불가능한 상태를 말한다. block된 프로세스들은 각각의 자원을 가지고 다른 프로세스가 점유한 자원을 얻기를 기다리고 있는 상태이다. 두 프로세스는 무한정 wait 상태에 빠지게 된다. 자원은 한 번에 하나의 프로세스에 의해서만 사용될 수 있고 non preemtable resource로 선점 불가능 하기 때문에 일반적으로 데드락이 발생한다. 데드락 발생 조건 하나라도 만족하지 않으면 데드락은 해결된다. 상호 배제 Mutal exclusion ..

프로세스 동기화 멀티 쓰레드 프로그램에서 쓰레드들은 자원을 공유하며 협력한다. 이때 공유 자원 접근 시에 동기화가 보장되지 않으면 Race condition이 발생할 수 있고 부정확한 결과로 이어진다. 이를 방지하기 위한 방법을 동기화라고 한다. 동기화라는 것은 공유 자원을 어떠한 프로세스가 사용하고 있을 경우 값이 반환되기 전까지 blocking 하는 것을 말한다. 즉, Critical section에 대한 상호 배제를 제공해 race condition을 회피하는 방법이다. Race condition 쓰레드에 의해서 공유 자원에 접근한 결과가 스케줄러에 의한 접근 타이밍에 의존해 결정되는 상태이다. 결과를 예측할 수 없고 싱글 프로세스이든 멀티 프로세스이든 발생할 수 있다. 임계 구역 문제 (Criti..