본문 바로가기

알고리즘/백준 & swacademy108

BOJ 15649 - N과 M (1~12) N개 중 M개를 뽑아 나열하는 경우의 수 시리즈이다. 기본적으로 백트래킹을 이용해서 재귀로 구현함. 9~12같은 경우 중복을 제거해줘야 하는데, 이건 set로 해결하였다. #include #include #include using namespace std; void printPicked(vector& picked) { for (int n : picked) printf("%d ", n + 1); printf("\n"); } int n, m; void pick(vector& picked, vector& isUsed, int k) { if (k == m) { printPicked(picked); return; } for (int next = 0; next < n; next++) { if (!isUsed[nex.. 2019. 7. 6.
BOJ 2448 - 별찍기11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) www.acmicpc.net 재귀를 이용해서 풀어주면 된다. boj 2447문제도 재귀를 활용한 별찍기 문제인데 2448이 생각하는데 조금더 시간이 걸렸다. 출력은 잘 되는데 자꾸 틀렸습니다가 떠서 찾아봤더니 백준에선 출력을 읽을때 null을 읽으면 틀렸습니다 처리를 한다고 한다. 가로의 길이가 세로의 길이의 두배인 것을 잘 확인해서 문제를 풀었지만 map[][]을 선언할때 가로길이를 두배로 두지 않아서 1차로 헤맸다. map[][]을 ' '로 fill해줄때 선언한 것에 맞게 여기도 가로길이를 세.. 2019. 7. 4.
BOJ 1074 - Z https://www.acmicpc.net/problem/1074 재귀로 완전탐색하는 기본문제를 찾다가 접한 문제다. 주어진 입력을 4분할해서 좌상단 우상단 좌하단 우하단 순으로 방문하고 기저를 잘 처리해주면 되겠다 해서 처음으로 짠 코드. cnt[][] 2차원 배열로 방문 순서를 저장할까 했지만, 그냥 cnt=0부터 한개씩 올려주면서 처리하는 것으로 했다. #include int n, r, c; int cnt, rst; void go(int cy, int cx, int n) { if (n == 0) { if (cy == r && cx == c) rst = cnt; cnt++; return; } go(cy, cx, n - 1); go(cy, cx + (1 2019. 7. 4.
(인강)기초-dp1 * 스터디에서 했던 것 복습한다는 생각으로 진행함. * boj 2225 합분해 문제) 2차원 배열로 먼저 풀어주시고 d[4][0] = d[3][0] d[4][1] = d[3][0] + d[3][1] d[4][2] = d[3][0] + d[3][1] + d[3][2] d[4][3] = d[3][0] + d[3][1] + d[3][2] + d[3][3] 이것을 1차원 배열 표현으로 바꾸는 것을 보여주심. (역순으로 진행해야 함) d[3] += d[0] + d[1] + d[2] d[2] += d[0] + d[1] d[1] += d[0] d[0] += 0 *boj 2011 암호코드 문제) 분기가 너무 많아서 까다로웠음. 침착하게 푸는 습관이 필요한 것 같다. 2019. 6. 23.

티스토리툴바