C++/알고리즘 공부기록 (4) 썸네일형 리스트형 imos법 이해하기 개인 기록용 느낌으로 글을 쓰기 때문에 나만의 해석이 첨가되어 있다 imos법이 뭔지에 대해선 나보다 훨씬 설명 잘 하는 사람들이 많으니 그사람들 글을 보기 바란다 이 글은 imos법이 다양한 문제에 활용되는 모습을 보면서, 그에 대한 내 고찰을 다룬다 imos법에 대한 내 생각은 누적합의 확장된 버전이라는 것이다 n차원 공간에서 쿼리를 처리할 때 그 구간의 시작점과 끝점만 기록해준 뒤, 마지막에 O(N)정도로 후처리를 해주면 그 쿼리 결과를 개빠르게구할수있다는 거였음 그 대표적인 문제들은 아래와 같다 https://www.acmicpc.net/problem/3020 https://school.programmers.co.kr/learn/courses/30/lessons/92344 https://www.a.. 노션/깃헙 board를 활용한 알고리즘 공부 최근 대기업 공채를 집어넣으면서 웬만한 코딩테스트는 합격할 수 있다는 걸 확인했고, 취미로 조금 어려운 알고리즘들도 공부해보려고 한다. 어려운 알고리즘일수록, 1)어디서 키워드를 주워듣는다 2)그 키워드를 구글링하고 공부한다 3)문제풀이 이 순서로 학습하게 되는 것 같은데, 이러한 과정에서 이미 알고있던 알고리즘을 까먹었단 걸 발견하기도 하고 그렇다 이러한 문제점을 해결하기 위해 Notion이나 Github project에 있는 보드를 활용하면 좋다는 생각이 들어 실행으로 옮겼다 아예 모르는 키워드 아는데 까먹은 키워드 개념만 아는 키워드 구현까지 아는 키워드 문제풀이가 가능한 키워드 완벽히 아는 키워드 이렇게 구분해 놓았다 https://lavender-ball-df5.notion.site/65fc5e.. 저는 DP가 너무 어려워요 ㅠㅠ -> Atcoder Educational DP Contest 풀이 (A~H) (작성중) DP는 너무 어려운데 참 자주 보인다 그리고 DP랑 애드혹을 잘 풀어야 멋있어 보인다 Atcoder에서는 Educational DP Contest를 통해 자주 나오는 DP들의 유형과 그 에디토리얼을 제공하니 DP가 어려운 나 너 우리는 모두들 이 문제 셋을 풀어봤으면 좋겠다 Atcoder에 첨부된 에디토리얼은 일본어로만 존재하므로 구글링을 해보는 것이 좋다. 아님 아래 깃헙 코드를 참고하여라 https://github.com/mrsac7/atcoder-educational-dp GitHub - mrsac7/atcoder-educational-dp: Accepted solutions to the Atcoder Educational DP Contest Accepted solutions to the Atcod.. (작성중)정수론 입문 0. 알아둬야 할 부분 이 내용은 정수론 교과서를 따라간 것이 아니라, 알고리즘 문제를 풀면서 나에게 필요한 부분만 공부한 것이고, 주관적인 부분이 많이 섞여 있으며, 틀린 부분이 있을 수 있으니 그냥 참고만 하자 정수론 문제들은 대부분 엄청나게 큰 수까지의 범위를 다룬다. 오버플로우에 조심하자. 아니면 다른 특별한 아이디어가 필요한 문제일지도 모른다. 그냥 파이썬 쓰면 쉽게 풀릴지도 모른다... 그리고 정수론 문제 풀다가 잘 모르겠으면 그냥 풀이를 보자. 정수론은 정말 알면 쉽게 풀지만 모르면 못 푼다고 생각한다. 1. sqrt, ceil, floor, round 이녀석들은 SQL을 하든 엑셀을 하든 어떤 언어를 공부하든 가장 기본적이고 유용하게 쓰일 녀석들임 C++에서 정수끼리의 나눗셈 결과는 .. 이전 1 다음
