본문 바로가기

Python

 (25)
[Python] 백준 11651번. 좌표 정렬하기 2 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제설명 x,y 가 주어졌을때 y를 기준으로 정렬하는 문제이다. 풀이설계 2차원 배열을 활용한다. x,y 값을 처음에 y,x로 저장한다. 그 다음 리스트를 sort 한다. 출력 시 y,x -> x,y로 바꿔 출력한다. import sys input = sys.stdin.readline n = int(input()) lst = [] for i..
[Python] 백준 1149번. RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제설명 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 풀이설계 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최소값을 저장해나가며 모든 집을 칠했을 때 최소값을 구하는 문제이다. DP용 2차원 배열을 하나 더 만들어준다. 첫번..
[Python] 백준 9461번. 신나는 함수 실행 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제설명: 삼각형이 나선 모양으로 놓여져 있을때 첫 삼각형은 정삼각형으로 변의 길이가 1이다. 그 다음 규칙에 맞게 계속 정삼각형이 추가된다. n이 주어졌을 때, P(N)을 구하는 프로그램이다. 문제설계: 이미 문제에서 수열이라고 알려주고 있다. 하지만 다시 생각해보자 삼각형을 나선형으로 만들어지고 있다. 2가 되었을때 1+1로 밑변으로 2가 만들어지고 있다. 3은 밑변 1+2로 만들어지고 있다. 4는..
[Python] 백준 9184번. 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 설명: 재귀 함수로 실행을 하고 있지만 시간이 너무 걸린다는 문제가 있다. 풀이 방법: dp, 메모이제이션으로 풀어본다. 재귀함수는 일반적으로 연산에 대한 결과를 저장하고 있지 않아 같은 값의 연산도 다시 수행되어야 하는 문제가 있다. 이를 기억하고 있다가 만약 그 숫자들에 대한 연산이 필요하면 값을 꺼내와서 반환하도록 한다. 20보다 크면 무조건 20을 반환하기 때문에 배열은 21을 최대 길이..
[Python] 백준 11399. ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 설명: 줄을 서 있는 사람의 대기시간이 주어졌을때 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 문제이다. 3 1 4 3 2 가 주어지면 1번 = 3분 / 2번 = 1분 / 3번 = 4분 / 4번 = 3분 / 5번 = 2분의 시간을 쓴다. 순서가 1번 -> 2번 -> 3번 -> 4번 -> 5번 이면 1번이 쓰는 시간 : 3분 2번이 쓰는 시간 : 3 + 1 -> 4분 3번이 쓰는 시간 : 3 + 1 + 4..
[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][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 를 설정한다. 디폴..

티스토리툴바