anozanami의 PS 블로그 anozanami의 PS 블로그

https://www.acmicpc.net/problem/2343문제 분석처음에는 어떻게 풀어야 할 지 감이 아예 안잡혔다. 블루레이 길이를 찾아야하는데 강의의 수의 범위가 꽤 커서 이분 탐색을 써야한다는 느낌은 들었지만 어떻게 적용할지 몰랐다. 개강 전부터 풀고 있다가 개강하고 나서 풀게 되었다..이분 탐색을 무슨 값으로 할 지 모르겠어서 어려웠던 것 같다. 이를 블루레이의 길이(l)로 잡았을 때 가능했다.풀어 보기이분 탐색을 진행할 때 start(최솟값)를 블루레이의 최댓값으로 해야 모든 블루레이를 담을 수 있다.(l이 1~9일 때 담는 크기가 1~8이면 9인 블루레이를 담을 수 없다) end(최댓값)는 모든 블루레이의 합이 되면 된다. 반복문을 돌 때 필요한 블루레이수 cnt와 m을 비교하여 cnt..

- 이진 탐색 : 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘. 타 탐색 알고리즘와의 차이점으로는꼭 정렬된 상태에서 구현되어야 한다.시간 복잡도가 O(log n)이다.중앙값 비교를 통한 대상 축소 방식이다.정도가 되겠다. 데이터의 양이 너무 많을 때(타 탐색 알고리즘을 이용하면 시간 초과가 날 때) 이용하면 좋겠다.  - 이진 탐색의 핵심 이론(오름차순으로 정렬된 데이터에서만 적용)현재 데이터의 중앙값(mid)을 선택한다.중앙값 > 타깃 데이터일 때 중앙값을 기준으로 왼쪽을 선택한다. (끝점을 중앙값 바로 이전 데이터로 선택한다.)중앙값 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 문제 하나를 풀면서 적용해보자.https://www.acmicpc.net/problem/1..

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법백트래킹의 가장 기본적인 문제인 N과 M 시리즈의 코드를 분석하면서 이해해보겠다.#include //15649 N과 M(1)using namespace std;int n, m;int arr[10];bool isused[10];void func(int k){ if(k == m){ for(int i = 0; i > n >> m; func(0); return 0;}arr은 답에 해당하는 여러 값을 저장하기 위한 배열이고 isused는 1 ~ N까지의 특정 숫자의 사용여부를 체크하는 배열이다.func 함수가 백트래킹의 핵심이자 전형적인 구조이다.func함수는 현재 숫..

#include using namespace std; #define X first #define Y second int board[101][101]; int dist[101][101]; // 기존의 bool형의 2차원 배열이 아닌 거리를 저장할 int형으로 대체 int n, m; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > board[i]; for(int i = 0; i < n; i++) fill(dist[i], dist[i]+m, -1); queue Q; dist[0][0]++..

Flood Fill 알고리즘은 주어진 시작점으로 부터 연결된 영역을 찾는 알고리즘이다. #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응 bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int n, m; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; // 상하좌우 네 방향을 의미 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0;..

접근 : 처음부터 접근을 완전 잘못했다. 배열의 값을 직접 바꾸면서 진행하려고 했었는데 지금생각해보니 그러면 정말 매우 복잡해지는 길이라는 생각이 든다. 블로그의 도움이라면 절대로 풀 지 못했을 것이다... 블로그에서는 백준 카테고리와 같은 브루트포스 알고리즘을 통해서 설명해주었다. 높이를 브루트포스하여 푼다. 높이 0부터 256까지 검사하면서 어떤 높이 값이 적당할지 체크하는 것이다. 중간 중간에 있는 조건문들도 초견에 풀기 정말로 힘들 것 같다. 풀이 : 높이를 높여가며 먼저 쌓아야 할 블록과 제거해야 할 블록의 개수를 센다. 왜 이렇게 하나면 가장 기본적으로 인벤토리에 있는 블록 개수와 쌓아야하는 블록의 개수에 오류가 생기면 바로 패스해야하기 때문이고 또 시간을 계산할 때에도 꼭 필요하기 때문이다...

접근 : 배열의 원소끼리 관계가 있을거라고 생각했다. 앞의 원소까지의 값에 따라서 그 다음 원소의 값이 결정된다. 전형적인 DP문제이다. 풀이 : DP라는 것을 알고 접근했을 때는 테이블을 현재까지의 연속된 가장 긴/짧은 구간, 점화식을 긴/짧은 것 각각 d1[i+1] = d1[i] + 1, if(arr[i] = arr[i+1]) 로 했다. 초깃값은 d1, d2를 전부 1로 초기화하고 d1[1] && d2[1] == 1, d1[2] && d2[2] == 2 이다. void Solution() { int Answer = 1; int Len = 1; int Len2 = 1; for (int i = 1; i < N; i++) { if (Arr[i] = Arr[i + 1]) Len2++; else Len2 = ..

정의 : DP(Dynamic Programming) 한글로 동적 계획법, 프로그래밍이다. 최적화 이론의 한 기술으로써 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 말을 조금 친절하게 하면 기억하며 풀기로 기억해주면 조금 더 좋겠다. (라임 맞춘거 맞다.) 구현 : 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 구한다. 잠시 바킹독의 실전 알고리즘 (DP)편을 인용한다. DP를 푸는 과정은 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 로 이뤄져 있다. 코딩테스트에 나올 수준의 DP 문제는 일단 점화식만 찾고나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 ..