문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 for test_case in range(1,11): result = 0 houseCount = int(input()) house = list(map(int , input().split())) for i in range(2, houseCount-2): def_2 = house[i] - house[i-2] def_1 = house[i] - house[i-1] def1 = house[i] - house[i+1] def2 = house[i] - house[i+2] if def_2 > 0 and def_1 > 0 and def1..
Problem Solving
문제 https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 풀이 맞는데 왜 틀렸지를 연발한 문제.. for j in range(1,n+1): 에서 범위를 n으로 해서 1이 대입되었을 때 정확한 답이 나오지 않았기 때문.. n = int(input()) max_nl = [] # 뽑은 수 저장 리스트 max_len = 0 # 최대 개수의 수 # 1부터 입력된 양수까지 반복 for j in range(1, n+1): nl = [n, j] # 임시 리스트 i = 0 while True: a = nl[i] - nl[i+1] i+=1 # 음의 정수가 만들어지면 중단 if..
문제 https://www.acmicpc.net/problem/2669 2669번: 직사각형 네개의 합집합의 면적 구하기 평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으 www.acmicpc.net 풀이 겹치는 면적을 어떻게 구할까 생각했는데 아무값도 없는 x, y 평면에 사각형이 한번이라도 해당 면적에 속하면 1을 대입함. 이후 x,y평면에 해당 좌표에 있는 값이 1들의 크기들을 더하면 면적이 됨. # x,y 평면 board = [[0 for _ in range(101)] for _ in range(101)] # x 시작, y시작, x끝, y끝 입력받고 해당 좌..
재귀함수를 이용한 피보나치를 구현해 보고 동적프로그래밍을 활용하여 쉽게 설명할 수 있는 예제인 피보나치 수를 소개한다. 그리고 동적프로그래밍이 무엇이고 이점이 뭔지 살펴보려 한다. 예제 문제 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수 정의 피보나치의 수를 구한다고 가정할 때 다음과 같이 나타낼 수 있다. (예시에서는 fib(5)) 피보나치 수열은 재귀함수 형태로 표현된다. pseudoco..
문제 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 내가 제출한 답 a = [int(input()) for _ in range(9)] sumList = sum(a) for i in range(8): for j in range(i+1, 9): if sumList - (a[i] + a[j]) == 100: one = a[i] two = a[j] a.remove(one) a.remove(two) a.sort() for b in a: print(b) if l..
문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제를 잘못 접근했다. 몸무게가 큰 순서대로 sort로 정렬하고 0번째 리스트 원소와 1번째 리스트 원소를 비교 1번째 리스트 원소와 2번째 리스트 비교... 반복하여 해당 인덱스에 rank를 추가하였다. [[88, 186, 1], [60, 175, 2], [58, 183, 2], [55, 185, 2], [46, 155, 5]] 출력을 구하였지만 문제에서 원하는 출력이 아니니까..
그래프를 탐색하는 방법인 깊이우선 탐색(DFS), 너비 우선 탐색(BFS)를 알아보자 깊이 우선 탐색(DFS) 한 지점을 골라서 팔 수 있을 때까지 계속해서 깊게 파다가 아무리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라서 다시 깊게 땅을 파는 방법 즉, 루트 노드나 임의 로드에서 출발하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방법으로 탐색하는 방법. DFS는 방문한 노드들을 스택 자료구조를 통해 방문했는지 확인한다. DFS는 탐색시 해당 노드를 방문했는지 여부를 검사해야 한다. 이를 검사하지 않으면 계속 탐색하게 되어 무한 루프에 빠지게 된다 스택(Iterative) 또는 재귀함수(Recursive)로 표현함. 재귀함수로 간결하게 구현 가능 깊이 우선..
문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 코드 import sys import heapq n = int(sys.stdin.readline()) card = [] answer = 0 for _ in range(n): heapq.heappush(card, int(sys.stdin.readline())) if len(card) == 1: print(0) else: while len(card) > 1: left = heapq..
문제 https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 코드 arr = [False for i in range(0,10001)] for i in range(1, 10001): sum = 0 n = i while (1): if n == 0: break; a = n % 10 sum = sum + a n = int(n/10) result = sum + i if(i == result): break eli..
문제 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제에서 A배열과 B배열의 값들을 곱해서 최솟값을 구하고자 한다. 가장 작은 수를 뽑아내려면? 최대값 X 최솟값 + 최대값 X 최솟값 + .... + 최대값 X 최솟값 이렇게 반복하면 된다. 즉 배열 하나는 오름차순 나머지 배열 하나는 내림차순하여 같은 인덱스마다 값들을 곱하면 구하고자 하는 가장작은S값을 얻을 수 있다. 문제를 살펴보면 "단, B에 있는 수는 재배열하면 안 된다." ..
