본문 바로가기

취준

[백준][Python][10942][DP] 팰린드롬? 문제 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net DP 문제다. 문제의 핵심은 길이가 1,2, 그 이상일때의 경우를 각각 나누는 것이다. (1은 참 0은 거짓이라 하자) dp 배열은 dp[처음][끝] -> 처음 - 끝까지 했을 때 팰린드롬 인가? 이다. 길이가 1 = 무조건 1 길이가 2 = 두 문자가 같으면 1 길이가 3 이상 -> 처음 문자 == 끝 문자 && dp[처음+1][마지막-1] 이 1 import sys n = int(input()) d = [int(i) for.. 더보기
[백준][Python][1890][DP]점프 문제 : https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net DP 길 갯수 문제 변형이다. 입력받는 배열의 원소는 그 자리에 갔을 오른쪽이나 아래로 점프를 해야되는 칸 의 갯수이다. 이 문제는 .. 더보기
[백준][Python][3190][브루트포스] 뱀 문제 : https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 최적화와 기타등등 아무것도 신경안쓴 누더기 코드를 보는 당신! 축하드립니다. 잘난 코드는 다들 비슷하지만 못난 코드는 개성있게 못났다는.. 더보기
[프로그래머스 Programmers][Python] 124 나라의 숫자 문제 : https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 programmers.co.kr 이 문제는 3진법 문제이다. 진법문제는 많으므로 이 문.. 더보기
[프로그래머스 Programmers][Python] 여행경로 문제 : https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 | 프로그래머스 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr Copy-Driven-dev 닉값했다. 개인적으로는 재귀를 정말 싫어하는데, DFS는 재귀를 많이 쓰더라. 대충 방식은 재귀를 쓰나 안쓰나 같다. 티켓을 출발-도착 순으로 나눠서 dict에 넣는다. 티켓의 도착지를 역순으로 저장한다. 스택을 만들고 돌면서 티켓의 출발지에 없거나 -> top not in t 있어도 도착지를 다 돌았으면 -> len(t[top]).. 더보기
[프로그래머스 Programmers][Python] K번째수 문제 : https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 | 프로그래머스 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 설명이 필요할거 같지는 않다. 명령어 단위로 잘라서 정렬하고 위치를 answer에 저장한다. 프로그래머스 문제들은 답은 원소 위치를 1부터 시작하게 주고 정작 데이터는 0부터 시작하게 주는 경우가 좀 있다. 리스트 인덱스에 조심하자. def solution(array, commands): answer = [] for c in commands: a = sorted(array[c[0]-1:c[1]]) ans.. 더보기
[프로그래머스 Programmers][Python] 더 맵게 문제 : https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 | 프로그래머스 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 programmers.co.kr 이 문제는 힙을 쓰면 간단하게 해결된다. 문제에서 섞은 음식의 스코.. 더보기
[백준][9095][Python][DP] 1,2,3 더하기 문제 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 간단한 DP 문제다. 1,2,3 더하기 시리즈 문제를 보면, 여러 제약조건이 생기면서 (같은 번호 2개이상 붙이면 안.. 더보기

티스토리툴바