PROGRAMMING
-
(백준 2110번 공유기 설치 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 3PROGRAMMING/STL 2024. 3. 22. 21:52
이분탐색,,, 디버깅 포기한 문제가 속출 중인지라 오늘은 시작부터ㅋㅋㅋㅋ다른 분들의 풀이를 탐독하는 시간을 가져보았다. 안 그래도 자존감 떨어지데 백준까지 나를 힘들게 하면 너무 슬프니까 오늘은 많은 멋진 분들의 코드를 참고했다. 백준 2110번 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제의 아이디어는 이분탐색의 대상을 무엇으로 할지이다. 위치를 기준으로 하면 어렵다. 예를 들어 ..
-
(백준 2805번 나무 자르기 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 2PROGRAMMING/알고리즘 2024. 3. 18. 21:08
라이님 블로그에 나와있는 풀이를 잘 익혀서 modern C++스타일로 짜봤다. 라이님 풀이는 아래 블로그 참고! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777333252&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 백준 2805번 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합..
-
절차형 재귀함수로 permutation 구현하기PROGRAMMING/C++ 2024. 3. 18. 20:57
모던 c++로 배우는 함수형 프로그래밍을 보다가 절차형 재귀함수로 nPr을 구현하는 걸 봤는데 코드가 너무 아름다워서 기록해놓는다. 절차형 재귀 : 값 반환 없이 각 재귀에서 특정한 작업을 처리 https://product.kyobobook.co.kr/detail/S000001804653 모던 C++로 배우는 함수형 프로그래밍 | 위스누 앤거로 - 교보문고 모던 C++로 배우는 함수형 프로그래밍 | 모던 C++의 새로운 기능과 함수형 프로그래밍을 다룬다. 기능이나 개념별로 예제 코드를 작성하고 실행하며 공부할 수 있도록 구성했다. 기본 문법은 자세 product.kyobobook.co.kr 책이 깊지 않다는 평이 있었는데, 내 실력에 이정도면 충분,,(조금 버겁)해서 좋다. 번역도 좋고 설명도 너무 친절..
-
(백준 2512번 예산 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 1PROGRAMMING/알고리즘 2024. 3. 18. 08:46
Modern C++과 함께 하는 월요일 아침.. 이분탐색 코드도 Modern C++ Style로 짜보기로 마음 먹었다. 참고로 이번주는 이분탐색을 뽀갤 예정!! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777333252&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 이분 탐색(Binary Search) (수정 2019-02-15) 안녕하세요. 블로그 점검이 새벽 1시부터 시작되어서 아쉽게도 개삘인 오늘 달릴 수가 없네요. 하지만... blog.naver.com 백준 2512번 https://www.acmicpc.net/problem/251..
-
Modern C++ 알아보기PROGRAMMING/C++ 2024. 3. 17. 20:26
Modern C++의 기본원칙 RAII(Resource Acquisition is Initialization) : 객체와 자원의 라이프 사이클을 일치시키자. C++이후 나온 언어들은 Garbage Collector(GC)라는 자원 청소기가 있어 프로그램에서 더 이상 사용하지 않는 자원을 자동으로 해제해주는 역할을 한다. 하지만 C++의 경우 사용자가 한 번 설정한 자원은 직접 해제해야만 하는데, 이 과정에서 메모리 누수가 일어날 수 있다. 메모리 누수를 방지하기 위해서는, std::unique_ptr와 vector을 이용하는 것도 좋다. - std::unique_ptr은 자원의 소유권을 객체 하나에게만 위임한다. - vector은 동적 배열의 할당과 해제를 직접한다. 즉, RAII에서는 직접적인 new의..
-
(백준 10844번 쉬운 계단의 수 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 8PROGRAMMING/알고리즘 2024. 3. 14. 08:16
출근 전 한문제 컷! 이라고 말하기엔 그제부터 풀었던 쉬운 계단의 수 문제 ㅎㅎ 백준 10844번 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이는 간단하다!(라고 말하고 생각하는데 하루 걸렸다) f(n)을 n자리 계단수의 갯수라고 정의하면 f(n+1) = 2 * f(n) - {n자리 계단수 중 마지막 자리가 0또는 9인 수의 갯수}로 나타낼 수 있다. 마지막 자리가 0 또는 9인 수를 알기 위해 DP[n][10]을 만들어 기록해주기만 하면 완성! 마지막 자리수가 1인 수만이 그 다음 숫자의 마지막 수를 0으로 만들 수 있고, 마지막 자리수가 8인 수만..
-
(백준 12865번 평범한 배낭 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 7PROGRAMMING/알고리즘 2024. 3. 14. 00:06
오늘은 배낭 문제를 풀어보았다. 회사갈 때 재미로 코딩테스트 푸는 영상을 보는데, 문제를 읽다보니 어제 본 문제랑 똑같았다!!!! 아래 유튜브 아니였으면 평생 못 풀고 이해도 못했을텐데..😖 영상이 진짜 잘 설명해준다!!!!(강추) https://www.youtube.com/watch?v=rhda6lR5kyQ 백준 12865번 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이..
-
(백준 2294번 동전2 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 6PROGRAMMING/알고리즘 2024. 3. 12. 21:45
내가 풀었다고 보기도 머쓱한 문제ㅎㅎ 이 문제의 풀이는 라이님 블로그를 무조건적으로 참고해야 한다!!! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 동적 계획법(Dynamic Programming) (수정: 2019-02-07) 안녕하세요. 오늘 소개해 드릴 것은 바로 그 유명한 다이나믹 프로그래밍(Dynamic Programming)입니다. ... blog.naver.com 백준 2294번 https://www.acmicpc.net/problem/2294 2294번: 동전 2 ..