728x90 Coding Test26 백준 1920 - 수찾기( Python ) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 가장 기본적인 이진탐색(이분탐색)문제이다. 해당 문제의 경우 100,000밖에 되지않기 때문에 순차탐색으로 풀어도되지만 이진탐색이 훨씬 효율적이므로 이진탐색으로 풀이한다 이진탐색은 기본적으로 정렬이 되어있는 상태여야한다. 재귀함수로 풀이해도되고 반복문으로 풀이해도 무관하다 #반복문으로 풀이 n = int(input()) arr1 = list(map(.. 2023. 1. 4. 백준 1463 - 1로 만들기( Python ) https://www.acmicpc.net/problem/1463 전형적인 dp유형의 문제로 입력값이 1000000개, 백만개로로 적은편이기때문에 더욱이 dp로 풀어야하는 문제임을 알 수 있다. 점화식을 찾아보자 array[1] = 0 array[2] = min(array[1] + 1, array[2//2] + 1) array[3] = min(array[2] + 1, array[3//3] + 1) array[4] = min(array[3] + 1, array[4//2] + 1) array[5] = array[4] + 1 //2와 3으로 나누어 지지 않는 경우 array[6] = min(array[5] + 1, array[6//3] + array[3]) array[7] = array[6] + 1 array.. 2022. 12. 24. 백준 11727 - 2×n 타일링 2 (Python) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 전형적인 dp 문제 dp문제의 핵심은 점화식을 빨리찾는 수 밖에 없는거 같다. 해당 문제는 직접 그리는 방식으로 점화식을 쉽게 찾을 수 있는 것 같다. 점화식 연습을 위해서는 가능한 다양한 문제를 풀어봐야할 것 같다. 1. 입력값이 1000이므로 1001개의 배열을 생성 -> 0번 인덱스는 계산하지 않기 때문 2. 입력값 1, 2는 규칙성을 찾을 수 없으므로 값을 바로 대입 3. 점화식 찾기 n = 2 -> 3 n = 3 ->.. 2022. 12. 19. 백준 17478 - 재귀함수가 뭔가요? https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제는 전혀 어렵지않은데 문자열을 작성하는 점이 조금은 헷갈렸다... 문자열을 연결해야하는 경우 콤마(,) 와 플러스(+)의 경우가 달랐다 콤마는 공백이 자동으로 추가되며 플러스의 경우 공백없이 연결된다 이것 때문에 6번은...제출을 다시함 ㅠㅠㅠ n = int(input()) text1 = "\"재귀함수가 뭔가요?\"" text2 = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지.. 2022. 12. 17. 백준 1439 - 뒤집기 ( Python ) https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 초급 그리디 알고리즘 문제 거스름돈을 거슬러주는 그리디 문제랑 다른경우이다. 문제에서 2가지 경우를 나눠서 구분하므로 알고리즘도 2가지의 경우로 나눠서 짜야한다. 제한 시간 20분 풀이방법 1. 모두 1로 뒤집는 경우 혹은 0으로 뒤집는 경우로 나눠서 계산 후 각각 변수에 저장 2. 1로 뒤집는 경우 -> 첫번째 숫자가 0이면 카운트 + 1 -> 1에서 0으로 바뀔 때 카운트 + 1 3. 0으로 .. 2022. 12. 9. 백준 2217 - 로프 ( Python ) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 예제풀이 n: 2 10 15 2개의 로프가 각각 10 15를 들 수 있음. 10인 로프는 10이 넘어가는 순간 끊어짐 예제의 최대 무게는 20이된다. n: 5 3 7 1 10 5 이런경우에는 줄을 5개를 쓰는 것이 불필요하다 1이 5개인 경우엔 고작 5까지밖에 못들지만 최대가 10이므로 하나를 쓰는게 더 나은 경우다 내림차순으로 정렬해보자 모든 경우의 수를 생각해보면 10 -> 10 7 .. 2022. 12. 1. 이전 1 2 3 4 5 다음 728x90 반응형
