본문 바로가기

코딩테스트

 (55)
[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] 백준 1932번. 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 설명: 삼각형에서 아래에 있는 수를 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 전에 저장된 값을 활용하고 있다. 7일때 3과 8은 7을 활용하여 최댓값을 구해야한다. 반복적이다. 3은 8을 더하고/ 1을 더해 다음값을 저장한다. 8은 1을 더하고/ 0을 더해 다음값에 저장한다. => 다이나믹 프로그래밍이다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 풀이해설: i는 2차원 배열의 길이의 인덱스이..
[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] 백준 1010. 다리놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 조합 방식이다. 조합의 공식을 보면 n..
[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] 백준 11047번. 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제: 최소 동전의 갯수를 찾는 문제이다. 4200원이 주어졌을때 1000 * 4 와 100 *2 동전 6개로 최솟값을 찾을 수 있다. 풀이 설계 p는 인덱스로 사용한다. k가 nlist[p] 보다 작으면 동전의 값이 더 크기 때문에 인덱스 값을 증가시켜준다. ex) 4200 < 5000 k가 nlist[p]보다 크면 cnt = k ..

티스토리툴바