티스토리

hijkl2e

검색하기

블로그 홈

hijkl2e

hijkl2e.tistory.com/m

hijkl2e 님의 블로그입니다.

구독자: 34

방명록 방문하기

주요 글 목록

문제 해결력을 높이는 알고리즘과 자료 구조 17-18장 연습 문제 풀이 17장 연습 문제 풀이 18장 연습 문제 풀이 P와 NP 그리고 다항식 알고리즘이 발견되지 않은 문제에 대한 접근법을 배우며 모든 장을 마무리하였다. 모든 장을 마쳤으니 간단히 도서 리뷰를 하고자 한다. "코딩 테스트, 프로그래밍 경진대회 전 필독서!" 출판사에서 제공하는 도서 홍보 문구이다. 우선 코딩 테스트 대비용으로는 적합하지 않다. 프로그래밍 경진대회 입문자에게 적합한 책이다. 그 이상의 실력자에게는 딱히 권장하지 않는다. 알고리즘 + 자료 구조 책처럼 보이지만 사실 그냥 알고리즘 책이다. 대표적인 자료 구조는 8장부터 10장까지 총 3장에 걸쳐 어설프게 다루고 있다. 자료 구조를 공부하고 싶다면 자료 구조를 전문적으로 다루는 책을 선택하자. 일본어 번역본이라서 어색한 문장들이 보이지만 읽기 어려.. 공감수 0 댓글수 0 2022. 10. 15.
문제 해결력을 높이는 알고리즘과 자료 구조 16장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 16.3번은 너무 복잡하게 푼 것 같아 저자의 풀이를 봤는데 똑같았다. 코드가 단순하지는 않았는데 나름 재미있는 문제였다. 연습 문제 16.5번은 아무리 머리를 굴려도 그래프 모델링이 되지 않아 힌트를 찾아보았다. 찾아보니 Kőnig's theorem을 모르면 풀 수 없는 문제였다. 2차원 격자가 주어지.. 공감수 0 댓글수 0 2022. 10. 14.
문제 해결력을 높이는 알고리즘과 자료 구조 15장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 15.2번은 proof by AC로 증명하였다. 유용한 성질인 듯 하여 잘 정리해놓았다. 연습 문제 15.3번은 이전 문제에서 얻은 성질을 이용해보려 하였으나 잘 되지 않았다. 결국 에디토리얼을 봤는데 감탄사가 나왔다. 끝 공감수 0 댓글수 0 2022. 10. 11.
문제 해결력을 높이는 알고리즘과 자료 구조 14장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 14.5번은 에디토리얼을 보고 풀었다. 정점 개수는 K개로 줄였으나 간선 개수를 ϕ(K)개에서 줄이지 못하였다. 에디토리얼에서는 정말 간단하게 간선 개수를 2개로 줄인다. 또한 0-1 BFS에서는 동일한 정점이 덱에 2번까지 들어갈 수 있다. 이 부분 때문에 WA를 받았다. 오늘은 못 풀었어도 매일 발전.. 공감수 0 댓글수 0 2022. 10. 9.
문제 해결력을 높이는 알고리즘과 자료 구조 13장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 13.6번은 간결하게 구현하려고 열심히 노력하였다. 여러 소스를 참고하였는데 현재 코드가 그나마 만족스럽다. 끝 공감수 0 댓글수 0 2022. 10. 8.
문제 해결력을 높이는 알고리즘과 자료 구조 12장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 12.5번과 12.6번은 굉장히 어렵다. 연습 문제 12.5번은 단순히 quickselect 알고리즘을 구현하는 문제인 줄 알았다. 이 경우 평균 시간 복잡도는 O(N)이 되어 문제의 조건을 만족한다. 자세히 보니 최악 시간 복잡도가 O(N)인 알고리즘을 설계하는 문제였다. 이 문제는 median of .. 공감수 0 댓글수 0 2022. 10. 7.
문제 해결력을 높이는 알고리즘과 자료 구조 8-11장 연습 문제 풀이 8장 연습 문제 풀이 9장 연습 문제 풀이 10장 연습 문제 풀이 11장 연습 문제 풀이 8-11장에서는 자료 구조를 다룬다. 각 장에서 다루는 자료 구조는 다음과 같다. 8장에서는 배열, 연결 리스트, 해시 테이블을 다룬다. 9장에서는 스택과 큐를 다룬다. 10장에서는 그래프와 트리를 다룬다. 11장에서는 Union-Find를 다룬다. 8-10장은 잘 알고 있는 내용이라 가볍게 읽었다. 다만 연습 문제 9.1번은 매우 귀찮았다. 연습 문제 10.5번은 저자의 간략한 수학적 귀납법 풀이에 놀랐다. 11장에서는 Union-Find 자료 구조를 다룬다. Union-Find를 naive하게 구현하면 시간 복잡도는 O(N)이다. 때문에 union by size(rank)나 경로 압축과 같은 최적화 기법을 적용해.. 공감수 0 댓글수 0 2022. 10. 3.
문제 해결력을 높이는 알고리즘과 자료 구조 7장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 7.2번은 sweep line 알고리즘으로 O(NlogN)에 풀이할 수 있다. 난이도가 조금 있는 편이라 개정판에서는 O(N^2)으로 풀이하도록 수정되었다고 한다. 끝 공감수 0 댓글수 0 2022. 10. 2.
문제 해결력을 높이는 알고리즘과 자료 구조 6장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제 풀이에 많은 시간을 쏟았다. 새로 배우고 깨달은 것이 많아 간단히 정리하고자 한다. 6.1번 좌표 압축, 모든 요소가 서로 다르다는 조건이 있으므로 unique는 필수적이지 않다. 6.2번 각 b[i]에 대응하는 a[i]와 c[i]의 개수를 잘 세주자. 6.3번 2개씩 나누어서 조합하자. O(NlogN).. 공감수 0 댓글수 0 2022. 9. 29.
문제 해결력을 높이는 알고리즘과 자료 구조 5장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 연습 문제가 중요한 책이다. 많이 배워 간다. 연습 문제 5.4번과 5.6번에서는 dp 테이블의 차원 축소 기법을 배울 수 있었다. 판정 문제라고 해서 테이블을 무조건 bool 형으로 선언하는 것은 어리석다. int 형으로 선언하고 추가적인 정보를 기록함으로써 복잡도를 크게 줄일 수 있다. 연습 문제 5.9번은 K.. 공감수 0 댓글수 0 2022. 9. 27.
문제 해결력을 높이는 알고리즘과 자료 구조 4장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 유클리드 알고리즘의 정당성 및 시간 복잡도 증명이 궁금하여 추가적으로 공부하고 있다. 확실히 직관적이지는 않고 다소 까다로운 면이 있다. 현재 모든 증명을 개인적으로 정리하였으나 내일까지 충분히 검토한 후 월요일에 포스팅하려 한다. 끝 공감수 0 댓글수 0 2022. 9. 24.
문제 해결력을 높이는 알고리즘과 자료 구조 3장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com AtCoder 처음 사용해보는데 지문도 UI도 깔끔하다. 끝 공감수 0 댓글수 0 2022. 9. 23.
문제 해결력을 높이는 알고리즘과 자료 구조 2장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 엄밀한 증명을 해본 경험이 거의 없고 그마저도 몇 년 전 이야기이다. 쉬운 문제에 오랜 시간을 들였지만 그만큼 얻어 가는 것이 있어 다행이다. 마지막 문제의 적분 풀이가 꽤나 흥미로웠다. 끝 공감수 0 댓글수 0 2022. 9. 22.
문제 해결력을 높이는 알고리즘과 자료 구조 1장 연습 문제 풀이 GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이. Contribute to hijkl2e/drken1215_algorithm_solution development by creating an account on GitHub. github.com 1장 연습 문제 풀이 완료 끝 공감수 0 댓글수 0 2022. 9. 21.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.