문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 넓이우선탐색(BFS)을 사용해 풀었습니다. 그래프에는 시작 정점의 인덱스에 해당하는 리스트에 (도착 정점, 유사도)를 추가해줍니다. 갱신한 유사도가 k보다 크거나 같은 경우, 큐에 (다음 정점, 갱신한 유사도)를 넣고 유사도를 최소로 갱신시켜 나갑니다. 코드 파이썬 from collections import deque import sy..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 백트래킹을 사용했습니다. 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편으로 런타임 에러가 발생할 수 있으므로 재귀 깊이 제한을 설정해주었습니다. lrud를 사전 순으로 {인덱스 : 문자열} 해싱하였습니다. 최소 이동 거리가 k보다 큰 경우 (k - 최소 이동 거리)가 홀수인 경우 위 두 가지 경우를 제외하고 백트래킹을 진행합니다. 한 칸씩 이동하며 스택에 이동 경로를 저장..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 스택을 이용합니다. number에 들어있는 숫자를 하나씩 확인하며 스택의 top에 있는 값이 현재 숫자보다 작으면 계속해서 카운트를 세며 스택에서 pop() 시킵니다. 주어진 숫자가 내림차순으로 정렬되어 주어질 경우도 있기 때문에 스택을 join() 한 값에 k개를 뺀 만큼 슬라이싱 합니다. 코드 파이썬 def solution(number, k): stack = [] cnt = 0 fo..

문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 큐를 사용해 문제를 풀었다. 큐에 저장되어 있는 색종이를 꺼내어 4등분으로 자른다. 자른 색종이의 모든 색이 같다면, 하얀색 혹은 파란색 색종이의 개수를 1 증가시킨다. 반대로 다른 색이 존재한다면, 자른 색종이를 큐에 저장한다. 큐에 저장된 색종이가 더이상 없을 때까지 이를 반복한다. ※ 재귀함수를 사용하는 방법도 좋은 것 같다. 코드 from collect..

문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 큐를 이용해 행 혹은 열에서 0이 아닌 값들을 저장해놓는다. board의 크기만큼 반복문을 돌며 큐의 길이가 2이상인 경우에 앞 혹은 뒤의 두 숫자가 같으면 pop() + pop() 값을 위의 조건이 성립하지 않은 경우 큐가 남아 있다면 pop() 값을 큐가 비어있다면 0을 board에 저장한다. DFS를 활용해 모든 경우의 수를 탐색하며 가장 큰 값을 저장..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 백트래킹을 사용해 풀 수 있었다. 이 문제 같은 경우에는 인자의 개수가 5개 밖에 되지 않기 때문에 파이썬 내장 함수인 product 를 사용하면 더욱 쉽게 풀린다. 코드 def solution(word): count = 0 flag = False stack = [] def DFS(): nonlocal count, flag if len(stack) < 5: for i in ['A', '..