정찡이 정찡이

백준

• [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..

  Read More
• [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():..

  Read More
• [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. 내..

  Read More
• [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..

  Read More
• [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 ..

  Read More
• [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 = ..

  Read More
• [Python] 백준 16938 캠프 준비

  알고리즘/문제풀이 2021. 9. 11. 21:35

  1. 문제 링크 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 2. 문제 요약 캠프에서 사용한 문제 방법의 수를 출력한다. 3. 아이디어 정리 조합을 이용해서 2~n개까지 문제를 뽑아서 조건에 맞으면 결과에 +1을 해준다. 4. 문제 풀이 4-1. 내 풀이 import sys from itertools import combinations # 문제 수, 난이도 합 l크거나 같고, r보다 작거나 같다, 난이도 차 x보다 크거나 같다 n, l, r, x = map(int, sys.stdin.readline().split()) arr = list(map(int,..

  Read More
• [Python] 백준 2579 계단 오르기

  알고리즘/문제풀이 2021. 9. 11. 21:33

  1. 문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 문제 요약 계단에 점수가 있을 때 게임에서 얻을 수 있는 점수의 최댓값을 구한다. 단 3개 이상의 연속된 계단은 안됨! 3. 아이디어 정리 dp[i][j] 정의: 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 최댓값. i 계단은 밟음 점화식 (연속으로 최대 2개만 가능하니 아래 두 점화식이 나온다.) dp[i][1] = max(dp[i - 2][1], dp[i - 2]..

  Read More