차곡차곡

https://www.acmicpc.net/problem/15591 문제 설명그래프와 유니온-파인드를 활용해 특정 조건을 만족하는 노드(동영상)들의 수를 구하는 문제이다. 그래프 구성동영상들은 노드, 동영상 쌍 간의 USADO 값은 간선의 가중치로 주어진다.총 N개의 노드와 N-1개의 간선이 있으며, 모든 노드는 하나의 연결 그래프를 이룬다. USADO 경로 계산: 두 노드 간의 USADO는 그들을 연결하는 경로의 간선 중 최솟값 아이디어처음 풀이로 BFS를 사용해 탐색했다. 하지만 시간초과가 발생했다. 따라서 union-find 를 사용해 해결했다. 또한 간선을 내림차순 정렬하여 K 이상의 간선만 처리하도록하여 효율성을 높였다. 코드노드 u가 속한 집합의 루트노드를 찾는 find 함수이다. 재귀함수를 ..

https://www.acmicpc.net/problem/9663 해당 풀이는 Python 으로 제출시에도 시간초과가 발생하지 않습니다. 초기 아이디어처음에 문제를 풀 때는 2차원 배열을 사용하여 체스판을 표현한 후, 백트래킹을 이용해 각 칸에 퀸을 배치했다. 결과는 당연히 시간초과가 발생했다.N이 커질수록 백트래킹을 통해 모든 가능성을 탐색하는 과정에서 시간 복잡도가 급격히 증가하기 때문이다. 이를 해결하기 위해서 퀸의 이동 방식에 대해서 다시 생각해보면 아래와 같다. 퀸의  이동방식 퀸은 다음과 같은 방식으로 이동한다. 같은 행에 있는 퀸끼리는 서로 공격할 수 없으므로, 한 행에 하나의 퀸만 배치할 수 있다.퀸은 같은 열에 있는 다른 퀸과도 공격할 수 없으므로, 한 열에도 퀸은 하나만 배치되어야 한다..

https://www.acmicpc.net/problem/1743 문제를 보고 바로 BFS를 이용해 상하좌우에 이어진 쓰래기를 탐색해 최대(Max)를 구하면되겠다고 생각했다. 처음 코드 (메모리 초과)from collections import dequeimport sysinput = sys.stdin.readlinedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]result = 0n, m, k = map(int, input().split())trash = [[False]*m for _ in range(n)]for _ in range(k): x, y =map(int, input().split()) trash[x-1][y-1] = Truedef bfs(x, y): cnt = ..

복잡도란? 복잡도 (Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 크게 두가지로 구분할 수 있다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 시간복잡도와 공간복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 시간적 이점을 얻을 수 있는 경우가 있는데 이 방법으로 메모이제이션 기법이 있다. 시간 복잡도 시간 복잡도를 표기할 때는 빅오..

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 해야할 일이 works 배열에 각 일에 대한 필요 작업량이 저장되어 있다. 1시간에 작업량 1만큼을 할 수 있다. 퇴근 시간까지 남은시간 n 이 주어진다. 야근피로도는 퇴근 시간 이후 각 일의 남은 작업량의 제곱의 합이다. 가장 적은 야근 피로도를 계산해서 Return 해야한다. 접근 법 야근 피로도를 가장 낮추는 방법은 모든 일의 작업량을 균등하게 낮추는 것이다. 남은..

정답 code #Four Squares import sys def check(n): # n의 제곱근이 정수라면 1출력 if (n**0.5).is_integer() : return 1 # n보다 작은 어떤 수를 뺀 수의 제곱근이 정수라면 2출력 ex(A^2+B^2) for i in range(1, int(n**0.5)+1): if (int(n-i*i)**0.5).is_integer(): return 2 #n보다 작은 어떤 제곱근의 수를 두개뺀 수의 제곱근이 정수라면 3출력 ex(A^2+B^2+C^3) for i in range(1,int(n**0.5)+1): for j in range(1, int((n-i*i)**0.5)+1) : if ((n-(i*i)-(j*j))**0.5).is_integer(): re..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 정답 code #카잉 달력 t = int(input()) for _ in range(t): m,n,x,y = map(int,input().split()) f = 1 while x (3-9) % 12 != 0 k = 13 -> (13-9) % 12 != 0 k = 23 -> (23-9) % 12 != 0 k = 33 -> (33-9) % 12 == 0 정답은 33 이 나오게 된다. x = 3(33) y..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 정답 code #AC from collections import deque import sys input = sys.stdin.readline t = int(input()) for _ in range(t): p = input() n = int(input()) arr = input().rstrip()[1:-1].split(',') #괄호 제외하고 [1~-1]까지 ','제외 입력 arr = deque(arr) r = 0 #reverse 횟수 계산 if n ..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 정답 code #집합 import sys input = sys.stdin.readline s = set() #중복 허용 x m = int(input()) for _ in range(m): x = input().strip().split() if len(x) == 1: if x[0] == 'all': s = set([i for i in range(1,21)]) else: s = set() continue menu = x[0] num =..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 정답 code import sys input = sys.stdin.readline n,m = map(int,input().split()) hear = {} result = [] for i in range(n): name = input() hear[name] = i for i in range(m): name = input() if name in hear: result.append(name) res..