Coding Test

https://www.acmicpc.net/problem/2309 ✔ 유형 : 완전 탐색✔ 문제 풀이:  def find(): smalls = list() for i in range(9): height = int(input()) smalls.append(height) for i in range(9): for j in range(i+1, 9): odd = smalls[i] + smalls[j] if sum(smalls) - odd == 100: if i > j : i , j = j , i smalls.pop(j) ..

https://www.acmicpc.net/problem/1181 ✔ 유형 : 정렬✔ 문제 풀이: 힙정렬 사용 import heapqfrom typing import MutableSequencefrom functools import reducedef heap_sort(a : MutableSequence): """힙 정렬""" def down_heap( a: MutableSequence, left:int, right:int)->None: temp = a[left] # 루트 # left 이외에는 모두 힙 상태라 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다. parent = left while par..

https://www.acmicpc.net/problem/2751 ✔ 유형 : 정렬✔ 문제 풀이: 시간복잡도를 최소화하여 정렬할 수 있는 법을 찾기. import heapqfrom typing import MutableSequencedef heap_sort(a: MutableSequence)->None: heap = [] for i in a: heapq.heappush(heap, i) for i in range(len(a)): a[i] = heapq.heappop(heap) num = int(input())heap = [None]*num # 원소 수가 num인 배열을 생성for i in range(num): ..

https://www.acmicpc.net/problem/1914 ✔ 유형 : 재귀✔ 문제 풀이: 규칙을 찾아 문제 크기를 줄여 일반화 하노이 탑 규칙 하노이 탑 규칙 최소한의 움직임으로 모든 원판을 크기 순서대로 1번 링에서 3번 링으로 옮겨야 한다.밑에 있는 원판은 위에 있는 원판보다 크기가 커야한다.  간단한 시뮬레이션 간단한 시뮬레이션생각을 바꿔서 마지막으로 남은 N번째 원판을 옮기려면 어떻게 해야할까?  하노이 탑 이동순서 하노이 탑 이동순서 1️⃣ n - 1 개의 원판을 기둥 1에서 2로 옮긴다.2️⃣ n번 원판을 기둥 1에서 기둥 3으로 옮긴다.3️⃣ n - 1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.💡 원판이 n-1 개일때 옮길 수 있으면 n개일 때도 옮길 수 있다!! 구현 구현 1...

https://www.acmicpc.net/problem/9020 ✔ 유형 : 수학✔ 문제 풀이: 소수의 특성과 두 수의 합을 이용 골드바흐 추측- 유명한 정수론의 미해결 문제- 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 문제 조건- 입력받은 N은 2보다 큰 짝수이다.- N은 두 소수의 덧셈 값으로 나타낼 수 있다.- 여러 쌍이 있다면 두 소수의 차이가 가장 작아야한다.  N의 중간값을 기준으로 두고 a+b = N 일 때, a와 b의 차이를 벌리며 a,b 두 수가 소수인 지점을 찾는다.   def isPrime(a : int) -> bool : if ( a == 1 ) : False for i in range(2, 10001): if( i*i > a ) : brea..

https://www.acmicpc.net/problem/1978   ✔ 유형 : 수학✔ 문제 풀이: 소수의 특성과 두 수의 곱의 특성을 이용  소수의 정의 소수의 정의소수 : 1과 자기 자신으로만 나누어지는 수        : 약수가 2개인 수 합성수: 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수  소수 판정법 소수 판정법소수 = 1과 자기 자신으로만 나누어지는 수        = 약수가 2개인 수        = 2부터 N - 1 까지의 수로 나누어지지 않는 수 ⬇️ 코드로 풀어보면 다음과 같다.def isprime(int n) if n == 1 : return 0 for i in range(2, n) if n % i == 0 : return 0 return 1 합성수..

문제 Write a function int solution(vector &A); that, given an array A consisting of N integers, returns the number of distinct values in array A. For example, given array A consisting of six elements such that: A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1 the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3. Write an efficient algorithm..

문제 A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east,1 represents a car traveling west. The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the w..

문제 A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river. You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in second..

문제 A non-empty array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| In other words, it is the absolute dif..

문제 An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing. Your goal is to find that missing element. Write a function: class Solution { public int solution(int[] A); } that, given an array A, returns the value of the missing element. For example, given array A such that: A[0] = 2 A[1] = 3 A[2..

문제 A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target. Write a function:int solution(int X, int Y, int D);that, given three integers X, Y and D, returns ..