[프로그래머스] 타겟 넘버 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 완전 탐색이 가능한가? 주어진 숫자의 개수는 최대 20개이다. 모든 원소를 더하거나 빼는 경우를 고려할 때, 최악의 경우에도 2^20번만 연산하면 된다. 이는 10^6 정도인데, 이 정도는 시간 초과 없이 계산할 수 있다. 모든 숫자를 더하고, 빼는 과정을 재귀로 돌리자 재귀 함수의 종료 조건은 index가 numbers 리스트의 길이 이상일 때이다. 만약 종료 조건에서 지금까지 재귀 ..
[백준] 14499번 주사위 굴리기 파이썬 풀이
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 1. 풀이 주사위를 동서남북으로 굴린 결과를 배열로 표현하자 위 그림처럼 동쪽으로 회전하면 기존 1번 자리에는 4가, 3번 자리에는 1, 4번 자리에는 6, 6번 자리에는 3이 온다. rolled = { 1: [o[3], o[1], o[0], o[5], o[4], o[2]], # 동쪽 2: [o[2], o[1], o[5], o[0]..
[백준] 5582번 공통 부분 문자열 파이썬 풀이
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. 풀이 DP 테이블을 활용하자 아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다. [백준] 9251번 LCS 파이썬 풀이 https://www.acmicp..
[백준] 12904번 A와 B 파이썬 풀이
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 1. 풀이 S에 말고 T에 집중하자 처음에는 S에서 T를 만들어 나가는 방식으로 접근했다. S 뒤에 A나 B가 붙는 모든 경우의 수를 고려하면, 그 수가 엄청나게 많아진다. 위 그림만 보아도, B 1글자에서 만들 수 있는 4글자 문자열은 2^(4 - 1) = 8개이다. 최악의 경우라면 S 길이가 1이고, T의 길이가 1,000일 때니까, 경우의 수는 무려 2^..