https://www.acmicpc.net/problem/2042세그먼트 트리라는 자료구조를 공부해야지..공부해야지 하다가 미뤄놨는데, 삼성 코딩테스트를 준비하면서 공부를 했다. 구현이 복잡해 보였지만, 결국 분할 정복 테크닉을 구간합에서 구현한 것이라는, 생각보다 쉬운 자료 구조였다. 공부할 때는 개발자 영맨님의 유튜브 영상을 참고했다. 현재 나와있는 어느 자료보다 본질적인 부분에 대해서 잘 설명하신 것 같다. 영상을 보고 이 포스트를 보면 되겠다(포스트는 대충 적어놔서 영상 안보고오면 이해가 안 될 것이다..)https://www.youtube.com/@bluedawnstar 개발자영맨(bluedawnstar) www.youtube.com 알고리즘 분류세그먼트 트리분할 정복 알고리즘문제 설명문제 접근..

백준에서 가장 인기 있는 문제집은 삼성 SW 역량 테스트 A형 문제집이다.https://www.acmicpc.net/workbook/view/1152이 중에서 어려운 문제에 속하는 "온풍기 안녕!"을 풀어보자.알고리즘 분류너비 우선 탐색 (BFS) 문제설명https://www.acmicpc.net/problem/23289while loop을 돌며 다음 단계를 거친다.바람 나옴온도 조절가장자리 온도 1 감소초콜릿 먹기온도 검사이 각각의 부분을 함수로 구현하면 된다. 문제접근1. 바람 나오는거 구현하기바람은 세 방향으로 퍼지는데, 그림으로 표현하면 다음과 같다. 우선 동쪽으로 바람을 쏘는 온풍기를 나타내면 다음과 같다. 문제와 다르게, y를 아래방향, x를 오른쪽 방향으로수정했다.우선 (y,x)에서 오른쪽으..

https://www.acmicpc.net/problem/4991 배열을 통해 적용할 수 있는 고급 테크닉들이 적용된 문제이다. 현대오토에버는 최근 AUTOSAR Classic 직무에 대해서 C 언어로만 응시할 수 있도록 프로그래밍 언어를 제한했는데, 이 경우 배열을 이용한 고난도 문제들이 등장한다. (priority queue는 구현하는데만 한 세월..이므로) 따라서 배열을 이용해서 문제를 풀어야 하는데, 그 중에서도 고급 테크닉인 DP와 비트마스킹 정도인데, 이것들이 짬뽕된 문제이다. 알고리즘 분류다이나믹 프로그래밍비트마스킹외판원 순회 문제(Traveling Salesperson Problem)너비 우선 탐색(BSP) 문제설명 예를 들어 이런 input이  들어오면,7 5........o...*.....

https://www.acmicpc.net/problem/11066 이전 포스트로 "행렬 곱셈 순서"에 대해서 두 가지 방식의 다이나믹 프로그래밍으로 문제를 풀어봤다.https://gg4ever1724.tistory.com/39 [C++] 11049: 행렬 곱셈 순서https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍  문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의gg4ever1724.tistory.com 이 포스트처럼 이번 파일 합치기 문제도 두 방법으로 풀되, 우선적으로 상향식 방법을 연습하자. 알고리즘 분류다이나믹 프로그래밍 문제설명 문제접근 어떻게 보면 행렬 곱셈 순서보다는 덜..

https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍  문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의 곱을 구할 때에는 B x A x C 이렇게 하면 안되지만,A x (B x C) 이렇게 하면 된다는 이야기다.  이 과정에서 행렬 곱을 구할 때 가장 작은 곱셈의 연산 횟수의 최솟값을 구하자는 것이다. 아이디어는 간단하고, 실제 최적화 작업에도 도움이 될 만한 로직이다. 문제접근우선 완전탐색으로 이 문제를 풀 수 있을지! 에 대해 알아보자.for loop 을 돌면서 괄호를 잡을 것이다. 우선 ABCD의 곱을 구한다고 가정하고, 현재 index = B 라고 생각하자. 그렇다면, 여기에서는..

https://www.acmicpc.net/problem/2749 피보나치 수를 구하는 재미있는 방법을 알게 되어 공유한다. 알고리즘 분류분할 정복다이나믹 프로그래밍 문제설명  문제는 아주 간단하다. 다만, n이 1e18이다. 일단 n은 long long으로 받아야 한다. 그리고 MOD값은 1e6이므로, 결과값 역시 안전하게 long long으로 받아주자. 문제접근 우선 피보나치 수열의 점화식은 다음과 같다. 이 방법으로 f(n)을 구할 수 있지만, n이 1억을 넘어가기 때문에 시간 초과에 해당한다. 즉 O(logN)으로 풀어야 한다. 그러면 어떻게풀어야할까? O(logN)으로 해결할 수 있는 알고리즘은 많지 않다. 분할 정복 말고는 풀이를 찾기 어려울 것이다. 따라서 이 문제를 분할 정복으로 풀어보자...

https://www.acmicpc.net/problem/11401  이항 계수 3이라는 문제를 풀었는데, 여기서 사용된 수학 개념과 테크닉은 향후 유용하겠다 싶어서 정리한다. 사용되는 기법유클리드 호제법페르마의 소정리O(logN) 거듭제곱 모듈로 계산(분할 정복)다이나믹 프로그래밍 문제의 접근문제는 매우 간단하다. 이항 계수를 1e9+7로 나눈 나머지를 구하면 된다. 일반적으로 이항 계수를 구하는 방법은 다음과 같이 팩토리얼을 이용한다. 여기서 MOD 연산이추가되어야 할 것이다. 최대 400만 팩토리얼을 구해야 하기 때문에 MOD를 통해 줄여야 한다.  우선 여기까진 당연히 맞다. 그러면 계산을 다음과 같이 해야할까? 아니다. 뭔가 이상하다. modulo 연산은 다음과 같이 덧셈(=뺄셈)과 곱셈에만 적..