알고리즘 검색 결과

해당 글 78건
in place 알고리즘에 대해서 간단하게 알아봅시다.

정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다. 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 l..
알고리즘/이론 2021. 9. 27. 04:21
Longest Substring Without Repeating Characters 문제를 풀면서 슬라이딩 윈도우를 정복해 봅시다.

이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다. 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다. 문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도..
알고리즘/ps 2021. 8. 27. 20:47
정보를 잘 저장해서 사전순 다익스트라 문제를 풀어봅시다.

얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다. 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요? 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요. 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 ..
알고리즘/ps 2021. 8. 11. 16:00
백준 시철이가 사랑한 수식을 브루트 포스로 검수한 썰

어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다. 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱..
알고리즘/ps 2021. 5. 21. 04:02
기하 문제를 다룰 때 잘 써먹게 되는 radian degree 변환을 알아봅시다.

가끔 기하 문제를 다루다 보면, 각도를 알아야 하는 경우가 있습니다. 혹은 주어진 각도를 가지고 무엇인가를 계산하거나. 그걸 하기 위해서는 라디안과 degree를 알아야 해요. 간단하게 알아보도록 하겠습니다. 먼저, python이나 java에서 제공되는 삼각 함수들에 대해 알아봅시다. cos을 예로 들어보겠습니다. 설명을 보시면, Params가 an angle, in radians로 되어 있습니다. 파이썬의 cos도 마찬가지입니다. measured in radians가 들어가 있습니다. 60을 Math.cos의 인자로 넣어봅시다. 그러면, -0.95241298041이 나오는데요. 우리가 알고 있는 cos60도는 0.5인데, 이것과 다른 수치가 나와 버립니다. 이는 Math.cos에 들어가는 것이 degr..
알고리즘/이론 2021. 5. 16. 02:15
반응형