qjatn0120

강의 내용[강의 노트]DP의 기초적인 내용들과 약간의 응용들을 다루었다.피보나치 수열의 다양한 구현 (top down, bottom up)으로 dp에 대한 기본 구현을 강의하고,LIS등 어려운 dp 문제 맛보기도 살짝 하였다.이후 피보나치 N번째 항 logN에 구하기 등 행렬의 분할 정복을 이용하는 테크닉도 소개하였다. 강의 과제피보나치는 $F_n = F_{n-1} + F_{n-2}$라는 매우 간단한 수식으로 이루어진 dp이다.따라서 이번 과제는 여기서 항 하나만 더 추가한 $F_n = F_{n-1} + F_{n-2} + F_{n-3}$ 이라는 수식에서 시작해서 살짝씩 변형해가며 3개의 과제 문제를 만들었다. A. 돌다리도 두드려보고 건너야 한다 (Easy)[문제] [정답 코드]$N$개의 돌로 이루어진 ..

1. 개요 지난 일지에서는 Online Judge 사이트를 AWS 무료 티어 계정을 이용해서 열어보았다. 이번에는 사이트가 터지지 않도록 어떻게 관리하는 지에 대해서 써보려 한다. 2. 무료는 이유가 있다 일단 무료로 제공하는 건 다 이유가 있는 듯 하다. 그냥 모든 게 딸린다. 모든 부분이 딸려서 하나라도 터진다면 채점 사이트 자체가 먹통이 되버리는 문제가 있다. 따라서 어떤 문제들이 지금까지 발생했고, 어떻게 대처했는 지에 대해서 적어보려고 한다. 2-1. Memory Limit Error (진짜 에러임) 백준에서 보통 문제 당 메모리 제한을 256MB 정도로 둔다. 하지만 우리 나약한 서버는 256MB로 두면 돌아오지 못할 강을 건너고 만다. 메모리 제한을 너무 크게 두면 제출 하나만 해도 제출 코..

1. [문제해결 실습 및 응용] 수업 강사 작년 여름부터 학교 측의 제안으로 "문제해결 실습 및 응용" 수업의 강사를 맡고 있다. 따라서 작년 2학기와 올해 1학기, 이 수업의 강사로써 매 주 1회, 약 2시간씩 강의를 진행하고 있다. 이론위주의 수업 보다는 코딩 및 알고리즘 구현 위주로 수업을 진행하고 있다. 맨 처음에는 교수님이 하는 수업 강의를 내가 직접 한다는 점이 뭔가 신기했지만, 이번에는 벌써 2번째라 편안한 마음으로 강의를 진행하고 있다. PS쪽 현역에서 뛰고 물러난 지 약 2년 정도 지났지만, 이 수업은 학부생들 1, 2학년들을 대상으로 진행하는 수업이라 아무리 감이 다 죽었어도 수업을 진행할 정도의 능력은 아직 유지하고 있다. 2. 왜 갑자기 글을 쓰는가 이 수업은 1학점짜리 수업이기 때..

A. We Need the Zero code 길이가 \(N\)인 배열이 주어진다. 이제 이 배열의 모든 값에 특정 \(x\)를 XOR해서 배열의 모든 원소를 XOR한 값이 0이 될 수 있는지 확인하고 싶다. 가능하면 XOR 결과가 0이 되도록 하는 \(x\)를, 불가능하면 -1을 출력해야 한다. XOR을 많이 다뤘다면 빠르게 풀 수 있는 문제이다. XOR의 가장 큰 특징은 \(a \oplus x \oplus x = a\)라는 점이다. 일단 처음 주어진 배열의 모든 원소의 XOR값을 \(A\)라 하고, 모든 원소에 \(x\)를 XOR하자. 만약 \(N\)이 짝수라면 모든 원소의 XOR값은 여전히 \(A\)일거고, \(N\)이 홀수라면 XOR값은 \(A \oplus x\)가 될 것이다. 따라서 \(N\)이 ..

들어가기에 앞서 올 해부터 대학원 생활을 시작했는데, 아무래도 밤 늦게 있는 코포를 치면 시간표가 망가지게 된다... 그래서 학기 중 평일 밤 늦게 있는 코포는 거의 안칠 것 같다. A. Alternately code H와 F로 이루어진 문자열이 주어진다. 이웃하는 두 문자가 같은 경우가 있으면 No, 아니면 Yes를 출력하면 된다. 단순 for문 문제이다. B. Chessboard code 8x8 체스판에 말이 딱 하나 존재한다. 말이 없는 칸은 점(.), 있는 칸은 별(*)로 주어진다. 말의 위치를 A4, D5와 같은 형식으로 출력해야 한다. 행과 열 번호를 구하고, 이에 대응하는 알파벳 + 숫자 조합을 출력하면 된다. C. Gap Existence code 길이가 \(N\)인 정수 배열이 주어진다...

A. Garland code 색깔이 있는 전구가 4개 주어진다. 4개의 전구는 모두 꺼져있다. 각 전구의 색깔은 0이상 9이하의 정수로 표현된다. 이제 4개의 전구를 하나씩 스위치(킨 전구를 끄거나 꺼져있는 전구를 키는 것)해서 모두 킬 것이다. 그런데 연속해서 같은 색깔의 전구를 스위치할 수는 없다. 최소 몇 번의 스위치를 해야 모든 전구를 킬 수 있는지 출력하면 된다. 만약 모든 전구를 킬 수 없으면 -1을 출력하면 된다. 일단 모든 전구의 색깔이 같으면 모든 전구를 킬 수 없다. 만약 세 전구의 색깔이 똑같고 나머지 하나가 다르다면, 총 6번 스위치를 해야 모든 전구를 킬 수 있다. 그 이외의 경우에는 4번의 스위치만으로도 모든 전구를 킬 수 있다. 따라서 모든 전구의 색깔이 같으면 -1, 세 전구..

처음으로 codechef에 가입하고 대회를 쳐보았다. 처음에는 Div 4.에서 치라길래 싱글벙글 빨리풀고 잘 생각으로 쳤는데, 생각보다 오래걸렸다;; 시간 남으면 Div 4. 이외의 문제들도 풀어보려고 했는데, 한 문제에서 너무 시간을 많이 잡아먹어서 Div 4. 문제만 푸는 선에서 마쳤다. Candy Division code \(N\)을 입력받아 3으로 나눈 나머지가 0이면 YES, 아니면 NO를 출력하라는 문제이다. 그냥 하면 된다. Reach Home code \(x, y\)를 입력받아 \(5x \ge y\)이면 YES, 아니면 NO를 출력하라는 문제이다. 역시 그냥 하면 된다. Min To Max code 길이가 \(N\)인 배열 \(A\)가 주어진다. \(A\)의 minimum 값을 \(M\)이..

A. Plus or Minus code \(a\), \(b\), \(c\)가 주어진다. \(a + b = c\) 또는 \(a - b = c\)를 만족한다. 둘 중 어느것을 만족하는 지 출력하면 된다. 문제에서 시키는대로 하면 된다. B. Grab the Candies code \(N\)개의 가방이 있고, \(i\)번째 가방에는 \(a_i\)개의 사탕이 있다. 이제 가방을 특정한 순서대로 열 것이다. 만약 가방에 짝수 개의 사탕이 있다면, Mihai가 그 가방에 있는 사탕을 모두 가진다. 반대의 경우에는 Bianca가 모두 가져간다. 이제 가방을 여는 순서를 잘 배열해서 처음부터 모든 가방을 열 때까지 항상 Mihai가 Bianca보다 사탕을 많이 가지고 있도록 하게 하고 싶다. 가능하면 Yes, 불가능하..

항상 앳코더랑 코포는 계속 참가했는데 풀이를 쓰는 게 귀찮아서 계속 블로그를 방치하고 있었다. 너무 블로그를 방치하는 거 같아서 이제부터 대회 이후 간단히라도 쓰려고 한다. A. Filter code 길이가 \(N\)인 배열을 입력받은 뒤 짝수인 원소만 출력하면 되는 문제이다. 문제에서 시키는대로 하면 된다. B. ASCII Art code \(H\times W\)크기의 정수 배열을 입력받는다. 각 배열은 0이상 26 이하의 정수이다. 각 정수 \(x\)를 \(x\)번째 대문자 알파벳으로 치환하여 출력하고, \(x\)가 0이면 마침표로 치환하려 출력하면 된다. 역시 문제에서 시키는대로 하면 된다. C. Merge Sequences code 길이가 \(N\), \(M\)인 두 배열 \(A\), \(B\)가..

A. Medium Number code 문제 설명 3개의 수를 입력받아 중앙값을 출력해야 한다. 알고리즘 세 수를 정렬하고, 2번째 숫자를 출력하였다. B. Atilla's Favorite Problem code 문제 설명 주어진 문자열을 적을 때, 1번째 알파벳인 a부터 몇 번째 알파벳까지 사용해야 하는지를 출력해야 한다. 알고리즘 문자열 \(s\)에 있는 모든 문자 \(c\)에 대해 \(c - 'a' + 1\)의 최댓값을 출력하면 된다. C. Advantage code 문제 설명 길이가 \(n\)이고 각 원소가 정수인 배열이 주어진다. 모든 원소에 대해 자신에서 자신을 제외한 값들 중 최대인 값을 뺀 결과를 구해 출력해야 한다. 알고리즘 먼저 최댓값을 가지는 원소를 하나 찾는다. 해당 원소를 제외한 ..