이미 끝난지 2주 지난 대회의 후기를 지금 올리는 이유는...울음소리로 힘차게 아침을 시작하면 재우면서 하루가 끝남. 아무튼... 이 대회가 뭔가 마침표가 될 것 같은 느낌이었는데 끝나고도 아직 식지 않는 걸 보니 아직 아닌 것 같다. 뭔가 더 멀리 있는 무언가에 도착해야 "다 했다." 싶을 듯. 여기까지 오게 된 과정을 정리해보고 싶어서 대회 후기를 남겨본다. 언젠가 흐릿해지면 아쉬울 기억인 것 같아서...0. 옛날 이야기더보기시간을 거슬러 2019년 여름. 대학원 5학기, 졸업을 앞둔 나는 지도교수님께 찾아가 논문 주제에 대해 여쭤보았다. 내가 생각한 논문 주제는 대강 '어디 고장난 게임을 디버깅하는 게임을 개발해 초등학생에게 적용하고 컴퓨팅 사고력 증진 효과를 검증'해보는 것이었다. 이게 당시에는 ..

시간 제한메모리 제한3초256MB문제(원문이 영어라서 gpt에게 번역 하청)Shagga와 Dolf는 검정색 또는 흰색으로 이루어진 돌로 게임을 하는 것을 좋아합니다. 게임이 시작되면, Dolf는 모든 돌을 왼쪽에서 오른쪽으로 한 줄로 배열합니다. 이제 Shagga의 목표는 모든 검은 돌이 모든 흰 돌의 왼쪽에 오도록 돌들의 순서를 재정렬하는 것입니다. 이를 위해, 그는 서로 다른 색의 돌 두 개를 선택하여 위치를 바꿀 수 있으며, 그 과정에서 Dolf에게 A개의 동전을 지불해야 합니다. 그러나 교환하려는 두 돌이 인접해 있으면, Dolf는 그에게 B개의 동전을 환급해 줍니다. 즉, 그 작업은 Shagga에게 A−B개의 동전만큼 비용이 듭니다.Shagga는 매우 똑똑하지 않아서, 이 게임을 통해 동전만 잃..

시간 제한메모리 제한1초128MB문제자동차 경주로는 의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다. 각 도로에는 의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 ..

1. 문자열의 효율적인 탐색 방법문자열 탐색의 가장 직관적인 방법은 직접 비교해보는 것이다. 한 글자씩 대조해보고 아니면 패스 하는 식. 그러나 이 탐색 방법은 한 가지 하자가 있는데 바로... 일대다 매칭(여러 후보 중에 특정 값과 매칭이 되는 값 찾기)에서는 답 없는 탐색 속도를 갖고 있다는 것. 문자열의 집합 S가 있다. 이 안에 어떤 문자열 T가 존재하는지 확인하고 싶다. S가 반 친구들 이름 정도의 규모라면 금방 확인 가능하겠지만 브리태니커 백과사전이라면? 하루 종일 찾아도 못찾을 수 있다. 문자열의 집합 S를 하나로 합쳐버릴 방법이 있다면 어떨까? S 안에 있는 무수한 문자들을 하나하나 대조하는 것이 아니라 하나로 합쳐진 S를 한번 훑어보는 것 만으로 T가 포함되는지 아닌지 확인 가능하다면? ..

시간 제한메모리 제한2초1024MB문제(본문이 러시아어이기 때문에 번역 결과만 간단히 요약함)1*n 크기의 필드가 주어졌을 때 k크기로 배를 배치하는 방법은 1*k 크기의 배를 1척, 1*(k - 1) 크기의 배를 2척, 1*(k  - 2) 크기의 배를 3척, ..., 1*2 크기의 배를 (k - 1)척, 1*1 크기의 배를 k척 띄우는 것이다. 배는 서로 겹쳐지거나 공백 없이 맞닿아 있을 수 없다. 주어진 필드 내에서 배치 가능한 최대 k를 출력하시오. 입력한 줄로 n이 주어지며 필드의 가로 칸 수를 나타내는 정수이다.(0 ≤ n ≤ 1e18) 출력조건에 맞춰 필드에 배치 가능한 최대 k를 출력하시오. 풀이식 세우기가 좀 까다로웠다.우선 배의 전체 길이만 더해보면 이런 식으로 정리된다.1 * k + 2..

1. 오토마타 이론문제를 해결하는 과정 중 한 시점을 "상태(state)"라고 하면 유한한 상태로 해결할 수 있는 문제들과 그렇지 않은 문제로 나눌 수 있다. 이 때 유한한 상태를 갖고 입력에 따라 한 상태에서 다른 상태로 전이되며 최초 상태(S0)에서 최종 상태(F)까지 이어져 출력을 내놓는 것을 유한 상태 기계(FSM, Finite-State Machine), 유한 오토마타(Automata)라고 부른다. 좀 더 쉽게 이해해보면 우리가 풀고 있는 거의 모든 PS의 문제들이 오토마타 문제로 분류될 수 있다. 오토마타는 순서도와도 매우 비슷하다. 순서도에서도 표현하는 방식이 있듯이 오토마타도 표현 방법이 정해져있다.M: 오토마타( M = {Q, ∑, δ, S0, F} )Q: 상태의 집합(Q ≠ { })∑:..

시간 제한메모리 제한1초128MB문제상근이는 서강 프로그래밍 대회의 문제를 준비해야 한다. 모든 문제의 난이도는 1과 N사이의 자연수로 표현할 수 있다. 하지만, 어떤 문제는 난이도를 정확하게 결정할 수 없는 경우도 있다. 따라서, 상근이는 문제의 난이도를 숫자 하나 또는 연속한 두 수로 표현하기로 했다. 예를 들어, 어떤 문제의 난이도는 3 또는 4가 될 수 있다. 올해 대회는 총 N문제가 필요하다. 상근이는 각 난이도에 해당하는 문제를 한 문제씩 내기로 했다. 당연하겠지만 같은 문제를 두 번 낼 수는 없다. 이때, 문제를 고르는 경우의 수를 구하는 프로그램을 작성하시오. 어떤 난이도에 해당하는 문제가 다른 경우에 두 방법이 서로 다른 경우이다. 정답이 매우 커질 수 있으므로 경우의 수를 1,000,0..

시간 제한메모리 제한1초512MB문제SASA의 자습 시간에는 매일마다 정독실, 소학습실, 휴게실, 그리고 방에서 휴식을 취할 수 있는 요양 4가지 중 하나를 선택할 수 있다. 우석이는 자습 장소에 따라 얻을 수 있는 만족도가 있으며, 그 4가지 값은 매일 우석이의 기분에 따라 결정된다. 우석이는 자습을 총 N일 동안 해야 하며, 기숙사에는 다음과 같은 규칙이 있다.요양 신청은 최대 A회 가능하다.휴게실에서 이틀 연속으로 자습을 할 경우, 게임을 하는 것으로 판단되어 퇴사 처리된다.정독실이나 소학습실에서 자습을 총 B회 미만으로 할 경우, 학습 의지 상실로 판단되어 퇴사 처리된다.공부하기 싫은 우석이가 퇴사를 당하지 않고 기숙사의 규칙을 지키면서 N일 동안 얻을 수 있는 만족도의 합의 최댓값을 구해보자.입..