본문 바로가기

코딩테스트

 (55)
[Python] 백준 2231. 분해합 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 설명: 216이 주어졌을때 198 -> 198 + 1 + 9 + 8 로 216을 만들 수 있다. 이 역시 1부터 216이 될 때까지 계속 for문을 돌면서 찾아 볼 수 있다. 문제 설계 루프를 돌면서 i가 10 이상이면 몫과 나머지를 구해 각 자릿수의 합을 구한다. ex) 23 일때 2+3을 구한다. 만약 각 자릿수의 합과 입력받은 N의 값이 같으면 종료한다. i..
[Python] 백준 2798. 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 설명: 주어진 카드 N개와 M을 넘지 않으면서 M을 넘지 않고 M에 최대한 각까운 카드 3장의 합을 구하는 문제 풀이 설계: 찾을 카드의 갯수가 정해져있기 때문에 재귀 함수보다 브루투포스 알고리즘을 이용하여 찾아보겠다. 브루투포스 알고리즘은 쉽게 말해 처음부터 끝까지 찾을때까지 모든 숫자들을 찾아보는 것이다. 결국 3장의 카드를 찾기 위해 for문이 3개가 필..
[Python] 백준 1927. 최소힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 설계: 입력받은 값이 0이고 힙이 비어있으면 0을 출력한다. 힙이 비어있지 않으면 값을 꺼낸다. 입력받은 값이 0이 아니면 힙에 값을 추가한다. import sys import heapq input = sys.stdin.readline n = int(input()) heap = [] for case in range(n): num = int(input()) if num ==..
[Python] 백준 11279. 최대힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 설명: 단순 알고리즘 적용문제이다. 힙으로 해결 가능하다. 주의 할 점은 파이썬은 힙 모듈은 디폴트가 최소힙으로 되어있다. 풀이 설계: 0이 입력되었을때 힙이 비어있으면 0을 출력 0이 입력되어있을때 힙에 원소가 있으면 출력 0이 입력되지 않았으면 heap에 원소추가 이때 제공된 모듈은 최소힙이기때문에 (-1)을 곱해 넣어준다. 5,6,3 -> -6, -5, -3 (6..
[Python][Java] 백준 1021번. 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 설명: N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 첫번째 원소를 뽑았을 때 찾는 숫자가 맞으면 pop을 하고 첫번째 원소와 뽑을 숫자가 맞지 않다면 왼쪽으로 이동시키거나 오른쪽으로 이동시킬 수 있다. 이때 원소들을 찾을 때까지 몇 번의 이동이 있었는지 확인하는 문제이다. 풀이 설계: 양방향 큐이기 때문에 deque로 이 문제를 푼다. dq의 첫번째 원소의 값과 찾는 숫자..
[Python/Java] 백준 4949번. 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 문제 설명: 받은 문자열이 균형이 맞는지 판단하는 문제이다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다. 문제를 보았을때 괄호문제와 별 다를점이 없다. 풀이 설계 flag 를 설정한다. 디폴..
[Python/Java] 백준 9012번. 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 설명: 문자열이 주어졌을 때 주어진 괄호 문자열이 VPS 인지 아닌지를 판단하는 문제이다. 만약 () 으로 계속 맞아떨어진다면 True 이고 )(이거나 (만 있다던가 하면 NO이다. 풀이: flag 설정한다. 디폴트 값은 True 받아온 문자열 split()으로 문자를 확인하여 "("면 스택에 넣는다. 문자가 ")"이면 스택을 확인한다 가장 마지막에 들어간 문자..
[Python][LeetCode] Climbing Stairs(계단오르기) https://leetcode.com/problems/climbing-stairs/description/ Climbing Stairs - LeetCode Can you solve this real interview question? Climbing Stairs - You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Outpu leetcode.com 문제설명: 정상에 도달하기 위해 n 계단을 올라가야 한다. 정상에 도달하기 위한 ..

티스토리툴바