알고리즘/문제풀이
-
[Python] 백준 15656 N과 M (7)알고리즘/문제풀이 2021. 12. 12. 12:43
1. 문제 링크 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 문제 요약 N개의 자연수 중 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 3. 아이디어 정리 증가하는 순서 출력이므로 정렬을 진행한다. 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건 같은 수 여러 개 가능하기 때문에 for 문에 조건을 없이 넣는다. 4. 문제 풀이 4-1. 내 풀이 import sys def dfs(list_): if len(l..
-
[Python] programmers 뉴스 클러스터링알고리즘/문제풀이 2021. 12. 4. 23:36
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 문제 요약 두 문자열의 자카드 유사도를 출력 자카드 유사도: 교집합 크기 / 합집합 크기 3. 아이디어 정리 문자열 2개씩 끊기 교집합, 합집합 구하기 다중집합 구하기 교집합: 두 교집합에서 갯수 최소값 합집합: 두 교집합에서 갯수 최대값 4. 문제 풀이 4-1. 내 풀이 import math def get_set(s)..
-
[Python] programmers 입국심사알고리즘/문제풀이 2021. 12. 4. 23:34
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 2. 문제 요약 모든 사람이 심사를 받는데 걸리는 시간 최솟값 구하기 3. 아이디어 정리 이분 탐색을 통해 걸리는 예측 시간을 구한다. 해당 예측 시간으로 몇 명이 허용되는지 확인 허용 가능한 인원으로 left, right 값을 조절 4. 문제 풀이 4-1. 내 풀이 def solution(n, times): answer = 0 left = 0 r..
-
[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)..