알고리즘 문제풀이/백준20 [백준1238] 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import heapq,sys input = sys.stdin.readline N,M,X = map(int,input().split()) INF = 987654321 graph = [[] for i in range(N+1)] for _ in range(M): s,e,w = map(int,input().split()) graph[s].append([w,e]) def f(graph,S.. 알고리즘 문제풀이/백준 2021. 5. 5. [백준14465] 소가 길을 건너간 이유 5 www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net import sys input = sys.stdin.readline N,K,B = map(int,input().split()) arr = [0]*(N+1) for i in range(B): arr[int(input())] = 1 s=[] cnt = 0 for i in range(N+1): cnt+=arr[i] s.append(cnt) answer = B for i in range(N+1-K): answer = min(answer,s[i+K] - s[i]) print.. 알고리즘 문제풀이/백준 2021. 5. 5. [백준1747] 소수&팰린드롬 www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 문제에서 요구하는대로 N보다 큰 소수를 찾고 그 소수리스트 중 팰린드롬 수를 찾으면 된다. 소수를 찾는 방법은 에라토스테네스의 체를 참고한다 에라토스 테네스의 체는 간단히 설명해서 1~N까지 반복하면서 배수들을 모두 제거하는 것이다. 소수는 어떤 숫자의 배수가 아니기 때문이다. 이렇게 소수리스트를 만든 후 찾는 범위의 숫자 중 작은것부터 하나씩 뽑아 팰린드롬인지 검사한.. 알고리즘 문제풀이/백준 2021. 5. 5. [백준2872] 우리집엔 도서관이 있어 www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 풀이 정렬문제인줄 알고 한참 헤맸다. 또한 문제에서 요구하는대로 그대로 구현하니 시간초과가 떳다. 법칙을 찾아야한다. 45123 순서로 책이 들어온다고 하면, 45는 그대로 두고 123을 위로 올려야 할것이다. 3 2 1 순으로 뽑아야 겠지만 순서는 중요하지 않다. 책을 뽑는 횟수를 세는것이기 때문에 3개라는게 중요하다. 12453 이면 어떨까? 이것도 45만 남겨두고 나머지를 다 위로 올리는 작업을 해야.. 알고리즘 문제풀이/백준 2021. 5. 5. [백준3980] 선발 명단 www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 S의 ij는 i번 선수가 j번 포지션에서 뛸 떄의 능력이다 visited에 이미 방문한 포지션을 체크한다. 방문한 포지션, 자신이 뛸 수 없는 포지션을 제거하고 가능한 포지션들을 재귀적으로 호출한다. 즉, 백트래킹 기법을 사용해 모든 경우를 탐색한다. 함수의 매개변수는 (맵, 선택한 인원, 능력치합, 방문체크)로 구성한다. 시간복잡도 재귀가 최대로 깊어진다고 해보자 가능한 포지션이 최대 5개이고 11명이 있다. 그러므로 재귀는 최대 55번보단 작게 .. 알고리즘 문제풀이/백준 2021. 5. 5. [백준2262] 토너먼트 만들기 www.acmicpc.net/problem/2262 2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 풀이 처음에는 DP인가 생각했다. 결국 못풀어 답을 참고하니 간단한 그리디 문제였다. 붙는 선수끼리의 랭킹차이가 적어야 한다. 이기는 선수(여러번 붙는 선수)는 랭킹이 높은 선수이다. 따라서 낮은 랭킹이 올라가서 여러번 붙으면 안된다. 올라가는 선수들은 랭킹이 높은 선수들이기 때문에 차이값이 많아진다. 즉 랭킹이 낮은 선수부터 시합을 뛰게해 제거한다. 랭킹이 제일 낮은 선수를 찾고 양 옆의 선수중 차이가 적은 선수랑.. 알고리즘 문제풀이/백준 2021. 5. 3. [백준1958] LCS 3 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 개념 LCS는Longest Common Subsequence의 줄임말로,공통 부분 문자열 중 가장 길이가 긴 문자열을 말합니다. 이 때, Substring과 Subsequence와의 차이점을 알 필요가 있습니다. Substring : 전체 문자열에서연속된부분 문자열 Subsequence : 전체 문자열에서꼭 연속된 문자열인 것은 아닌부분 문자열 서로 다른 문자열 중에.. 알고리즘 문제풀이/백준 2021. 5. 3. [백준1114] 통나무 자르기 1114번: 통나무 자르기 첫째 줄에 L, K와 C가 주어진다. L은1,000,000,000보다 작거나 같은 자연수이고, K는 통나무를 자를 수 있는 위치의 개수이다. K와 C는 10,000보다 작거나 같은 자연수이다. 둘째 줄에 통나무를 자를 수 www.acmicpc.net 풀이 처음 생각(오답) : 제일 긴 토막이 짧도록 만드려면 나무토막중 제일 긴 토막을 우선적으로 잘라야 한다. 우선순위 큐를 이용해 제일 긴 토막을 차례대로 뽑아낸다. 우선순위 큐는 [나무길이,나무시작점,나무끝지점] 으로 저장한다. 길이를 최소로 만들어야 하기 때문에 나무의 최대한 중간에 있는 위치를 잘라야 한다. 이분탐색을 통해 나무범위에 해당하는 후보중 중간위치((나무시작점+나무끝지점) // 2)와 가까운 인덱스를 찾는다. 이것.. 알고리즘 문제풀이/백준 2021. 5. 3. 이전 1 2 다음