본문 바로가기

PYTHON 13

[백준,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]PEP-8 코딩 스타일 [파이썬, Python]PEP-8 코딩 스타일 코딩을 하면서 좋은 코딩 습관, 스타일을 갖추는 것이 중요하다는 생각이 들었다. 그래서 기존 코딩 스타일을 버리고, 파이썬 프로그래머들의 일반적인 코딩 스타일인 'PEP-8' 스타일로 코딩 습관을 갖춰보려고 중요한 내용을 정리해 보려고 한다. www.python.org/dev/peps/pep-0008/ PEP 8 -- Style Guide for Python Code The official home of the Python Programming Language www.python.org 이 링크를 통해 들어가보면 PEP 8에 대한 자세한 소개가 있다. "PEP-8"스타일에 대한 장점 -이 코딩 스타일을 적용하는 것은 자신의 코드를 명료하게 할 뿐만 아니라, .. 2020. 12. 23.

티스토리툴바