분류 전체보기
-
[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)..
-
해시(Hash)와 해시 충돌 해결 방법CS(Computer Science)/Data Structure 2021. 11. 26. 16:08
1. 해시란? 💡 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다. 1-1. 해시 순서 해당 원소의 해시 함수를 이용하여 해시값을 얻는다. 해시값을 주소로 하는 위치에 원소를 저장한다. 저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다. 1-2. 사용 용도 무결성 검사: 파일 다운로드..
-
[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 ..
-
[Python] 백준 17086 아기 상어 2알고리즘/문제풀이 2021. 10. 30. 00:17
1. 문제 링크 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 2. 문제 요약 안전거리 최댓값 구하기 3. 아이디어 정리 bfs 탐색을 통해 최단 거리 구하기 4. 문제 풀이 4-1. 내 풀이 import sys from collections import deque dx = [-1, -1, -1, 0, 1, 0, 1, 1] dy = [-1, 0, 1, 1, 1, -1, 0, -1] n, m = map(int, sy..
-
[Python] 백준 2470 두 용액알고리즘/문제풀이 2021. 10. 30. 00:15
1. 문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 2. 문제 요약 두 용액을 혼합하여 0에 가장 가까운 용액 만들기 3. 아이디어 정리 투 포인터 이용 합이 0보다 큰 경우 right - 1 합이 0보다 작은 경우 left + 1 4. 문제 풀이 4-1. 내 풀이 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.read..