알고리즘/문제풀이
-
[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 ..
-
[Python] Programmers 프린터알고리즘/문제풀이 2021. 9. 28. 13:35
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 2. 문제 요약 3. 아이디어 정리 덱을 사용하여 앞에 있는 문서를 꺼낼 수 있도록 합니다. 가장 앞에 있는 것과 max 문서를 비교하여 더 중요한 문서가 있는 경우 맨 뒤로 보냅니다. 아닌 경우 내가 요청한 문서인지 확인합니다. 4. 문제 풀이 4-1. 내 풀이 import collections def solution(priorities, loca..
-
[Python] Programmers 기능개발알고리즘/문제풀이 2021. 9. 28. 13:30
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 2. 문제 요약 각 배포마다 몇 개의 기능이 배포되는지 반환합니다. 3. 아이디어 정리 덱을 이용하여 걸리는 작업일을 넣어줍니다. 현재 값이 이전 작업보다 작거나 같은 경우 앞 작업 배포 수에 + 1 합니다. 아닌 경우는 배포 시기가 다른 경우라서 1을 뒤에 추가해줍니다. 4. 문제 풀이 4-1. 내 풀이 from collections i..
-
[Python] 백준 12904 A와 B알고리즘/문제풀이 2021. 9. 18. 14:45
1. 문제 링크 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 2. 문제 요약 S를 T로 만들 수 있는지 확인 3. 아이디어 정리 s를 t로 바꾸는 것이 아닌 t를 s로 바꾼다. 반대로 확인해야 모든 경우를 확인하지 않을 수 있다. A가 있는 경우 반대로 뒤에서 제거한다. B가 있는 경우 B를 제거하고 뒤집는다. S==T 같으면 그만 확인한다. 4. 문제 풀이 4-1. 내 풀이 import sys s = ..
-
[Python] 백준 14676 영우는 사기꾼알고리즘/문제풀이 2021. 9. 18. 14:43
1. 문제 링크 https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 2. 문제 요약 3. 아이디어 정리 1. 우선 위상 정렬을 하기 위해 진입 차수를 아래와 같이 저장한다. 2. 건설을 하는 경우 진입 차수가 0이 아니면 치트키 사용 0이고 처음 건물을 지은 경우는 다음 연결 관계를 가진 진입 차수를 -1 하여 건물을 짓도록 한다. 3. 파괴하는 경우 지은 건물이 지금까지 없는 경우 치트키 사용 그 외의 경우 파괴된..