본문 바로가기

전체 글

[프로그래머스 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개이상 붙이면 안.. 더보기
[백준][Python][10971][브루트포스] 외판원 순회 2 문제 : https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 외판원 순회 Traveling Salesman problem 는 유명한 NP-Complete 문제다. O(N!)의 어마어마한 복잡도를 가지는 문제이므로 순열도 부담없이 사용했다. 문제 풀이는 다음과 같다. 1-n 사이의 모든 순열을 만든다. 수열 하나하나마다: 1-2.. 더보기
[백준][Python][11057][DP] 오르막 수 문제 : https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 이 문제는 고생 많이한 문제다. 문제의 해결법은 다음과 같다. d[i] 를 i+1 번째 자릿수의 앞자리 로 하자. 1자리 숫자들은 전부 오르막 수로 볼수 있기 때문에 1로 초기화한다. 이제 생각해보면 12,13,14.. 23,24,25..등등은 전.. 더보기
[프로그래머스 Programmers][Python] 타겟 넘버 문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 | 프로그래머스 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘 programmers.co.kr BFS로 풀었다. BFS는 기본적으로 큐를 쓰는데, 파이썬은 d.. 더보기

티스토리툴바