msmn

알고리즘 분류: bfs, dfs 문제 링크: https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net dfs, bfs 모두 해결 가능하지만 이 문제에선 bfs가 메모리와 시간복잡도가 효율적이다. dfs는 방문처리 배열을 선언해야하므로 메모리가 많이 소요된다. #include #define ll long long using namespace std; // https://www.acmicpc.net/problem/1039 교환 int n, k; int conv(int n, int l, int r) { string s = to_..

알고리즘 분류: dp, dfs, bfs 문제 링크: https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net #include #define ll long long using namespace std; typedef pair pii; // https://www.acmicpc.net/problem/1103 게임 int r, c; char board[51][51]; int max_dist[51][51]; int visited[51][51]; const int..

알고리즘 분류: 구현, 시뮬레이션 문제 링크: https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net #include #define ll long long using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector photo; int visit[101] = {}; int n, num_cc; cin >> n >> num_cc; for(int ..

알고리즘 분류: 비트마스킹, 백트래킹 문제 링크: https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net #include #define ll long long using namespace std; // https://www.acmicpc.net/problem/1062 가르침 int word[50]; int alpa; int n, k, ans; void go(int start, int depth) { if(depth == k) { int cnt ..

알고리즘 분류: BFS 문제 링크: https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net #include #define ll long long using namespace std; typedef pair pii; int r, c; char forest[51][51]; int ddg_dist[51][51]; int water_dist[51][51]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; pii ddg; v..

알고리즘 분류: 구현, 자료구조, 스택 문제 링크: https://www.acmicpc.net/problem/3425 3425번: 고스택 각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 www.acmicpc.net #include #define ll long long using namespace std; stack stk; vector commands; vector num_x; int numx(ll x) { stk.push(x); return 0; } int pop() { if(stk.empty()) return -1; stk.pop(); return 0; } int ..

알고리즘 분류: DP 문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net LIS를 활용한 DP로 해결했다. n이 4만이므로 n^2가 8억이므로 시간초과가 발생한다. 이분탐색을 활용하여 O(nlogn)으로 해결했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #incl..

알고리즘 분류: DP 문제 링크: www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net DP[i]: 길이가 i인 모든 2진 수열의 개수라고 정의한다. 주어진 조건대로 나열해보면 DP[i] = DP[i-2] + DP[i-1]이라는 점화식을 도출해낼 수 있다. DP[i-1]의 개수(1 하나가 붙은 경우) + DP[i-2]의 개수(00 붙은 경우)이기 때문이다. #include #include #include #include #include #include #include ..

알고리즘 분류: 백트래킹 문제 링크: www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 먼저, 한 행에 한 개의 퀸만 놓는 방식으로 진행하면 가로 방향은 체크할 필요가 없다. 그렇기 때문에 세로, 슬래시, 역슬래시 방향으로 방문 확인을 해줄 배열을 3개 만들어서 해결했다. 재귀를 돌며 x+1이 되므로 행이 한 칸씩 내려가고 방문확인을 통해 퀸을 놓을 수 있는 좌표인지 확인한다. 놓을 수 있는 곳이면 정답을 +1 하는 방식으로 백트래킹이 진행된다. 예를 들어 n=3일 때를 표로..

알고리즘 분류: 수학, 분할 정복, 재귀 문제 링크: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net O(logb)로 구현하기 위해서는 수학의 거듭제곱의 규칙을 활용해야 한다. (a^b)% c == (a^b/2)% c * (a^b/2)% c이다. 매 번 지수(b)의 홀수 여부를 판별해서 a를 한번 더 곱해준다. 재귀를 도는 동안 b가 절반씩 줄어드므로 O(logb)라 할 수 있다. #include #include #include #include #include #include #include #include #include..