투투

programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr 문제요약 입력되는 괄호들의 쌍이 맞는지 확인을 한다. 접근 스택을 이용해 여는 괄호가 들어오면 스택에 넣고 닫는 괄호가 들어오면 POP을 한다. 이때 스택이 비어있는데 닫는괄호가 들어오면 False를 반환하고 모든 문자열을 검색했는데 스택이 비어있지 않는다면 False를 반환한다. 구현 def solution(s): answer = True..

programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 문제요약 모든 음식을 스코빌지수 K이상으로 만들기 위해서 스코빌지수가 제일 낮은 음식과 두 번째로 낮은 음식을 일정한 규칙응로 섞는다. 모든 음식의 스코빌지수가 K이상이기 위해서는 몇 번을 섞어야 하는지 구하라 단 모든 음식을 K이상으로 만들지 못할 때는 -1을 출력한다. 접근 힙으로 분류가 되었기 때문에 Python의 heapq 모듈을 사용해보았다. 힙에 넣게 ..

문제 0 또는 양의 정수가 주어졌을 때 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내자. 입력 0 또는 양의 정수가 담긴 배열 numbers가 입력된다. 출력 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 출력한다. 접근 처음에 numbers에 담긴 숫자들을 문자형으로 바꾸고 리스트에 저장 한다음에 내림차순으로 정렬하여 출려하면 될 줄 알았지만 예외 케이스가 많았다. 먼저 34, 30, 3으로 정렬이 되었고 이대로 출력하면 34303이되어 가장 큰 수인34330이 나오지 않는다. 따라서 현재 문자와 다음 인덱스의 첫 글자가 같을 때 현재 문자의 두 번째 글자가 0이면 스왑을 해주었는데 입력되는 수는 1000이하였기 때문에 한계가 있었다. 이를 해결하는 것이 문자형으로 변경된 리스트..

문제 무인도에 갇힌 사람들을 구명보트로 구출하려고 한다. 구명보트에는 최대 2명씩 밖에 탈 수 없고, 무게제한도 있다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하라. 입력 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit이 입력된다. 사람의 몸무게는 40kg이상 240kg이하 구명보트의 무게제한은 40kg이상 240kg이하 출력 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 출력한다. 접근 최대한 적게 구명보트를 사용하려면 한 번에 많은 사람을 태워야하고 그러기위해서는 몸무게가 작은사람과 몸무게가 큰사람을 비교해보면서 제한 이하라면 이동시켜야한다. 그리고 문제에서 주어진 조건들을 모두 공격적으로 살펴 볼 필요가 있다. 그냥 주어지는 조건은 없다. 여기서 2명..

www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 접근 N! / K!(N-K)! 를 그대로 구현을 하였다. 하지만 math에서 factorial이 있다는 것을 알게되었다. 팩토리얼 안쓰고 구현 N, K = map(int, input().split()) D = 1 t = N-K while N > 0: D *= N N -= 1 M = 1 while K > 0: M *= K K -= 1 while t > 0: M *= t t -= 1 print(D//M) 팩토리얼 연산 from math import factorial N, K = map(in..

문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 접근 처음에는 while문으로 A만큼 빼고 B를 더하도록 하였지만 시간초과가 발생하였다. 이후 규칙을 찾으려고 하였다. 하루에 A-B만큼 올라가게 되고 V로 나누려고 했지만 밤에 자는 동안 떨어..

programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 접근 in 연산을 통해 파악하려고 했으나 몇몇 케이스에서 실패를 하였다. 정렬을 해야할 필요가 있었고 오름차순으로 정렬을 한다면 정수형으로 봤을 때 맨 앞 글자가 작은 순서대로 앞에온다. 만약 맨 앞 글자가 같다면 그 다음 수를 보기 때문에 in 연산을 사용할 수 있게된다. 1233, 33 이라는 케이스가 있을 때 문자열의 길이를 오름차순으로 정렬한다면 33이 1233안에..

programmers.co.kr/learn/courses/30/lessons/12900?language=python3 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 접근 백준에서도 풀어봤던 문제다. 그런데 dp로 접근했을 때 시간초과가 발생하였고 다른 사람의 풀이를 참고하였다. 구현 현재 n의 경우의 수는 n-1, n-2의 경우의 수와 같은데 아래와 같이 구현할 수도 있다는 것을 알았다. dp1에는 현재 n의 경우의 수에 해당하고 dp2는 다음 n의 경우의 수가 담기게된다. def solutio..

문제 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 접근 수들의 규칙성을 찾으려고 하였다. 4는 7가지의 경우의 수가 있었는데 1은 1, 2는 2, 3은 4의 경우의 수가 있었고 각 경우의 수를 펼쳤을 때 중복되는 연산이 많았다. 따라서 현재 N의 경우의 수는 N-1, N-2, N-3일 때의 경우의 수와 같다는 것을 알게되었다. 구현 먼저 1, 2, 3일 때를 먼저 구해놓고 이후의 수들은 for문을 통해 idx..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..