우당탕탕 공부중

[백준 1463번] 1로 만들기 - python

https://www.acmicpc.net/problem/1463📌 문제 탐색하기목표정수 n이 주어졌을 때 세 가지 연산 기법들을 사용하여 1을 만들어 본다.연산을 사용하는 횟수의 최솟값을 출력한다.사용할 수 있는 연산은 다음과 같다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.입력값정수 n을 입력한다. (1 ≤ n ≤ $10^6$)ex)10출력값세 가지 연산들을 사용하는 횟수의 최솟값을 출력한다.ex)3📌 코드 설계하기해결 아이디어시간 제한이 0.15초이므로 재귀나 반복되는 계산을 모두 줄여야한다.수의 규칙을 찾기 위해 쭉 써보면 다음과 같은 결과가 나오게된다.연산을 위해 이미 연산이 되어있는 앞의 숫자를 사용하면 되는 것이다.그러면 bottom-..

[백준 1010번] 다리 놓기 - python

https://www.acmicpc.net/problem/1010📌 문제 탐색하기목표다리를 지을 수 있는 경우의 수를 구해보자.다리는 반드시 N개를 지어야 하고 교차되지 않아야한다.한 사이트에는 최대 한 개의 다리만 연결이 가능하다.입력값서쪽 사이트: N동쪽 사이트: M (N ≤ M)ex)3 2 2 1 5 13 29출력값다리를 지을 수 있는 경우의 수를 출력한다.ex)1 5 67863915📌 코드 설계하기해결 아이디어교차되지 않게 다리를 짓는 방법의 수 → 조합 문제결국, M개의 동쪽 사이트 중에서 N개를 선택하는 경우의 수와 동일하다.따라서 mCn = m! / (n! · (m-n)!)📌 정답 코드import sysdef fac(n): result = 1 for i in range(1, ..

[백준 2775번] 부녀회장이 될테야 - python

📌 문제 탐색하기목표아파트에 해당 집에 거주민 수를 출력하기a층의 b호에 살려면 자신의 (a-1)층의 1호부터 b호까지 사람들의 수의 합 만큼 데려와 살아야한다.입력값첫 번째 줄에 테스트케이스 수 t가 주어진다. (t에 대한 제한은 주어지지 않는다.)각 케이스마다 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 ≤ k, n ≤ 14)ex)2 1 3 2 3출력값각 테스트케이스에 대해서 해당 집에 거주민 수를 출력한다.ex)6 10📌 코드 설계하기해결 아이디어시간 제한을 보면 0.5초이다. 약 5천만 번만 연산 가능하다는 뜻이다. 계속 재귀로 구현하면 시간복잡도가 굉장히 높을 것이므로 dp로 풀자.어제 풀었던 피보나치 수열의 방법을 떠올리면 하나의 배열을 만들어서 한 번 계산을 진행하면..

https://www.acmicpc.net/problem/2748📌 문제 탐색하기목표피보나치 수열 계산해서 n 번째 피보나치 수 구하기입력값n이 주어진다. (1 ≤ n ≤ 90)ex)10출력값n번째 피보나치 수를 구해서 반환한다.ex)55📌 코드 설계하기해결 아이디어흔히 생각하는 일반 피보나치 수열은 재귀를 쓰기 때문에 시간 복잡도가 굉장히 크다. 따라서 시간 제한이 1초로 제한되어있으니 dp를 사용해서 구현해보자.dp를 쓰기 위해서는 배열을 정의해야 한다.한 번 fibo(n)을 구하면 배열에 해당 값을 저장한다. 다시 fibo(n)이 필요하면 다시 재귀를 호출하지 않고 저장된 값을 꺼내 쓰도록 하는 것이다. 이렇게 하면 숫자는 단 한 번만 계산된다.📌 Trouble Shooting1차 시도impo..

https://www.acmicpc.net/problem/2578📌 문제 탐색하기목표빙고 게임 만들어서 선이 세 개 이상 그어지게 만드는 수 출력하기빙고는 가로, 세로, 대각선을 취급한다.입력값첫 줄부터 총 다섯 줄까지 빙고판에 써질 숫자가 주어진다. 1~25까지의 수가 하나씩 입력된다.사회자가 부르는 수가 여섯째 줄부터 열째 줄까지 주어진다. 마찬가지로 1~25까지의 수가 하나씩 입력된다.ex)11 12 2 24 10 16 1 13 3 25 6 20 5 21 17 19 4 8 14 9 22 15 7 23 18 5 10 7 16 2 4 22 8 17 13 3 18 1 6 25 12 19 23 14 21 11 24 9 20 15출력값철수가 “빙고”를 외치게 되는 숫자를 출력한다. 빙고는 가로, 세로, 대..

버블 소트는 인접한 두 원소를 비교해가며 더 큰 값을 한 쪽 끝으로 밀어 올리는 정렬 알고리즘이다. 가장 단순하고 직관적인 알고리즘이라 정렬의 기본 개념을 이해하는 데 매우 유용하다. 마치 큰 거품이 물 위로 차례로 떠오르는 모습과 같다며 해당 이름이 붙었다.정렬 과정 (오름차순)한 번 순회할 때 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를 등 계속 마지막 바로 전 원소와 마지막 원소와 비교하여 가장 큰 값을 오른쪽 끝으로 이동한다.한 번 순회할 때 생긴 오른쪽 끝의 가장 큰 값은 고정되어 다시 비교할 필요가 없다.정렬이 완료될 때까지 반복한다.파이썬 코드def bubble_sort(arr): n = len(arr) for i in range (n): for ..

https://www.acmicpc.net/problem/7568📌 문제 탐색하기목표몸무게와 키를 비교하여 덩치 등수 매기기몸무게와 키 모두가 커야지 등수가 더 높다.입력값첫 줄에는 전체 사람의 수 N이 입력된다. (2 ≤ N ≤ 50)N개의 줄에 각 사람의 몸무게와 키가 양의 정수로 공백을 두고 주어진다. (10 ≤ x, y ≤ 200)ex)5 55 185 58 183 88 186 60 175 46 155출력값나열된 사람의 덩치 등수를 구해서 입력된 순서대로 등수를 한 줄로 출력한다.ex)2 2 1 2 5📌 코드 설계하기해결 아이디어입력을 받으면서 비교를 해야할까 먼저 고민을 했다. 근데 입력을 받으면서 비교하려면 처음 입력된 사람의 키 몸무게는 비교할 대상이 없어서 나중에 다시 비교를 하려면 계산..

https://www.acmicpc.net/problem/2947📌 문제 탐색하기목표나무 조각 5개를 앞에서 부터 하나씩 바꿔가며 정렬하기두 개의 나무 조각에 써져있는 수를 비교하며 앞 조각의 수가 뒷 조각의 수보다 크면 위치를 바꾼다.입력값1, 2, 3, 4, 5 숫자가 랜덤으로 배치되어 한 줄에 입력된다.ex) 2 1 5 3 4출력값두 조각의 순서가 바뀔 때마다 조각의 순서를 출력한다.ex)1 2 5 3 4 1 2 3 5 4 1 2 3 4 5📌 코드 설계하기해결 아이디어차근차근 수를 비교하며 정렬을 한다.완료된 정렬 결과와 실제 정렬 결과와 비교를 한 후 일치하지 않으면 다시 처음부터 비교하며 정렬을 진행한다.📌 정답 코드block = list(map(int, input().split()))wh..

https://www.acmicpc.net/problem/25305📌 문제 탐색하기목표n명의 응시자 점수 중 상위 k명을 선별상을 받을 사람 중 가장 낮은 점수(커트라인)을 출력입력값응시자의 N(1 ≤ N ≤ 1000), 상 받는 사람의 수 k(1 ≤ k ≤ N)각 학생의 점수 $x$ (0 ≤ $x$ ≤ 10000)한 줄에 공백을 주고 주어짐.출력값상을 받는 커트라인 점수📌 코드 설계하기해결 아이디어점수 리스트를 내림차순으로 정렬k-1번 인덱스를 가진 점수 출력📌 정답 코드n, k = map(int, input().split())arr = list(map(int, input().split()))[:n]arr.sort(reverse=True)# print(arr)print(arr[k-1])시간 복잡도..

https://www.acmicpc.net/problem/1181📌 문제 탐색하기시간 제한이 1초니까 최대 2중 for문까지만 가능하다.반에 있는 학생 수 n 입력으로 주어지고이름, dd, mm, yyyy가 주어져서 나이 가장 적은 사람과 가장 많은 사람의 이름을 출력하는 것이군!각각 하나를 배열로 저장하려면 2차원 배열이어야하는데 다른 방법없나? + 입력 받을 때마다 가장 나이가 많은 사람과 적은 사람을 저장할 수 없나?날짜가 거꾸로 주어져 있으니까 yyyymmdd로 바꿔서 저장하고 int로 바꿔서 매턴마다 비교해서 이름 저장해야겠다!📌 코드 설계하기입력 n 받고for문 돌면서 입력 받을 때 split()으로 받는다. 그리고 다시 date라는 변수에 yyyymmdd를 저장한다.매 생일이 입력될 때마..