[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

위키피디아 : 아호-코라식 알고리즘

여러 개의 패턴 검색할 때 선형시간에 패턴을 검색하게 해 주는 알고리즘입니다. IDE에서 색깔 입혀줄 때 사용할 것으로 강력하게 추정되네요.

패턴 하나는 KMP로 선형에 되는데 패턴 여러 개 있을 때 어떻게 하나 항상 궁금했었는데 이런 알고리즘이 존재하는군요.

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

메아리
한글날을 맞아 아희에 관련된 얘기가 돌길래 여기 들어가서 이것저것 구경하고 있었는데 알고 보니 경기과학고 선배였다(!)

사이트에 올라와 있는 숏코딩이라던지 난해한 프로그래밍 코드들 보고 있으면 대략 정신이 멍해진다.

지금은 저널 읽어보는 중인데 한 번쯤 생각해 볼만한 글들이 많은 것 같다. 푸붉님한테 처음 들었던 CSON 얘기도 있었다. 읽다 보면 연륜이랄까 경험이랄까 이런 게 느껴지는 것 같다.

C++로는 문제 푸는 것밖에 할 줄 몰라서 이런 분들 볼 때마다 C++이나 다른 언어를 제대로 배워보고 싶은 마음이 들기도 한다. 플래시도 충분히 좋은 플랫폼이라고 생각하지만 보안 관련 이슈 때문인지 AIR를 사용하더라도 불가능한 저수준 제어가 많기 때문에 이런 저수준 제어 쪽을 보면 흥미롭다. 근데 또 한편으로는 내가 만들고 싶어 하는 쪽은 게임이나 웹사이트 등 딱히 저수준 제어가 필요하지 않은 것들이라 굳이 배울 필요성을 느끼지 못하기도 한다.

음… 그래서 결론은 숙제랑 시험공부를 해야 한다는 것일 듯.

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

PMP 검색하다가 화가 나서 쓰다 보니 굉장히 장문의 글이 되었다.
엄청 길어서 몇 안 읽을듯.

요약
학습실에서의 스마트폰 전면 금지는 현재 학생들의 학습 실태를 전혀 고려하지 않고 만들어진 법으로 제정 원인과 해결책 모두 말도 안 된다. 꼭 폐지시키고 말겠다. 학생들 학습 효율을 올리고 싶다면 스마트폰 문제로 멀쩡히 잘 사용하는 학생들 피해주지 말고 수면 시간 늘리고 운동장 점호나 폐지하는게 좋을 것 같다.

==

우리 학교의 많은 학생들이 그렇듯이 나는 학습실에서 핸드폰으로 공학용 계산기 쓰고, PDF 뷰어로 솔루션이나 교재 보고, 음악 듣고 하면서 굉장히 편하고 유익하게 스마트폰을 사용하고 있었기 때문에 이번 스마트폰 사용 전면 금지에 대해 굉장히 불만이 많다.

사실 나는 학습실에서 공부하다가 머리 식히려고 잠깐 게임을 했다가 다시 공부를 하는 것도 위에 서술한 ‘유익한 사용’에 포함된다고 생각한다. 하지만 학습실에서의 게임을 허용해준다면 분명히 게임만 하는 애들이 나오고 더 큰 문제를 유발할 것이라고 예상되기에 그 정도까지는 주장하지 못하지만 애들이 학습실에서 스마트폰으로 게임을 한다는 이유만으로 음악을 듣거나 솔루션을 보는 것까지 금지당해야 한다는 학교 측의 주장에 대해서는 전혀 공감할 수가 없다.

학습실에서 공부하지 않고 게임만 하는 학생들을 구제한다는 명목으로 이런 법을 시행하고 있는데, 의도는 좋은데 왜 그것을 위해 멀쩡하게 잘 공부하는 학생들까지 피해를 봐야 하는지 모르겠다.

사람마다 자기에게 적합한 공부 방식은 다양한데, 학교에서 제정한 법안이 시행된다면 이런 다양한 공부 방식들 중 일부를 차별하게 된다. 학습실에서 게임을 하는 건 학습 행위가 아니니 처벌 대상이지만, 음악을 듣거나 솔루션을 보는걸 금지한다는건 개인의 학습 습관에 대한 학교의 차별이라고까지 생각된다.

이러한 주장에 대해서 선생님께서는 ‘우리 공부할 때는 스마트폰이고 뭐고 없었다. 학습에 스마트폰이 필수는 아니다. 꼭 필요한 경우 노트북 사용실에서 사용하라’는 답변을 하고 있지만 이는 문제의 본질을 이해하지 못하기 때문에 나오는 답변이다. 물론 공부야 할 수 있겠지만 공부의 효율과 질이 떨어지는 문제에 대해 이야기 하고 있는데, 단순히 차선책이 있으니까 아무런 문제가 없다는 논리에는 문제가 있다.

차선책이 있으니까 아무런 문제가 없다는 것은 카드 사용을 금지하고 현금을 들고 다니면 된다거나, 선풍기 사용을 금지하고 부채를 쓰라고 하거나, 마우스 사용을 금지하고 터치 패드를 쓰면 된다는 논리와 별로 다를 게 없다. 과학자 기술자들이 열심히 발전 시킨 기술이 있는데 왜 편한 길을 놔두고 불편하게 살아야 하는지 모르겠다.

또한 노트북 사용실에서 공부하라는건 현재 노트북 사용실의 사용 실태를 전혀 이해하지 못하고 하는 소리다.

  1. 노트북 사용실까지 이동하는데 2분 정도 걸린다. 짐 챙기는데 걸리는 시간 포함하면 더 늘어나는데 이동할 때마다 시간을 소모하게 된다. 또한 이동 후 다시 집중 상태에 들어가는데 걸리는 시간까지 고려하면 더더욱 늘어난다.
  2. 노트북 사용실은 보통 대회 준비하거나 발표 준비할 때 등 여러 명의 논의하면서 컴퓨터 작업을 하기 위해 사용되는데, 노트북으로 숙제하거나 이럴 때는 어느 정도 괜찮지만 집중력이 많이 요구되는 작업의 경우 꽤나 방해가 된다. 하지만 이건 노트북 사용실의 컨셉 자체가 이런 것이기 때문에 학습실에서처럼 논의하는것 자체가 문제가 되는 것은 아니기 때문에 단순히 조용히 해달라고 부탁 할 수는 없다.
  3. 노트북 사용실은 한 차시만 쓸 수 있게 제한되어 있다. 또한 각 차시 시작과 끝에 이동 금지 시간이 있는데 만약 사용하려면 이 이동 금지 시간을 피해서 해야 하기 때문에 솔루션을 봐야 할 때 바로 사용할 수 없으며 불필요하게 시간을 낭비하게 된다.
  4. 노트북 사용실은 전교생의 1/4도 수용하지 못한다.

학습실에서 음악을 듣는 것에 대해서는 ‘와이파이가 되지 않는 MP3를 사서 써라. 요즘 얼마 하지도 않던데’라고 얘기하셨는데, 왜 학교가 만든 멍청한 법안 때문에 돈을 써야 되는지도 모르겠고 스마트폰이랑 MP3랑 둘 다 관리하기 굉장히 불편하다. 또한 솔루션 보는건 여전히 노트북 사용실에서 해야 한다. 사실 MP3, PMP 검색하다가 갑자기 화나서 이 글을 쓰게 됐다<<

위에서 서술했듯이 법안 자체에 문제가 있기도 하지만, 이런 법안을 시행하게 된 논지 자체에도 반박할 거리가 있다.

학습실 스마트폰 금지의 논지는 다음과 같다.
1학기때부터 솔루션 보기, 음악 듣기 이외의 스마트폰 사용은 금지되어 있었고, 사용 빈도가 높아진다면 처벌을 강화한다는 이야기를 계속해서 했었다. 시간이 지나면서 점점 잘못된 사용이 많아졌으며, 학생들의 자정작용을 보여주기를 기대했지만 자정작용도 제대로 이루어지지 않았다. 또한 게임 등을 하다가 걸리더라도 다른 화면을 틀어 놓고 발뺌하는 경우도 많다.

여기서 문제가 되는 점은 크게 두 가지이다. 자정작용이 제대로 이루어지지 않았다는 점과, 점점 잘못된 사용의 빈도가 늘어났다는 점이다.

자정작용 같은 경우 1학기 때 선생님께서 제시하신 자정작용의 경우 ‘학습실 분위기가 좋지 않을 때 스스로 학생들끼리 학습하는 분위기를 만들 수 있도록 하라’였다. 나는 이 부분은 지켜졌다고 생각한다. 잡담을 해서 공부에 방해가 될 때 정중하게 요청하면 거절하는 경우는 없었다.

약간의 잡담이 있더라도 크게 방해가 되지 않거나, 아니면 공부에 관한 질문이라 옆에서 듣는 것으로 학습에 도움이 되기 때문에 이야기 하지 않은 경우임에도 단순히 이야기를 하고 있고, 주변 사람들이 말을 하지 않았다는 이유만으로 자정작용이 이루어지지 않았다고 판단하는 경우가 있는 것 같다.

또한 선생님과 내가 이해했던 자정작용의 범위가 다른 것도 있다. 자정작용의 범위는 ‘주변에 잡담을 하느라 시끄러우면 서로 이야기를 해서 조용히 할 수 있도록 하라’였지만 선생님께서는 ‘옆 친구가 게임을 하고 있으면 못 하게 해라’도 포함되었던 것 같다.

하지만 이것까지 학생들에게 요구하는 것은 약간 무리가 아닌가 생각한다. 옆에서 게임하는게 나에게 방해도 되지 않고, 내가 게임을 하지 못하게 할 권한도 없는데 왜 내가 나서서 그런 것까지 막아야 하냐는 생각이 크다. 이 부분에 대해서 ‘나만 잘 되면 된다’는 식의 논리냐고 얘기하셨었지만, 이건 자정작용 보다는 오지랖에 가깝다고 생각한다.

에스컬레이터 두 줄 서기가 이것과 굉장히 유사한 경우라고 생각한다. 두 줄 서기를 하는게 맞다고 알고는 있지만, 두 줄 서기를 하지 않고 걸어 내려가는 사람들이 굳이 내가 에스컬레이터 타는데 피해를 주는 것도 아니고(두 줄 서기하고 있는데 비키라고 하는 경우가 아니라면), 내가 그 사람에게 명령할 권한도 없고 하니 걸어 내려가는 사람들을 무시하는 경우가 많다. 에스컬레이터 두 줄 서기나 주변에 게임하는 친구가 있을 때 아무 말도 하지 않는 것은 굉장히 유사한 심리적 판단이 작용하는 것이라고 생각한다.

애들이 게임하다 화면 바꿔 놓고 거짓말해서 잡기 힘들다는 고충은 충분히 이해하지만, 그건 거짓말 했을 때 처벌을 강화하던가 해서 잡아야지 이런 방식의 전체적인 통제로 해결하는건 아니라고 생각한다. 자동차에 비유하면 ‘음주 단속을 하는데 음주운전 때문에 교통 사고가 늘어난다. 단속할때도 자꾸 술 마시고 안 마셨다고 거짓말 하는 사람이 많아서 힘들다. 교통 사고를 해결하기 위해 자동차를 모두 없애겠다.’ 이런 느낌이랄까.

아청법과 게임 셧다운제가 빈대 잡겠다고 초가삼간 태우는 법으로 유명한데, 이번에 제정되는 법도 비슷한 것 같다.

잘못된 사용의 빈도가 늘어났다는 것도 그렇다. 학기 아주 초반에는 학습실도 생기고 2학년이니까 열심히 해보자는 마음이 좀 있어서 어느 정도 사용이 적었던 것은 사실이지만 1학기 중간고사 이후 정도부터 걸리는 학생이 늘어났고, 나는 그 때부터 그 사용량이 쭉 유지됐다고 느꼈는데 선생님 입장에서는 그렇지 않았나보다.

방학 계절학기 때 학습실 분위기가 많이 좋지 않았던 것에 대해서는 동의한다. 하지만 그건 점점 나빠지다가 방학 때 정점을 찍은게 아니라 그럭저럭 유지되다가 방학 때니까 사용량이 늘어난 것이지, 점점 공부 안 하는 애들이 늘어난게 아니라는 것이다. 오히려 방학 때와 2학기를 비교해보면 2학기 학습 분위기가 정말 당연하지만 훨씬 좋다.

애초에 분위기가 좋다 나쁘다는 정말 주관적인 의견이기 때문에 오히려 일주일당 스마트폰 게임을 하다가 걸린 횟수 등의 통계를 통해 말했다면 설득력이 있었겠지만 학생들 사이에서도 점점 나빠진다 아니다 의견이 나뉘고 있다. 이것도 주관적인 생각이지만 나는 아침 조회때마다 스마트폰 좀 쓰지 말라고 말했기 때문에 그냥 그런가보다하고 받아들인 학생들이 많다고 생각한다. 주관적인 생각에서 의견이 갈리는 경우라면 어떤 것이 맞는지 객관적인 통계 등을 이용해 검증하는 과정이 있어야 하는데 이런 과정이 전혀 포함되어 있지 않았다.

지금 제정되려고 하는 법안에는 정말 문제점이 많다고 생각한다. 지금까지도 학교의 학습실 통제에 대해서 굉장히 불만이 많았지만, 그건 우리 학교에서 정보올림피아드 공부를 하거나 아니면 내 공부 방법이 남들과는 다르게 유난히 컴퓨터를 많이 사용하는 등 마이너한 공부 방법을 사용하는 개인적인 문제였기 때문에 개인적인 해결 방법을 찾아왔다.

하지만 이번 법안은 다르다. 학습하면서 음악을 듣거나 솔루션을 보는 것까지 금지한다는 것은 상당히 메이저한 공부 방법임에도 불구하고 지금 금지되려고 하고 있다. 학생들은 스마트폰 사용할 수 있는 인권이 있다는 등의 이런 문제가 생기면 꼭 학생 측에서 들이미는 인권 문제를 굳이 꺼내지 않더라도, 이 법안이 당장 다음주부터 시행되게 된다면 많은 학생들이 학습에 치명적인 피해를 입을 것이라 예상된다.

뭐 우스갯소리긴 하지만 이 글 쓰면서 나도 공부할 시간에 PMP 찾다가 글 쓰느라 오늘의 학습에 피해를 입었다. 법안이 시행되기도 전에도 이렇게 피해를 입는 학생이 나오고 있는데, 시행된 이후는 어떻겠는가!

K모군이 말한 것처럼 이런 메이저한 문제임에도 나서는 학생이 정말 적다는게 의아하다. 예상하기로는 전처럼 음악 듣고 솔루션 보고 하다가 걸리고 스마트폰 뺏기고 나서 학교 욕하는 사람이 많을 것 같지만 이런 수동적인 자세를 취해서는 안 된다. 학생들의 의견을 모아 꼭 이 법안을 폐지시키고 말겠다.

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

화폐개혁

전국대회 예비소집 전 자기 전에 연습삼아 한 문제를 풀고 자려고 ‘화폐 개혁’이라는 문제를 선택했음.

열심히 풀다가 너무 안 풀려서 풀이를 보기로 했음.

T[i]를 ‘i를 최대 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 아래서부터 에라토스테네스의 체 방식을 이용하여 배수를 채워 나가는 Bottom-Up 방식과, T[i]를 ‘i를 최소 화폐로 사용할 때 사용하는 화폐의 수’로 정의해서 max값부터 내려오면서 그 값의 약수들을 채워나가는 Top-Down 방식의 풀이가 있었는데 Bottom-Up 방식은 글과 코드가, Top-Down 방식은 코드만 첨부되어 있었음.

Bottom-Up 방식도 잘 보면 이해할 수 있었을 것 같은데 첨부된 글이 너무 못 알아듣게 써 있어서 Top-Down 방식 코드를 보고 있었고, 마침 그 방식대로 짠 친구가 있어서 설명을 듣고 그대로 짰음. 처음에 풀이를 봤을 때는 저게 Bottom-Up 방식인지도 못 알아들었었음.

처음에는 Top-Down 방식으로 짰는데 전처리를 안 하고 그냥 \sqrt{M}까지 루프를 돌렸기 때문에 최초에는 O(MN \sqrt{M}) 정도의 시간복잡도로 마지막 테스트 케이스에서 TLE.

그래서 전처리를 이용해 소인수분해를 미리 해 두고, 계산할 때는 소수들을 이용해 약수를 직접 구하는 방식으로 코드를 고쳤지만 이번에도 마지막 테스트 케이스에서 TLE.

Top-Down 방식은 에라토스테네스를 이용하는 Bottom-Up 방식과는 다르게 약수를 구하는 과정에서 어쩔 수 없는 낭비가 생긴다는 것을 깨닫고, Bottom-Up 방식으로 다시 짜기로 함.

Bottom-Up 방식에서는 에라토스테네스 방식을 사용해서 시간복잡도가 O(MN lglg M)이 보장되기 때문에 훨씬 빠를 것이라 예측하고, 다시 짰으나 결과는 별반 다르지 않았음. 심지어 더 앞쪽에서 TLE.

뭐가 문제일까 생각하다가, 설마 아니겠지 생각하면서도 나눗셈 연산과 퍼센트 연산이 느려서 그런게 아닐까 생각하게 됨.
a/i-(a/j+a%j/i) 이 부분을 a/i/(j/i)*(j/i-1)로 고치고 j가 i의 배수라는 사실을 이용해 a/j*(j/i-1)로 고쳐서 겨우겨우 AC.

나눗셈 연산과 나머지 연산 좀 줄인걸로 속도가 세 배이상 빨라졌음. 생각한 것 보다 나눗셈과 나머지 연산이 많이 느리다는것을 느끼는 계기가 되었음.

문제 자체는 평소에 잘 접하지 못하는 새로운 형태의 dp라서 좋았던 것 같음. T[i] 정의와 dp라는것만 떠올렸으면 스스로 풀 수 있었을 것 같은데 워낙 생소한 형태의 문제라 좀 고생했던 것 같음.

전국대회에서 좋은 결과 있으면 좋겠네요.