plzfday's notes

제가 참고한 링크 오늘은 어제저녁부터 지금 시각 1시 30분까지 했던 허튼짓을 담은 글입니다. 윗분의 글이 정말 좋은 글인데 저처럼 템플릿 쓰려고 하다가 시간 낭비하지 않으시길 바랍니다. 제가 이번에 마크다운으로 논문 쓰기를 준비하려고 했던 이유는 최근에 했던 유전 알고리즘의 보고서를 마크다운으로 쓰면 괜찮을 것 같았기 때문입니다. 글 내용은 이미 google docs에 적어놨기 때문에 큰 걱정은 없었고 저녁 시간 동안 모든 일정을 끝낼 수 있을 것이라 생각하고 작업에 착수했습니다.​ 고난 1: Pandoc 설치 Pandoc 자체가 얼마나 큰지 잘 모르겠지만 제 생각에는 다운로드 속도가 너무 느린 것 같습니다. (해외 서버라 그런가..?) 어쨌든, 이거 다운로드하는데 약 2시간 걸렸습니다. 사실 저는 이..

decltype은 키워드이고 declared type의 줄임말이다. 타입을 정해주는 녀석이라고 보면 되겠다. auto와의 차이는 아직 나도 잘 모르겠으니까 추후에 업데이트하도록 하겠다. int x; decltype (x) y; // x와 동일한 타입인 y를 만들어라! 컴파일러가 저 타입을 결정하는 것인데 여기에는 규칙이 있다. decltype (expression) var; 1단계: expression이 괄호가 없는 식별자(identifier) 면, var은 expression과 같은 타입이다. double x = 5.5; double y = 7.9; double& rx = x; const double* pd; decltype(x) w; // double 타입 decltype(rx) u = y // do..

void show_array(const double ar[], int n); 다음과 같은 코드는 show_array()에게 전달되는 배열이 어떤 것이든지 그 배열 안에 있는 값을 변경할 수 없다는 것을 의미한다. 이것은 한 다리 건너는 간접 지시의 경우에만 동작한다. 배열의 원소들이 기본형이 아닌 포인터라든지, 이중 포인터면 const를 사용할 수 없다. 그래서 이차원 배열을 함수의 매개변수로 넘길 때 함수 원형을 const로 설정하지 않는 것이다.

함수도 주소를 가지고 있다. 함수는 스택을 하나 새로 만드는 것을 리버싱이나 디버깅을 해봤다면 알 수 있는데, 함수의 주소는 해당하는 메모리 블록의 시작 주소다. 내가 읽고 있는 책에서는 함수 포인터의 활용의 예시로 시간 측정 함수를 예로 들고 있다. estimate()라는 함수가 있는데 함수 포인터를 인자로 받아서 상황에 따라 측정 기준을 바꿀 수 있다는 것이다. 함수 포인터를 사용하기 위해서는 다음과 같은 절차를 거치면 된다. 함수의 주소 얻기 함수를 지시하는 포인터 얻기 함수를 지시하는 포인터를 사용하여 그 함수를 호출하기 ​1. 함수의 주소 얻기 함수의 주소는 함수의 이름이다. 따라서 함수 포인터를 인자로 취하는 foo() 함수가 있다면 다음과 같이 호출할 수 있다. foo(this_is_func..

문제 링크 2018년 JOI 1번 문제다. 난로가 켜져 있는 시간은 N + α 인 것은 자명하다. 그렇다면 α를 알아야 한다. 성냥이 N보다 부족하면 계속 켜놔야 하는 시간을 알아야 하는데 예제를 보면서 계산하는 것이 좀 더 좋을 것 같다. [예시1] 1 3 6 K가 2일 땐 1 3 사이[1초]나 3 6 사이[2초]를 계속 틀어놔야 할 것이다. 이것에 착안해서 나는 우선순위 큐(오름차순 정렬)를 사용해서 (친구들 방문이 이어져 있지 않을 경우) 일 때 간격을 우선순위 큐에 저장을 시키고, 만약 이어져 있는 경우에는 cnt를 증가시켰다. 그래서 우선순위 큐에서 pop을 시키는 횟수는 가 된다. 난로가 켜져 있는 시간의 최솟값을 구해야 하므로 정답은 이 된다. #include using namespace s..

2842번: 집배원 한상덕 이분 탐색 + flood-fill도 가능하지만 inchworm 알고리즘을 사용할 수도 있다. 피로도와 방문할 수 있는 곳은 비례하기 때문이다. (찾아보니 단조함수이면 가능하다고 한다.) inchworm 알고리즘에서는 1차원으로 작업을 하는데 고차원에서도 가능한지는 모르겠다만... 아무튼 1차원에서 작업하기 때문에 2차원의 좌표에 있는 값을 1차원의 위치로 바꿔주고 정렬을 한 상태에서 inchworm 알고리즘을 돌면서 flood-fill을 했다. #include #include using namespace std; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[] = { 1, 0, -1, -1, -1, 0, 1, 1 }; int n, ..

1309번: 동물원 지극히 개인적인 생각입니다. 제대로된 풀이는 다른 블로그 보시길 바랄게요 죄송합니다! 문제가 규칙성을 찾을 수 있을 것 같아서 야매로 찾다가 3 7 17 41이 나오길래 int n, ret = 3; scanf("%d", &n); int plus = 4, add = 6; for (int i = 1; i < n; ++i) { ret += plus, ret %= R; plus += add, add += 8; } 했지만 당연히 틀렸다. 그래서 "스티커"문제의 경험을 되살려서 대각선으로만 놓을 수 있다는 것에 착안을 했다. dp[0][i] = dp[1][i - 1] + dp[0][i - 2] + dp[1][i - 2] dp[1][i] = dp[0][i - 1] + dp[0][i - 2] + d..

1699번: 제곱수의 합 해법 DP, 동전2 문제와 굉장히 유사하다. 분명히 정올 준비를 하면서 이 문제를 풀어 봤음에도 불구하고 처음에는 n보다 작으면서 가장 가까운 제곱수를 빼주는 것으로 생각했는데 그렇게 하니까 32 = 16 + 16같은 반례에 막혔다.(당연하다... ㅠ) 그래서 다시 생각한 것이 제곱수들의 리스트가 주어질 때 i를 범위 내의 제곱수들로 뺀 수의 최소 구성 개수 중에서 가장 작은 것을 고르는 것으로 생각했다.(= min(D[i - sqrt_list[j]]) ) 그래서 나온 점화식은 다음과 같다. int Min = dp[i - sqrt_list[0]]; for (int j = 1; j 0) return dp[n]; int idx = find_close(n); dp[n] = 1 + st..

9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화..

https://www.acmicpc.net/problem/1976 Union Find를 사용하면 쉽게 풀 수 있다. 만약 갈 수 있는 경로라면 find함수를 실행했을 때 반환값이 모두 같을 것이다. #include #include using namespace std; int n, m, par[201]; int find(int u) { if (u == par[u]) return u; return par[u] = find(par[u]); } void merge(int u, int v) { u = find(u), v = find(v); if (u > v) swap(u, v); par[u] = v; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i