olrlobt

완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm Brute : 무식한 Force : 힘 직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 쓰이기도 한다. 브루트 포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘이며, 대부분은 반복문과 조건문을 통하여 답을 도출한다. 모든 경우의 수를 전부 탐색하기 때문에, 100%의 정확성을 보장하지만, 모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다. 완전 탐색과 브루트포스 알고리즘의 차이 브루트 포스와 완전탐색은 의미차이가 거의 없기 때문에, 같은 의미로 쓰이기도 한다. 영어로도 완전탐색은 Exhaustive Search 라고도 하고, Brute Force ..

https://www.acmicpc.net/problem/2294 🔒 골드5 - #2294 동전 2 📌 테스트케이스 추가 힌트 2 15 3 5 = 3 2 15 2 1 = 8 ✍️ 풀이법 대표적인 DP 문제이고, 이 전 포스트인 동전 1 문제와 비슷하게 생각할 수 있다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저, 1원짜리 동전을 추가해 준다. 첫 동전 만으로는 점화식을 도출하기 어려우므로, 다음 동전으로 넘어간다. 5원짜리 동전을 추가해 주게 되면, 4원까지는 캐시에 영향을 미치지 않는다. 이후, 5원을 만들 때부..

https://www.acmicpc.net/problem/2293 🔒 골드5 - #2293 동전 1 📌 테스트케이스 추가 힌트 4 10 1 2 5 3 = 20 ✍️ 풀이법 대표적인 DP 문제이다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저 1원짜리 동전을 추가한다. 1원짜리 동전으로 1원을 만들던, 2원을 만들던, 3원을 만들던... 값은 모두 1이 되므로 1로 채워지게 된다. 또한, 0원을 만드는 경우도 { x } 동전을 선택하지 않는 경우 1가지로 생각할 수 있다. 다음으로 2원짜리 동전을 추가한다. 2원짜리 ..

🔒 골드5 - #12865 평범한 배낭 📌 테스트케이스 추가 힌트 5 7 6 13 4 8 3 6 5 12 2 7 = 19 ✍️ 풀이법 대표적인 DP (다이나믹 프로그래밍) 문제이다. DP 문제를 해결해야할때, 가장 먼저 고려해야 하는 것은 캐싱을 통한 점화식 생성이다. 먼저 값을 저장할 DP 테이블 만든다. 가로축은 들 수 있는 무게를 의미하며, 세로축에는 차례대로 물건의 무게와 가치를 입력한다. 먼저 첫번째 물건인, 무게 6에 가치 13의 물건이 들어가게 되면, 무게 6까지는 들 수 없으므로 DP (캐시)에 6부터 채워지게 된다. 이후, 두번째 물건인 무게 4에 가치 8의 물건이 들어가게 되면, 마찬가지로 무게 4까지는 들 수 없으므로 이 전 값인 0을 가져오게 된다. 이후, 4부터는 두 번째 물건을 ..

동적계획법 : 다이나믹 프로그래밍 DP (Dynamic programming) DP는 하나의 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 알고리즘 기법이다. DP에서 동적계획법, 동적프로그래밍이라는 단어는, DP 창시자가 그냥 멋있는 단어를 붙인 것이라고 한다. 따라서 크게 의미를 부여하거나 찾아볼 필요는 없다. 하나의 문제를 작은 문제로 나누어 해결하는 방식은 분할정복 알고리즘과 비슷하다고 생각할 수 있다. 분할정복 알고리즘의 경우는 단순히 큰 문제를 작게 나누어 해결하는 방식에 불과하지만, DP의 경우는 작은 문제를 풀고 값을 저장하여, 중복된 계산 자체를 없애버린다. 예를 들어 피보나치 수열을 보자. 피보나치 수열은 재귀함수로, f(n) = f(n-1) + f(n-2) 의 형태를 띈다. 이때 계..

싸피 9기 합격자가 발표된 지 2주가 지났다. 추가합격이 될지 모른다는 희망에 탈락 후기를 미루었었는데, 이제는 그냥 마음을 접고 공부를 열심히 하기로 정해서, 탈락 후기를 쓰며 실수를 반복하지 않으려 한다. 또한, 다음 지원자 분들에게 도움이 되었으면 하는 바람이다. 대외비인 부분은 제외하고, 내가 준비한 과정과 후회되는 점 들을 위주로 작성하였다. 싸피 삼성 청년 SW 아카데미(SSAFY)는 삼성의 SW 교육 경험과 고용노동부의 취업지원 노하우를 바탕으로 취업 준비생에게 SW 역량 향상 교육 및 다양한 취업지원 서비스를 제공하여 취업에 성공하도록 돕는 프로그램이다. https://www.ssafy.com/ksp/jsp/swp/swpMain.jsp 삼성 청년 SW 아카데미 삼성 청년 SW 아카데미| 소..

탐욕법 : 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm)이란 여러 가지 선택지 중에서 지금 이 순간 최적이라고 생각되는 것을 선택하는 알고리즘이다. 지금 당장 최선의 선택을 하므로, 정답을 항상 구할 수는 없다. 하지만, 그리디 알고리즘 자체가 최적의 해를 구하는 것이 아니라, 상대적으로 최적의 해에 가까울 수 있는 해를 구하는 알고리즘이다. 예를 들어, 아래 그림과 같이 Start에서 층을 내려가면서 숫자의 최댓값을 구하는 문제가 있다고 하자. Start에서 시작을 했을 때, 5와 10중에 최댓값에 더 최적화된 선택지는 10이 된다. 그리고 그다음 선택지인, 1과 2중에 최댓값에 더 최적화된 선택지는 2가 되므로, 위 문제를 그리디 알고리즘으로 해결..

* WebRTC에 관한 공부를 하며 정리한 글로, 부정확한 개념 정리가 있을 수 있습니다. * WebRTC에 관한 깊은 정리가 아닌, 간단히 구현을 해보고자 하는 개발자분에게 도움이 되려 글을 작성했습니다. WebRTC는 오픈된 정보가 많지 않기때문에 개발에 어려움을 느끼는 분들이 많을 것 같아, 유용했던 사이트를 공유하려한다. Google Developers Codelabs - https://codelabs.developers.google.com/codelabs/webrtc-web?hl=en#0 Real time communication with WebRTC | Google Codelabs Learn how to stream media and data between two browsers. Get to..