전체 글
-
[Python] Programmers 더 맵게알고리즘/문제풀이 2021. 10. 10. 20:52
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 2. 문제 요약 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 구하여 K 이상 음식 만들기 3. 아이디어 정리 heapq를 이용하여 최소 힙 구한다. 4. 문제 풀이 4-1. 내 풀이 import heapq def solution(scoville, K): answer = 0 heapq.he..
-
[Python] 백준 2234 성곽알고리즘/문제풀이 2021. 10. 9. 15:41
1. 문제 링크 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 2. 문제 요약 방의 개수 구하기 가장 넓은 방 구하기 하나의 벽 제거 시 가장 넓은 방 크기 구하기 3. 아이디어 정리 bfs를 이용하여 탐색을 한다. 방문 안 한 방 중 상하좌우 탐색하여 벽을 찾는다. 벽이 존재하는 경우 "3. 하나의 벽 제거 시 가장 넓은 방 크기 구하기"를 구하기 위해 근처 벽 변수에 넣어준다. 벽이 존재하지 않는 경우 현재 방의 크기를 늘려주고 de..
-
[Python] 백준 1174 줄어드는 숫자알고리즘/문제풀이 2021. 10. 8. 16:44
1. 문제 링크 https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net 2. 문제 요약 n번째로 줄어드는 수 구하기 3. 아이디어 정리 백트래킹 이용 마지막 값 > 현재 값 경우, 재귀 진행하여 감소하는 수를 만들어 준다. 감소하는 수를 정렬한다. 조합 이용 0~9로 하나씩 조합 만들기 모든 조합을 정렬한다. 4. 문제 풀이 4-1. 백트래킹 이용 import sys arr = list() result = set() def dfs():..
-
[Python] 백준 17129 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유알고리즘/문제풀이 2021. 10. 8. 15:53
1. 문제 링크 https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 2. 문제 요약 가장 가까운 음식에 도달하면 음식까지의 최단 거리를 출력한다. 3. 아이디어 정리 bfs 사용 2인 경우 최초 큐에 넣어 준다. bfs를 사용하여 가까운 음식에 방문하는 경우 거리를 출력한다. 음식에 방문을 못한 경우 NIE를 출력한다. 4. 문제 풀이 4-1. 내..
-
[Python] Programmers 단어 변환알고리즘/문제풀이 2021. 10. 6. 13:13
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 2. 문제 요약 한 번에 한 개의 단어만 변경하여 begin ⇒ target으로 변경하는 최소의 과정 찾기 3. 아이디어 정리 bfs로 현재 단어에서 변경 가능한 값을 방문하는 방식을 이용합니다. 현재 값이 target과 동일하면 그만 모든 단어를 현재 단어와 비교하여 1개 차이나는 경우 deque에 넣..
-
[Python] Programmers 위클리 8주차 최소직사각형알고리즘/문제풀이 2021. 10. 5. 13:29
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 8주차_최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 2. 문제 요약 모든 명함을 수납할 수 있는 가장 작은 지갑 만들기 3. 아이디어 정리 가로길이 세로 길이 정렬을 명함 별 진행을 한다. 작은 값 중 가장 긴 길이를 찾는다. 큰 값 중 가장 긴 길이를 찾는다. 2.3 값으로 지갑의 크기를 구한다. 4. 문제 풀이 4-1. 내 풀이 def solution(sizes): # 1. 정렬을 한다. ..
-
[Python] 백준 2812 크게 만들기알고리즘/문제풀이 2021. 9. 28. 13:42
1. 문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 요약 k개를 지워서 가장 큰 수 만들기 3. 아이디어 정리 앞에 있는 숫자가 가장 커야한다. 모든 숫자를 for문을 돌려준다. 리스트에 담기 마지막 숫자와 현재 숫자와 비교하여 현재 숫자가 크면 기존에 담은 수를 pop한다. 4. 문제 풀이 4-1. 내 풀이 import sys """ k개를 지워서 얻을 수 있는 가장 큰 수 구하기 """ n, k = map(int, sys.stdin.readline().split()) # n자리, k개 지우기 s..
-
[Python] 백준 5397 키로거알고리즘/문제풀이 2021. 9. 28. 13:38
1. 문제 링크 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 2. 문제 요약 비밀번호를 출력한다. 3. 아이디어 정리 그대로 구현해준다. < 인 경우 범위 확인하고 now - 1 인 경우 범위 확인하고 now + 1 -인 경우 now 앞에 있는 수를 제거한다. 그 외는 비밀번호이기 때문에 현재 위치에 넣어준다. 4. 문제 풀이 4-1. 내 풀이 import sys from collections import deque for _ in ..