본문 바로가기

전체 글263

함수 매개변수 작성 시 주의점 void show_array(const double ar[], int n); 다음과 같은 코드는 show_array()에게 전달되는 배열이 어떤 것이든지 그 배열 안에 있는 값을 변경할 수 없다는 것을 의미한다. 이것은 한 다리 건너는 간접 지시의 경우에만 동작한다. 배열의 원소들이 기본형이 아닌 포인터라든지, 이중 포인터면 const를 사용할 수 없다. 그래서 이차원 배열을 함수의 매개변수로 넘길 때 함수 원형을 const로 설정하지 않는 것이다. 2019. 5. 5.
함수 포인터 함수도 주소를 가지고 있다. 함수는 스택을 하나 새로 만드는 것을 리버싱이나 디버깅을 해봤다면 알 수 있는데, 함수의 주소는 해당하는 메모리 블록의 시작 주소다. 내가 읽고 있는 책에서는 함수 포인터의 활용의 예시로 시간 측정 함수를 예로 들고 있다. estimate()라는 함수가 있는데 함수 포인터를 인자로 받아서 상황에 따라 측정 기준을 바꿀 수 있다는 것이다. 함수 포인터를 사용하기 위해서는 다음과 같은 절차를 거치면 된다. 함수의 주소 얻기 함수를 지시하는 포인터 얻기 함수를 지시하는 포인터를 사용하여 그 함수를 호출하기 ​1. 함수의 주소 얻기 함수의 주소는 함수의 이름이다. 따라서 함수 포인터를 인자로 취하는 foo() 함수가 있다면 다음과 같이 호출할 수 있다. foo(this_is_func.. 2019. 5. 5.
[BOJ] 15553번: 난로 문제 링크 2018년 JOI 1번 문제다. 난로가 켜져 있는 시간은 N + α 인 것은 자명하다. 그렇다면 α를 알아야 한다. 성냥이 N보다 부족하면 계속 켜놔야 하는 시간을 알아야 하는데 예제를 보면서 계산하는 것이 좀 더 좋을 것 같다. [예시1] 1 3 6 K가 2일 땐 1 3 사이[1초]나 3 6 사이[2초]를 계속 틀어놔야 할 것이다. 이것에 착안해서 나는 우선순위 큐(오름차순 정렬)를 사용해서 (친구들 방문이 이어져 있지 않을 경우) 일 때 간격을 우선순위 큐에 저장을 시키고, 만약 이어져 있는 경우에는 cnt를 증가시켰다. 그래서 우선순위 큐에서 pop을 시키는 횟수는 가 된다. 난로가 켜져 있는 시간의 최솟값을 구해야 하므로 정답은 이 된다. #include using namespace s.. 2018. 9. 30.
[BOJ] 2842번: 집배원 한상덕 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, .. 2018. 9. 13.
[BOJ] 1309번: 동물원 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.. 2018. 8. 31.
[BOJ] 1699번: 제곱수의 합 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.. 2018. 8. 30.
[BOJ] 9465번: 스티커 9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화.. 2018. 8. 30.
[BOJ] 1976번: 여행 가자 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 2018. 8. 11.
[BOJ] 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 랜선 하나의 길이를 이분탐색하자. #include #include using namespace std; int k, n, lan[1000001], Max = -987654321; int main() { scanf("%d %d", &k, &n); for (int i = 0; i 1; int cnt = 0; for (int i = 0; i = n) .. 2018. 8. 9.
[BOJ] 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 나무를 자르는 것을 이분 탐색으로 구할 수 있다. 1부터 주어진 나무의 최대 길이까지 이분 탐색을 하면서 잘라서 얻은 나무가 더 많으면 위 부분으로 조절하면 되고 반대로도 같은 방식으로 하면 된다. 하지만 그 필요한 양만큼만 못 가져갈 때도 있으므로 그럴땐 한 번 더 mid를 구한 것이 답이다. 참고: 파라매트릭 서치 #include #include using namespace std; int n, m, maxH = -987654321, tree[1000001]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &tree[i]); maxH = ma.. 2018. 8. 9.
[BOJ] 10815번: 숫자 카드 https://www.acmicpc.net/problem/10815 이분 탐색 #include #include using namespace std; int n, m, ar[500001]; bool bs(int find) { int s = 0, f = n - 1; while (s find) f = mid - 1; else s = mid + 1; } return 0; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &ar[i]); sort(ar, ar + n); scanf("%d", &m); while (m--) { int a; scanf("%d", &a); printf("%d ", bs(a)); } return 0; } 2018. 8. 9.
[BOJ] 1162번: 도로포장 https://www.acmicpc.net/problem/1162 벽 부수기 문제와 비슷하다. 주어만 바뀐 느낌이고 트리 구조(?)에서 그래프로 바뀐 것 뿐이다. 도로를 포장하거나 안 하거나 두 가지 경우가 있으므로 그 두 가지 경우를 모두 확인해주면 된다. #include #include #include #include #include using namespace std; struct Edg { int idx, cnt; long long dst; Edg(int idx, long long dst) : idx(idx), dst(dst) {} Edg(int idx, long long dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool operator nxt.dst .. 2018. 8. 7.
[BOJ] 10545번: 뚜기뚜기메뚜기 https://www.acmicpc.net/problem/10545 만약에 map이 없었다면... 이걸 어떻게 풀었을까 STL을 만들어 주신 모든 분에게 감사드립니다. #include using namespace std; const char alphabet[10][5] = { {}, {}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"} }; int main() { ios_base::sync_with_stdio(false), cin.tie(0); string str; map m; for (int i = 1, a; i > a; for (int j = 0; alphabet[a][j]; ++j) m[al.. 2018. 8. 7.
[BOJ] 2698번: 인접한 비트의 개수 https://www.acmicpc.net/problem/2698 D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수 처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다. 마지막 비트가 0일 때 D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1] 마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다. ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다. 마지막 비트가 1일 때 D[n][k][l.. 2018. 8. 7.
[BOJ] 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 다익스트라를 구현하는데 경로를 저장해야 한다. 추적방법 trace 배열을 선언한다. 다익스트라 알고리즘에서 거리 업데이트하는 부분에 trace[nxt.idx] = now.idx로 지정한다. 도착 지점부터 trace 배열을 돌면서 t = trace[t]를 통해 노드 A로 오기 전 노드로 t를 변경한다. #include using namespace std; struct Edg { int idx, fair; Edg(int i, int f) : idx(i), fair(f) {} bool operator nxt.fair + now.fair) { dist[nxt.idx] = nxt.fair + now.fair; trace[nxt.idx] = now.. 2018. 8. 7.

티스토리툴바