파이썬

[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결 S2 | 그래프, BFS(DFS) 단순한 그래프 문제였는데 전부다 시간초과 발생.... 다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공) 풀이방법은 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다) 모든 노드에 대해서 BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다. 가장 높은 카운트의 노드들을 출력한다. 다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지... 💻소스 코드 import sys from collections import defaultdict from collections import deque def bfs(start): q = deque([start]) visited = [0] * (N ..

[python] 백준 - 10773. 괄호

🤔문제 해결 S4 | 스택 너무 기본적인 스택문제라서 포스팅을 안하려고 했지만 input 과 sys.stdin.readline 에 대해서 말하고 싶어서 포스팅했다. 위의 사진을 보면 시간에서 큰 차이가 있을 것이다. 첫번째는 sys.stdin.readline을 사용하고, 두 번째는 input을 사용했다. 엄청난 시간차이가 나타난다. 이렇게 한줄 한줄 읽는 식으로 인풋값을 받을 때는 첫번째 방법을 사용하는 게 훨씬 빠르다. 속도 비교 하기 [python] input, sys.stdin.readline 📗 파이썬 알고리즘 풀 때!! 입력 속도 문제 🔵 input vs sys.stdin.readline 천만개의 숫자를 한줄한줄 입력받을 때의 속도 입력 방법 속도 input() 12.5초 sys.stdin.re..

[python] 백준 - 2512. 예산

🤔문제 해결 S3 | 이분탐색 이분 탐색의 기본문제 이분탐색이란? 탐색 부분을 두 부분으로 분할해서 답을 찾는 과정이다. 1부터 10까지 값이 있다고 가정했을 때 7이란 값을 찾아보자 최소는 1이고 최대는 10이다. 절반으로 나누면 5인데 운이 좋아서 5가 맞으면 정답, 하지만 찾는 값은 7이므로 정답이 아니다 크기를 비교해서 찾는 값이 5보다 작으면 최대를 줄이고, 찾는 값이 5보다 크면 최소를 늘린다. 찾는 값이 5보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 그대로 10이다. 절반으로 나누면 8 찾는 값은 8보다 작으므로 최대를 줄인다. 최소는 6 최대는 절반-1이다. 절반으로 나누면 6 찾는 값이 6보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 7이다. 절반으로 나누면 7이므로 정답! ..

[python] 백준 - 1874. 스택 수열

🤔문제 해결 S2 | 스택 수열 스택을 이용한 문제 스택에 값이 있고 스택의 마지막 값이 뽑아야 하는 값이면 pop 그렇지 않을 때 넣어야할 숫자가 n보다 작으면 push 둘 다 아니면 break 스택에 계속 넣는 것을 먼저 생각하는 것보다 스택에서 값을 빼는 걸 먼저 생각해야 한다. ( 연속으로 뽑을 수 있기 때문 ) 💻소스 코드 import sys input = sys.stdin.readline numbers = [] n = int(input()) for _ in range(n): numbers.append(int(input())) stack = [] result = [] number = 1 idx = 0 while idx < n: if stack and stack[-1] == numbers[idx]..

[python] 프로그래머스 - 쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌1)

🤔문제 해결 압축문제 백준에서도 비슷한 문제를 풀어본적이 있다. 리스트를 실제로 자르지 말고 나뉘는 인덱스만 구해서 해결하는게 좋다. 인덱스를 구할 때는 네모의 시작점의 위치만 구한다. 거기에 + 네모의 길이만큼 해주면 네모를 완성시킴 시작점을 기준으로 하면 위의 경우는 0, 0 그리고 크기는 8이다. 다음 4가지는 0, 0, 4 0, 4, 4 4, 0, 4 4, 4, 4 다음 네모는 크기를 절반으로 나누고 x에 더하거나 y에 더하거나 x와 y 둘다 더해서 시작값을 만든다. 다음은 이 네모가 모두 같은 숫자인지 판별하는 것인데 네모중 하나의 값을 초기값으로 잡고 네모안의 값을 하나씩 비교해가면서 초기값과 다른게 하나라도 있으면 압축할 수 없으므로 또 그 네모를 잘라준다! 💻소스 코드 def solutio..

[python] 프로그래머스 - 3진법 뒤집기 (월간 코드 챌린지 시즌1)

🤔문제 해결 3진법으로 만든다. 뒤집지마라 stack구조로 문자열을 쌓으면 저절로 뒤집은 형태가 나온다. 10진법으로 바꿔준다. 문자열은 앞에서부터, 3의 n승은 뒤에서부터 만들어준다. 💨 실제 대회시간 때 급하게 풀다가 n 이 3보다 작을 때 처리를 안해줘서 한두문제 틀리고 넘어갔다. ( 시간 깜빡하다가 늦게 입장 함😂 ) 💻소스 코드 def solution(n): answer = 0 # 3진법 mok = 0 nmg = 0 number = '' while True: mok = n // 3 nmg = n % 3 number += str(nmg) if mok < 3: number += str(mok) break n = mok print(number) # 10진법으로 바꾸기 leng = len(number)..