시나위

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다 3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다. 바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다. # import sys; input = sys.stdin.readline from collections import deque def bfs(): global N, M..

https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹이 너무 부족해서 쉬운문제부터 다시 시작... def backtrack(ind, limit, prev): global nums, answer, visit if ind == limit: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in answer: print(*tmp) answer.add(tmp) return ..

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 두 개의 힙(최대힙, 최소힙)을 사용해서 최대값 최솟값을 같이 파악하고, 출력할때 힙에서 제거했던 값이면 빼내는 방법으로 진행한다. 한번 제거했다가 같은 문제번호가 난이도가 바뀌어서 추가하는 경우 따로 처리해줘야했는데 level이라는 딕셔너리를 사용해서 현재의 난이도를 추적할수 있도록 했다.(힙에 같은 문제로 이전 난이도를 가지고 있다면 제거할수 있도록) import..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 백트래킹 문제를 풀다가 계속 틀려서 쉬운문제를 하나 가져왔다. 최소 신장 트리를 구하는 문제이고 prim 알고리즘을 사용해서 풀었다. 다익스트라랑 크게 차이가 없는듯 하다. from heapq import heappop, heappush def mst(g): ret = 0 visit = [0 for _ in range(len(g))] h = [(0, ..

https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문자열 문제이고 쉬운 문제이다. 포인터로 풀었다. #include #include int main() { int i, tmp; char s[101], *ptr; fgets(s, 101, stdin); ptr = s; while (*ptr != '\0') { if ((int)'a'

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net DP로 풀면 되는데 자료형을 주의해야한다. #include #include #include int arr[100][100]; long long dp[100][100] = { 0, }; int main() { int n, i, j, tmp; scanf("%d", &n); int* arr = (int*)malloc(sizeof(int) * n * n); long long* dp = (lon..

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 쉬운문제인데 C++ 공부를 위해 풀었다. 현재 단계에 있는 모든 돌들을 확인하면서 다음 단계를 추가하고 가장 마지막에 있는 돌에서 최솟값을 찾는 방식으로 풀었다. #include #include using namespace std; int find_energy(int n, int super_jump, int jump[20][2]) { int i, j, cur, cur_chance, ret; vector memo[20]; memo[0].push_back(make_pair(0, 1)); for (i = 0; i < n; i++..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS로 진행했다. #include #include #include using namespace std; #define D(s) ((2 * (s)) % 10000) #define S(s) (((s) + 9999) % 10000) #define L(s) (((s) % 1000) * 10 + ((s) / 1000)) #define R(s) (((s) / 10) + (((s) % 10) *..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 전형적인 유니온 파인드 문제인데 recursion 에러로 애를 먹었다. sys.setrecursion으로 해결하려했으나 못했고, 반복문으로 구현해서 통과했다. import sys; input = sys.stdin.readline def find(a, p): if a == p[a]: return a # p[a] = find(a, p) while a != p[..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전형적인 백트래킹 문제이다. import sys; input = sys.stdin.readline def is_correct(value, r, c): global sudoku, find_list # 1 check row for i in range(9): if value == sudoku[r][i]: return False # 2 check col for i in range(9): if val..