시나위

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제를 이해하기까지 꽤 오래걸렸다. 근데 알고리즘이 어렵진 않았다. 문제를 요약하자면 각 목적지 별로 최단 경로를 찾는데 그 최단 경로 안에 g와 h 사이 도로를 포함하는 후보만 출력하는 것이다. 출발지, 교차로 g, h 에서 각 한 번 씩 최단 거리를 탐색하면 충분히 찾을수 있다. 각 지점에서 다익스트라로 최단거리를 파악하고, '출발지에서 목적지 까지'의 최단거리와 '출발지 - g - h ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 언제 풀었는지 모르는 문제지만 새롭게 풀었다. 푸는 방식은 deque같은 자료구조를 사용하지 않고 배열로만 접근해서 풀었는데, start와 end 인덱스, 순회방향을 변수로 R일땐 순회 방향만 바꾸고, D일땐 순회 방향에 맞는 맨 앞에있는 원소를 제거했다. 그외엔 어려운게 없었고 입출력은 C++이라 조금 귀찮은 작업이었다. 파이썬이라면 입출력이 조금 쉬웠을것이다. #include #include // stoi, to_string using namespa..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 비트마스크를 사용한 조합문제이다. dp를 사용하지 않았고 비트마스크를 사용해서 모든 부분 수열의 합을 구했다. def main(): N, S = map(int, input().split()) seq = list(map(int, input().split())) answer = 0 for select in range(1, 1

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크와 동적 계획법을 사용해서 최소비용을 구하는 문제이다. 2차원 배열을 사용해서 푸는데, 상태는 지금까지 선택한 것들을 넣으면 되지만 row 값을 고르는게 오래걸렸다. 이전 값을 넣어야할지 현재 값을 넣어야할지 막막해서 결국 찾아보았고 현재 방문한 도시 번호를 넣는 걸로 하게 되었다. (이건 다른 문제를 더 많이 풀어보면서 감을 익혀야할거같다.) 알고리..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 동적 계획법을 사용한 문제인데 어떻게 짜야할지 막막했다. 그래서 구글링으로 LCS에 대해서 찾아보았고, 도움받은 것을 바탕으로 코드를 작성했다. 맨 아래 참고 블로그를 확인하자 a, b = input(), input() c, r = len(a), len(b) t = [[0 for _ in range(c + 1)] for _ in range(r + 1)]..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) node_parent = [-1 for _ in range(N)] node_son = [[] for _ in range(N)] root = 0 for son, parent in enumerate(map(int, input().split())): if parent == -1: root = son..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net import sys;input = sys.stdin.readline from collections import deque # 탐색 def bfs(start, end, size, building): q = deque() q.append(start) visit = [[[0 for k in range(size[2] + 2)] for j in range(size[1] + 2)] for i in range(si..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr from heapq import heappush, heappop def solution(operations): answer = [0, 0] min_h, max_h = [], [] number_in_heap = dict() for op in operations: if op[0] == 'I': # 숫자 삽입 _, num = op.split() num = int(num) heappush(min_h, num) heappush(max_h, -num) if not number_in_heap.get(num): number_in_heap[num] = 0..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 지난번 풀었던 문제인데 재채점된 이후에 값이 틀리게 나와서 다시 풀게되었다. import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(start, end, num_of_nodes): INF = 200_000 * 1_000 * 2 q = [] q.appen..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net #include #include using namespace std; typedef long long ll; typedef vector matrix; #define DIVMOD 1000000007; matrix operator *(matrix a, matrix b) { ll i, j, k; matrix ret(2, vector(2)); for (i = 0; i < a.size(); ++i) { for (j = 0; j < a.size(); ++j) { for (k = 0; ..