시나위

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'

이번 포스팅의 목표는 포인터를 사용해서 연결 리스트(linked list)를 구현하는 것이다. 선수지식은 C의 포인터 인데 사실 몰라도 이해는 될 것 이다. 구현이 조금 어려울뿐 우선 연결 리스트라는 단어를 뜯어보면 연결된(linked) 리스트라는 뜻이다. 파이썬이나 C, C++등 어느정도 지식이 있는 사람들은 배열은 이미 연결되어있지 않나 생각이 들수 있다. 하지만 배열처럼 처음부터 사이즈를 정해져있는게 아니라 새로 추가하든 삭제하든 할때 파편화된 데이터를 만들고 이를 서로 연결해서 리스트로 사용한다는 뜻으로 이해하면 된다. 연결 리스트를 만들기 위해선 각각의 데이터마다 다음 데이터가 어디있는지 알고 있어야한다. 그래서 데이터 뿐만아니라 주소를 저장하는 공간이 있어야한다. 주소 공간이 몇개 인지에 따라..

1. 아직도 교육 리눅스와 C언어를 배웠다. 새로 배우는 것 자체는 재미있으나 8시간 내내 온라인 강의를 들어야해서 집중이 자주 깨지는 문제가 있다. 휴대폰도 멀리하고 강의 외에 웹사이트나 프로그램등을 안키려고 하지만 자꾸 손이 거기로 간다. C언어를 배울 때는 뭔가 만들어야할 것을 넘겨줘서 다행히 정신을 붙잡고 있을수 있지만 그전에는 조금 힘들었다. C언어는 다 아는 것을 바탕으로 빠르게 훑고 넘어갔다. 나도 전공 수업으로 배워서 나름 잘할수 있다고 생각했는데 포인터에서 다시 막혔다. 이번 주말은 다음주 월요일 시험에 대비해서 리눅스 커맨드를 한번 훑었고 포인터를 활용해서 더블 링크드 리스트를 만들어 봤다. (C/C++ 에 코드정도만 간단히 올릴 예정이다.) 내일은 또 시험.. ㅠㅠ 2. 아이패드 미니..

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) *..