본문 바로가기

BaekJoon 10

[백준,Python]15649번 N과 M (1)(Backtracking) 이런 유형의 탐색 문제를 만났을 때,가장 먼저 모든 경우의 수를 다 계산해야 풀 수 있는 가를 생각해본다.그렇지 않다면 함수로 조건문을 사용하여 빠르게 탐색않해도 될 부부을 정의할 수 있는 방안이 무엇인지 생각한다.예를 들어, 이 문제에서는 중복된 수열에 대해서는 탐색하지 않아도 된다. 실제로 수열의 크기가 커진다면 굉장히 Critical 해질 수 있는 부분이다. ( 1 1 2 3 4 5 6 7 8 ...) 또한 사전 순으로 증가하는 순서로 출력하는 부분에서 탐색 범위가 한정되었다. Brute Force 로 접근할 경우,수열의 크기가 커질 경우,  가능한 모든 조합을 찾고 그 중에서 필터링하는 방법은 시간이 굉장히 오래 걸리고 비효율적이다. 따라서 처음 빈 수열을 입력 받아 , 조건이 맞을 때 출력을 하.. 2024. 5. 11.
[백준,Python]11651번 좌표 정렬하기 2(Sort) 처음 문제를 풀 때, 생각 없이 아래와 같이 Bubble Sort로 접근하였다. import sysinput = sys.stdin.readlinenum = int(input())s_list = []for i in range(num): N,M = map(int, input().split()) s_list.append([N,M])c = 0 while c s_list[c+j][1]: s_list[c], s_list[c+j] = s_list[c+j], s_list[c] c += 1for k in s_list: print(k)하지만 Bubble Sort 방식으로 접근하면 O(n^2) 시간 복잡도를 가진다. 문제에서 점의 개수(N)이 최대 100,000이라고 주어졌으.. 2024. 5. 6.
[백준,Python]7576번 토마토(Graph Search/BFS, 시간초과 해결) [백준,Python]7576번 토마토(Graph Search/BFS) www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 테스트 케이스들을 모두 통과하도록 코드를 짰지만 , 반복문이 많이 들어가서 불안했는데 '시간초과'가 발생하였다. 시간초과가 발생했던 코드와 개선하여 효율적으로 짠 코드를 비교해가며 이번 문제를 설명하려 한다. 1. 처음 코드( 시간 초과) import sys input = sys.stdin.readline m,n = map(i.. 2021. 2. 21.
[백준,Python]15903번 카드 합체 놀이(Greedy) [백준,Python]15903번 카드 합체 놀이(Greedy) www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 이번 문제의 알고리즘은 Greedy이고, 1. 처음 푼 풀이와 2. 효율적인 풀이를 비교하며 설명하려고 한다. 1. 처음 푼 풀이 import sys input = sys.stdin.readline a,b = map(int, input().split()) card = list(map(int,input().spli.. 2021. 2. 19.
[백준,Python]16953번 A->B(Greedy) [백준,Python]16953번 A->B(Greedy) www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 이번 문제는 빠른 시간안에 문제 해결을 하였지만, 시간 초과 문제로 여러가지 고민을 하게 만들었던 문제이다. 문제 해결 알고리즘은 B를 처음에 10으로 나눈 나머지가 1인 것 체크하고 다음으로 2로 나눈 나머지가 0 인것들을 체크하여 b를 계속 수정하여 A에 도달하게 만들도록 구현하였고, 첫번째 코드는 시간초과, 두번째 코드는 그 문제를 해결한 코드이다. 처음 코드(시간초과) import sys input = sys.stdin.readline().strip a,b = map(int.. 2021. 2. 12.
[백준,Python]1003번 피보나치 함수(DP,dynamic programming) 1003번 피보나치 함수(DP)문제 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 테스트 케이스 수를 받고, 피보나치 함수를 실행했을 때 Fib(0)과 FIb(1), 0과 1이 몇 번 호출되는지 출력하는 문제입니다. 일단, 다른 문제들에서는 그렇게 시간 제한에 대한 제약이 없었는데, 이번 문제에서는 확실히 0.25초(감이 잘 안잡히긴 하지만) 줄어들었습니다.. 문제에서 요구하는 바가 확실히 , '이러이러한 식으로 풀면 컴파일 시간이 오래 걸리기에 풀지 마라'라고 정의 해 둔 것으로 느껴집니다. 일단 그런 것 상관없이 설마 시.. 2020. 8. 19.

티스토리툴바