알고리즘
-
[Python] 백준 15683 감시알고리즘/삼성 역량 문제 2021. 12. 4. 23:29
1. 문제 링크 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 문제 요약 사각지대의 최소 크기를 출력 3. 아이디어 정리 각 cctv 모든 경우의 수 구하기 ⇒ 각 경우 별 감시 가능한 좌표를 모두 구한다. 백트래킹으로 모든 경우의 조합을 탐색한다. 최댓값인 경우 갱신한다. 4. 문제 풀이 4-1. 내풀이 def watch(x, y, dir): """ 해당 방향으로 보기 :return: """ set_ = set() for d..
-
[Python] programmers 교점에 별 만들기알고리즘/문제풀이 2021. 11. 27. 22:27
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 교점에 별 만들기 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 2. 문제 요약 Ax + By + C = 0으로 표현할 수 있는 ..
-
[Python] 백준 21921 블로그알고리즘/문제풀이 2021. 11. 27. 21:28
1. 문제 링크 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 2. 문제 요약 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는가 3. 아이디어 정리 누적합을 먼저 구한다. 슬라이딩 윈도우로 특정 기간 동안 최대 값인 경우 방문자 수와 기간을 갱신한다. 4. 문제 풀이 4-1. 내 풀이 n, x = map(int, input().split()) # 블로그 일수, x일 동안 가장 많이 들어온 방문자 arr = list(map(..
-
[Python] 백준 12865 평범한 배낭알고리즘/문제풀이 2021. 11. 27. 21:22
1. 문제 링크 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 문제 요약 3. 아이디어 정리 3-1. 냅색 문제 개념 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. dp[i][j] = max(현재 물건 가치 + dp[이전 물건][현재 가방..
-
[Python] 백준 13975 파일 합치기 3알고리즘/문제풀이 2021. 11. 26. 17:10
1. 문제 링크 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 2. 문제 요약 두 개의 파일을 계속 합하여 최종적으로 하나의 파일을 완성하는데 필요한 비용의 총합을 구한다. 3. 아이디어 정리 우선순위 큐 최소힙을 이용하여 가장 작은 2개의 파일을 얻는다. 두 파일을 합하여 다시 최소 힙에 넣고 파일이 1개가 될 때까지 진행한다. 4. 문제 풀이 4-1. 내 풀이 import sys import heapq for _ in range(int..
-
[Python] 백준 4358 생태학알고리즘/문제풀이 2021. 11. 26. 16:55
1. 문제 링크 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 2. 문제 요약 나무의 종이 전체 몇 %를 차지하는지 구하기 3. 아이디어 정리 defaultdict를 이용하여 모든 dict 값이 0으로 세팅 입력된 값 + 1을 해준다. 나무의 종이 차지하는 비율을 출력한다. 4. 문제 풀이 4-1. 내풀이 import sys from collections import defaultdict dict_ = defaultdict(int)..
-
[Python] Programmers 위클리 12주차 피로도알고리즘/문제풀이 2021. 11. 3. 13:58
[Python] Programmers 위클리 12주차 피로도 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 2. 문제 요약 최대 던전을 방문할 수 있는 수를 출력 3. 아이디어 정리 순열을 이용하여 모든 경우를 확인한다. 4. 문제 풀이 4-1. 내 풀이 from itertools import permutations def solution(k, dungeons): answer = 0 ..
-
[Python] 백준 1476 날짜계산알고리즘/문제풀이 2021. 11. 3. 13:56
1. 문제 링크 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 2. 문제 요약 몇 년인지 구하는 문제 3. 아이디어 정리 단순 구현 4. 문제 풀이 4-1. 내 풀이 E, S, M = map(int, input().split()) # 지구, 태양, 달 ne, ns, nm = 1, 1, 1 ans = 1 while True: if ne == E and ns == S and nm == M: break ne += 1 ns += 1 nm += 1 ans ..