바쁘지 않은데, 바쁘다.

블로그에 글을 4달만에 올려본다.요즘 회사 일 때문에 바쁘다고 말하곤 하는데,사실은 열정이 식은것이 아닐까? 그렇다고 열심히 놀았던 것도 아니다.쉬면 뒤쳐지는 것 같아서하루도 제대로 논 적이 없던 것 같다.(아, 물론 데이트는 빼자) 어쨌든 공부하는 것도 아니고 노는 것도 아닌 주말을 계속 보내다보니'일단 오늘은 실컷 놀아보자!'라는 생각에모든 걸 내려두고 만화카페에 가서 4시간을 선불로 긁었다. 처음 2시간은 약간 불안불안 했는데,놀다보니 재밌어서 거의 5시간이나 있다가 나왔다. 그러다 집에 오는 길에오랜만에 연락온 후배가 문제(PS)에 대해 물어봤다.덕분에 한참 들어가지 않던 Slack도 들어가보고조언 아닌 조언을 한 뒤 정말 오랜만에 문제를 풀어봤다. 언제쯤 다시 시작할 수 있을까? - 새벽에 쓰는..
Diary/2018 2018. 4. 9. 01:19

Codeforces Round #443 (Div. 1) A. Short Program

Codeforces Round #443 (Div. 1) A. Short Program 나는 왜 이런문제를 못푸는지 모르겠다.하... 이 코포셋이 나온지는 6주나 지났는데,요즘 한 두달간 뻘짓만 하다가 다시 정신차리고 문제를 풀기 시작했다. 일단 이 문제는 xor, and, or 연산을 하는데,문제에서 주어지는 최대 50만개의 연산을 진행한 뒤이 값과 똑같은 값을 출력하는 5개 이하의 XOR, AND, OR 연산 조합을 출력해야한다. 이 문제의 핵심은 다음과 같다.1. 0과 AND 연산을 한다면 반드시 0이 출력되어야 한다.2. 1과 OR 연산을 한다면 반드시 1이 출력되어야 한다.3. 임의의 x번째 비트가 AND와 OR연산의 영향을 받지 않을 때에만 XOR 연산의 영향을 받는다. 이 3가지만 고려하면 문..
PS - OJ/Codeforces 2017. 12. 10. 17:17

Dinic - Network Flow (Maximum Flow)

오늘 드디어 디닉 알고리즘을 정복했다. 작년 입사시험 보기전에서티 기출로 네트워크 플로우 문제가 나왔다고 해서디닉까지 준비해서 가려고 했었는데,그때부터 지금까지 준비한다고 말만하다가 1년도 더 지난 오늘에서야 공부하게 됐다 ㅠ 시간복잡도는 O(V^2 E)이지만 이것보다 훨씬 빨리 동작하며, 거의 O(VE)로 봐도 무방할만큼의 속도를 보여준다.사실상 PS문제에서 Network Flow문제가 제한에 대해 최악의 경우까지 가도록 테케를 만드는건 거의 불가능(?)하기 때문에... 아무튼 생각보다 훨씬 쉬웠다.역시 지금까지 공부한 알고리즘 중에서 LCP가 제일 익히기 까다로웠는데,그에 비하면 디닉은 아주 쉬웠다. 간단하게 말하자면 bfs돌면서 정점들의 level을 체크해주고,level체크가 완료되면 network..
Algorithm/Network Flow 2017. 11. 26. 22:25

예전보다 구현실력이 좀 괜찮아진 것 같다. (제목 수정함 ..)

어후 이거 제목이 왜이랩..ㅠ.ㅠ역시 자기전에 글 쓰면 안되는 것 같다. 원래 제목: 이제 무엇이든 코드로 구현하는데 큰 어려움은 없는 것 같다.PS에만 국한된 얘기는 아니다.나는 코딩능력이 생각하는 능력과 구현능력으로 나뉜다고 생각한다. 코딩력 = 생각 + 구현 여기서 과연 연습한다고 좋아질 수 있는지 의문이 드는 부분이 바로 생각하는 부분이다.이 부분은 아직도 잘 모르겠다.물론 옛날에 비하면 많이 늘었지만, 그 속도가 너무 더디다. 구현은 진짜 정말 많이 늘었다고 말할 수 있다.생각을 못해서 그렇지 누가 생각만 해주면 꽤 괜찮은 시간 안에 무엇이든 구현을 할 수 있는 것 같다. 요즘은 논문을 자주 보고 있는데,논문에서 추상적으로 설명하는 것들을 코드로 옮겨보고 있다.신기한건 나 스스로에게 어떤것이든 ..
Diary/2017 2017. 11. 7. 23:16

서티 합격했다고 연락주신 분들~ 감사합니다.

제가 뭐라고..감사하다고 연락주신 분들, 오히려 제가 감사합니다 블로그를 시작하게 된건원래 좀 떠벌리기 좋아하고페북에 적긴 좀 그런 글들을일기처럼 끄적이고 싶어서 시작했는데, 몇몇 분들이 도움이 됐다고 말씀해주시니황송하기 그지없네요... 헤헿헿ㅎㅎ^^;; 항상 제가 쓰는 글은다음 날만 봐도참 사람이 아직 철도 덜들었고조금 듣기 거북한 단어들을 사용해서 읽기 불편한 것들이 사실인데,도움이 됐다고 하시니 정말 제게 큰 힘이 됩니다 :D 올 한해 취업이 목표이셨던 분들,삼성 합격하구 밥 한번 같이 먹자구 연락주시면바보같이 웃고 있는 저를 보면서한끼 공짜로 드실 수 있을 것 같습니다.^^ 11월에 면접까지 끝나고 아마 결과까지 다 나올텐데,부디 좋은 결과로 만나뵐 수 있게 되었으면 좋겠네요! 그럼 저는 이만...
Diary/2017 2017. 11. 2. 00:36

오늘부터 육목(Connect6) AI를 코딩해보려고 한다.

우리 회사 내 DS부문에서 육목 AI 대회가 열렸다. 총 상금 1000만원...1등은 600만원이나 준다. 사실 나는 같이 할 사람도 없고 해서 1인팀으로 참가했는데,1인팀은 안된다는 메일이 날라왔다.당연히 같이 할 사람도 없고 그렇게 큰 뜻을 품은 것도 아니어서 답장도 안보냈는데,팀원을 구할 수 없으면 그냥 1인팀으로 참가하라고 다시 연락이왔다 ^-^ 나는 우리 부서에서도 모르게 그냥 슬쩍 등록하고 나가는 정도라예선 통과도 힘들겠지만, 그래도 한번 도전해보려고 한다. 일단 당장 돌아오는 일요일까지 코드를 완성해야 하는데,퇴근 후 집에와서 코딩 깔짝 하는 것만으로 과연 완성할 수 있을지 잘 모르겠다. 일단 오늘은 한 게 거의 아무것도 없는데,괜찮은 논문 하나를 찾은 것 같다.threat라는 걸 기반으로 ..
Algorithm/Connect6 2017. 10. 31. 01:19

다시 시작한 아스가르드

요즘 다시 아스가르드를 시작했어요~ 처음엔 할게 없어서 와우좀 하다가이번에도 만렙을 못찍고 정액이 끝났는데갑자기 아스가 막 땡겨서~ ㅎㅎ 템도 그대로 있었기 때문에그냥 바로 시작할 수 있었지만,3변셋을 조금 더 좋은거 사구... 아무튼 완전 망해가는 줄 알았는데,최근에 영양제랑 소소한 이벤트까지 하면서뭔가 게임이 조금씩 살아날 기미를 보여주는 것 같았어요! 아래 스샷은 파워래빗+떡국+미라클토닉+각종 직바버프 받고댐감소 디버프 안받았을 때 찍어본거~크~ 댐이 만족스러워요 ^-^ 여기까지는 리히네 포트2 쉬버댐지~4300이라닛!그뤠잇~! 사실 댐감소 디버프 받으면 4100정도 뜨는 것 같아요.ㅎㅎ(평소엔 3700정도 뜨는건 안비밀) 이건 하복댐지~6만 5천대 대미지가 하복 크리터진 대미지에요 ㅎㅎ 3변셋 새..
Hobby/Asgard 2017. 10. 29. 20:51

Counting Sort & Radix Sort

Counting Sort & Radix Sort 오랜만에 포스팅을 해보려한다. 해당 정렬방법은 O(N)만에 수행이 가능하다. 아마 이 정렬방법을 모르는 사람은 거의 없을거고.. counting sort도 다 짤줄 안다고 생각하겠지만, PS를 접하지 않은 사람들은 사실 제대로 짤 줄 모르는 경우가 많다. 소개 순서는 다음과 같다. 1. int type 데이터를 Counting Sort 2. pair type 데이터를 Counting Sort 3. Radix Sort 1. Counting Sort 먼저 개념은 누구나 다 알고 있을 것이다. 이 방법으로 1,3,2,3,4를 정렬하면, count[1]=1; count[2]=1; count[3]=2; count[4]=1; 이므로 해당 개수만큼 순서대로 써주면 된다..
Algorithm/Sort 2017. 10. 28. 22:54

Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquityhttp://codeforces.com/contest/869/problem/E div2이지만 무려 E번 문제다.근데 E번 문제치고는 쉽게 풀 수 있었던 것 같다.2D Fenwick + 적절한 random값으로 풀 수 있었다. 일단 문제는 직사각형 평면에 사각형을 그리고 지우는 것을 반복하다가 틈틈이 쿼리가 들어온다.쿼리는 두점을 찍고 두점을 연결할 때 평면에 그린 사각형들의 모서리를 지나지 않고 연결할 수 있으면 Yes, 아니면 No를 출력해야 하는 문제였다. 일단 아래의 입력을 예제로 한번 더 설명하자면, Examplesinput5 6 5 1 2 2 4 5 1 3 3 3 3 3 4 4 1 1 2 2 2 4 5 3 1 1 4 4 outputNo Yes 맨 위의..
PS - OJ/Codeforces 2017. 10. 12. 22:19