알고리즘

알고리즘 주차가 끝났다. 근데 곰곰히 생각해보니까 1년전에 알고리즘 풀었던게 머리에서 지워진 경험이 있었다.그렇기 때문에 알고리즘 주차가 끝나더라도 계속해서 백준 문제를 풀어야 겠다고 생각했다.하지만 무작정 풀기만 한다면 또다시 머리에서 지워질까봐 엄청 무서웠는데그래서

느슨해진 알고리즘 공부 마지막문제에 갑자기 핵폭탄이 터졌다. 도전? 이라고 적힌 문제였는데 진짜 이거때문에 거의 12시간 가까이 붙어서 이게 뭔가 하고 계속 보니까 정신이 나갈것 같았다.(솔직히 일요일이라서 집중력이 낮아지긴 했다.) 근데 이걸 그냥 머리로만 이해할

설 연휴 첫날이다. 다른 사람들은 집도 가고 약속도 잡고 해서 강의실에 5명도 안남았다. 근데 할게 너무 많이 쌓여있고 기차도 못 잡은 나는 그냥 공부나 해야된다. 집을 짓고 지어도 계속 없어지는 저 비버처럼 공부할게 끊이지 않는다. 하지만 실력도 없는 내가 경

지난 알고리즘 주차때 비트마스킹을 활용해서 외판원 순회 문제의 연산량을 획기적으로 줄였던 적이 있다.https://www.acmicpc.net/problem/2098외판원 순회2에서 비해 메모리/시간만 줄었을 뿐인데 골드 1이 되었다.이 외판원 순회와 같은 n

처음에는 문제를 보고 meet in the middle 과 같은 방법으로 풀면 되는게 아닌가? 라는 생각을 했다. 그도 그럴것이.. 이전문제 N개의 정수로 이루어진 수열이 있을 때, k개의 원소 합이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 이번문제

두 선분이 교차하는지를 판별하는 알고리즘이다.기본적으로 행렬의 외적이 들어가기 때문에 백터 연산이라고 보면 된다.기계공학 책에서나 보던게 여기서 튀어나오니까 어이가 없었다.한줄로 정리하면'한 선분과 한 점을 외적 때렸을때 나오는 값이 양수일때는 점이 선분의 반시계 ,

2-sat 11280 11281 tri 19585

SSC : Strongly Connected Component 강한 결합 요소는 그래프 안에서 강하게 연결된 정점 집합을 의미한다.위 그림에서 보면 ( 1 , 2 , 3 ) , ( 6 , 7 , 5) , ( 8 , 9 , 10 , 11 )은서로가 서로를 가르키며 순환하

또 쉬워보인다고 물었다가 3시간이 날아갔다.백준 18809 Gaaaaaaaaaardenhttps://www.acmicpc.net/problem/18809시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초 512 MB 5

(코테를 처음 봤는데 내 자신을 되돌아보게 되었다..) 청사진이라는 아키텍처 또는 공학 설계를 문서화한 기술 도면을 인화로 복사하거나 복사한 도면을 의미한다. 알고리즘을 처음 배운 사람들은 알고리즘을 이해하기에 바빠서 어떻게 적용시키는가에 많은 고민을 하게 되는

마치 알고리즘계의 기가차드 같은 문제들이 있다.그건 빡구현이라는 문제들이다.https://www.acmicpc.net/problem/1210012100번 2048이라는 문제이다.문제 자체에 그림이 너무 많아서 링크로 때운다.이 문제의 골때리는 점이라고 하면 알

곧있으면 플레 4가 된다.시간이 없어서 정수론 문제를 깔짝여 봤는데 좋은 문제가 있었다.https://www.acmicpc.net/problem/2014소수의 곱 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초 128 MB 16816 4071 28

오늘 알고리즘을 푸는데 참 기묘한 문제를 풀었다. https://www.acmicpc.net/problem/2437 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는

https://www.acmicpc.net/problem/31263백준 31263번 대한민국을 지키는 가장 긴 힘시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 1024 MB 780 268 218 41.366%문제대한민국 공군의 표어는 "대한민국을

실버~골드 쪽에서 문제를 풀다보면 가끔 보이는 모듈러 연산이다.모듈러 연산은 공식만 봤을때 정말 간단하다.A mod B = A % B그냥 별거 없다. A를 B로 나눴을때의 나머지를 구하라는 거다.그럼 빠르게 문제부터 보자.시간 제한 메모리 제한 제출 정답 맞힌 사람 정

백준에 신기한 시스템이 들어왔다.바로 마라톤이라는 시스템인데, 1주일마다 랜덤 8문제를 내주고 문제풀때마다 별가루/업적을 쌓는 시스템이다. 동기부여해주는거를 생각하면 정말 좋은시스템이다.그래서 이번 글에 왜 이런 말을 하냐고 하면, 저 마라톤 시스템은 말 그대로 문제를

그리디는 이론만 보면 참 간단한 알고리즘이다.현제 상황에서 최적화된 답을 고르면 되기 때문이다.하지만 이러한 선택이 바로 보인다면 상관없겠지만2번, 3번의 연산 앞을 봐야한다면 상당히 힘들 것이다.시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초 512 MB

드디어 시간이 나서 알고리즘 공부를 할 수 있게 되었다.정말 바쁜 1주일이었고.. 이번 주말은 느긋하게 보낼 생각이다...그리고 풀고 싶었던 알고리즘이 있었는데, 처음배우는거라 이해는 되어도 코드로 나오지가 않기에 정답 코드를 보며 왜 이렇게 코드를 짰는지 분석해보자.

볼록껍질 알고리즘과 이어지는 내용이다.이번 알고리즘은 이름에서 알 수 있듯이, 길이를 측정하는 기준이 회전을 한다. 무슨말인고 하니, 볼록껍질 list를 탐색하면서 점 사이의 최대값을 구할때 볼록껍질 특성상 원형 도형 위를 회전하며 찾아야 하고 이 때 캘리퍼스로 빙빙

첫 다이아 문제 풀이다.생각보다는 벡터쪽 문제라서 할만은 했지만.. 다른 문제들은 얼마나 어려울지 감조차 잡히지 않는다. 이 문제만 해도 정보 검색하는데만 거의 3시간 넘게 썼었고, 벡터의 길이 계산을 외적/내적을 이용하기 때문에 잠깐의 리마인딩 시간도 필요했다.일반적

요즘 계속 풀고있는 볼록껍질 관련 문제이다.이번에는 볼록껍질 내부에 점이 있는지, 다른 볼록껍질과 충돌이 일어나는지 판단하는 문제이다.시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 128 MB 3483 1013 676 27.457%문제평면 위에 여러 개의

30시간이 날아갔다.KMP 복습한다고 플래 문제 뒤적거리다가 뭔가 재밌어보여서 풀었는데한 1시간쯤 풀다보니 정답률 15프로짜리였다..푼 사람도 보면c++ 29명 + pypy 4명 , 푼 사람의 티어는 플래1 2명 + 나 이렇게 3명 제외하고는 다이아~루비, 마스터이다

또 30시간이 날아가 버렸다.플레티넘 상위권은 확실히.. 어지간하면 재대로 손대기 쉽지가 않다..일단 문제를 풀었지만 정신차려 보니 알고리즘 몇문제에 4일이 지나갔다.....정신 차리고 프로젝트에 집중하도록 해야겠다.시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비

과연 시행당 10배씩 늘어나는 계산이 진짜로 느릴까

코딩 테스트를 할때 필요할수도 있고 아닐수도 있는 글

경로 탐색 알고리즘을 복습해 보자.

알고리즘/함수의 속도 비교

BFS

Eval과 같은 리스크 기술에 대한 생각

볼록껍질 응용문제