아이단은 어디갔을까

순간 순간이 소중한 목적지

구글 코드잼 2019 QR 도전!

20대의 마지막으로 기본기를 탄탄히하자는 생각으로 알고리즘 공부를 진행해 왔다. 목표가 있으면 동기부여에 좋기때문에 구글코드잼을 도전해보았다. 올해 4월 7일에 진행된 Qualification Round는 다음 라운드로 통과할 수 있는 자격을 주는 테스트이다. 문제는 어렵지 않다. bfs, dfs, dp 등 문제만 읽어도 케이스가 좀 나뉘는 한국의 정형화된 코딩테스트에 비해 창의력이 필요한 문제가 좀더 많았다. 문제 하나당 3개의 테스트 케이스가 존재한다. normal case는 보통 자료의 크기가 적어 정확성 테스트가 진행돠며 통과할경우 6point를 얻게된다. hard case는 좀더 데이터 input의 크기가 크며 효율성을 증명하는 테스트이다 통과할경우 10point를 얻게된다. Continue reading

빅오 표기법(Big O notation)과 자바스크립트

오늘은 컴퓨터과학의 꽃, 알고리즘의 인트로에 늘 나오는 빅오표기법에 대해서 이야기해보고자한다! +_ + 대학생 때, 삼성SCSS 덕분에 컴퓨터과학을 늦게 접하면서 시립대에서 김진석 교수님 알고리즘 수업을 야간에 들었었는데 컴퓨터과학 전공자와 비전공자를 나누는 기준이 알고리즘이며 알고리즘의 효율성을 판별하는 빅오표기법은 매우 중요해요라고 콕 찦어 말하신게 기억에 남는다. 스타트업에 있을 때는 되게하는데 바빠 빅오표기법을 고민한 적이 없었고, 현업에 들어와서 게임프로그래밍을 하며 알고리즘의 효율성, 뎁스를 줄이기 위한 고민을 했을 뿐 정확하게 빅오표기법으로 얼마다하며 팀장님을 설득한 적이 없다. Continue reading

Golang 동시성을 활용한 알고리즘 문제풀이 - 1

파이프라인 패턴을 활용해서 알고리즘을 풀어보기로 했다. 알고리즘 문제: Google Code Jam 2016 qualification round A 궁금했던 점 동시성 프로그래밍으로 기존 알고리즘 모범답안보다 얼마나 퍼포먼스를 낼 수 있을까 많은 프로그래밍대회가 싱글쓰레드기반으로 동작해 정답이 순차적으로 나와야한다. 하지만 멀티쓰레드 프로그래밍은 Case #1번이 아니라 Case #5번이 먼저 풀릴 수 있다. (사실 구글 코드잼의 가장 큰 난적은 문제가 영어라는 점이다) 문제요약 Bleatrix Trotter 이라는 여자분은 불면증에 걸린거 같다. 이 여자분은 잠에 골아떨어지기위해 특별한 전략이 있다. Continue reading