백준 알고리즘 - 1074 - Z
2021. 8. 22. 21:38
⏰ 코딩테스트/백준 알고리즘
이 문제는 주어지는 입력값이 매우 크고, 제한 시간이 짧기 때문에 리스트를 만들어서 숫자를 나열한 후에 (r, c)에 있는 숫자를 출력하는 방식으로는 통과할 수 없다. 따라서 단순 구현식으로 이중리스트를 만드는 것이 아니라, 규칙을 찾아서 재귀함수를 통해 숫자를 출력해주는 것이 옳은 방법이다. def solve(n, x, y): global result if n == 2: if x == r and y == c: print(result) return # 현재의 함수에서 빠져 나와라 result += 1 if x == r and y + n/2 == c: print(result) return result += 1 if x + n/2 == r and y == c: print(result) return resul..
백준 알고리즘 - 2747 - 피보나치 수
2021. 8. 22. 17:27
⏰ 코딩테스트/백준 알고리즘
풀이 def fibo(n): if n == 0: return 0 elif n== 1: return 1 else: return fibo(n-1) + fibo(n-2) n = int(input()) fibo(n) 단순 재귀 함수로 구현하면 틀린다. 재귀의 한계 때문이다. 필요 없는 계산은 하면 안된다. 호출이 되는 횟수는 깊이 들어갈수록 2배씩 늘어난다. 즉, 시간복잡도는 O(2^n) 이 된다. def fibo(n): cache = [0] * (n+1) cache[0] = 0 cache[1] = 1 for i in range(2, n+1): cache[i] = cache[i-1]+cache[i-2] return cache[n] n = int(input()) fibo(n) DP로 풀어도 시간 초과가 나온다. ..
백준 알고리즘 - 10989 - 수 정렬하기 3
2021. 8. 21. 17:14
⏰ 코딩테스트/백준 알고리즘
문제풀이 횟수 : 문제 풀이 핵심 아이디어 파이썬은 대략 1초에 약 2천만개까지 연산을 수행할 수 있다. 따라서 파이썬의 기본 정렬 라이브러리를 사용하면 이 문제를 풀 수 없다. 시간 복잡도가 O(N)의 정렬 알고리즘을 이용해야 하고, 데이터의 개수가 최대 1천만개 이므로 기본 정렬 라이브러리를 사용하면 안된다. 또한 수의 범위가 1~10000 이고, 범위가 작으므로 계수정렬(Counting sort)을 이용할 수 있다. 유의사항 데이터의 개수가 많을 때 파이썬에서는 sys.stdin.readline() 으로 읽어야 한다. input()함수에 비해서 빠르기 때문이다. 코드 import sys n = int(sys.stdin.readline()) arr = [0]*10001 for i in range(n)..
백준 알고리즘 - 11650 - 좌표 정렬하기
2021. 8. 21. 16:26
⏰ 코딩테스트/백준 알고리즘
문제 풀이 핵심 아이디어 (x좌표, y좌표)를 입력 받은 뒤, x좌표 y좌표 순서대로 차례대로 오름차순 정렬한다. 파이썬의 기본 정렬 라이브러리는 기본적으로 튜플의 인덱스 순서대로 오름차순 정렬한다. 따라서 단순히 기본 정렬 라이브러리를 이용하면 (key 속성 설정 없이) 저절로 정렬된다. 코드 n = int(input()) arr = [] for _ in range(n): x, y = map(int, input().split()) arr.append((x, y)) arr = sorted(arr) for i in arr: print(i[0], i[1])
백준 알고리즘 - 10814 - 나이순 정렬
2021. 8. 21. 15:56
⏰ 코딩테스트/백준 알고리즘
튜플의 기본 of 기본 정렬의 기본 of 기본 코드 n = int(input()) arr = [] for _ in range(n): data = input().split() arr.append((int(data[0]), data[1])) # 튜플 형태 arr = sorted(arr, key=lambda x:x[0]) # 튜플의 (첫번째, 두번째)중 첫번째를 기준으로 정렬 for i in arr: print(i[0], i[1]) lambda 인자 : 표현식 sorted() 함수 sorted(정렬할 데이터) sorted(정렬할 데이터, reverse 파라미터) sorted(정렬할 데이터, key 파라미터) sorted(정렬할 데이터, key 파라미터, reverse 파라미터) sorted 함수는 파이썬 내장..
백준 알고리즘 - 1427 - 소트인사이드
2021. 8. 20. 18:32
⏰ 코딩테스트/백준 알고리즘
접근법 코드 N = input() for i in range(9, -1, -1): for j in N: if int(j) == i: print(i, end='') 다른 풀이 N = input() N = [int(n) for n in N] ans = sorted(N, reverse=True) for i in ans: print(i, end="")
백준 알고리즘 - 2750 - 수 정렬하기
2021. 8. 20. 17:49
⏰ 코딩테스트/백준 알고리즘
코드 1. 삽입 정렬 N = int(input()) data = [] for _ in range(N): a = int(input()) data.append(a) for stand in range(len(data)-1): lowest = stand for i in range(stand+1, len(data)): if data[lowest] > data[i]: lowest = i data[stand], data[lowest] = data[lowest], data[stand] for i in data: print(i) 2. 버블 정렬 N = int(input()) data = [] for _ in range(N): a = int(input()) data.append(a) for i in range(len(da..
백준 알고리즘 - 5397 - 키로거
2021. 8. 19. 11:17
⏰ 코딩테스트/백준 알고리즘
접근법 문자열의 크기가 1,000,000 이므로 단순하게 구현하라는대로 구현하면 문제를 풀 수 없다. O(n) 의 선형시간 안에 문제를 풀 수 있는 알고리즘을 짜야 문제를 해결할 수 있다. 스택 풀이 코드 testcase = int(input()) for _ in range(testcase): arr = list(str(input())) stack1 = [] stack2 = [] for i in range(len(arr)): if arr[i] == "": if len(stack2) != 0: stack1.append(stack2.pop()) elif arr[i] == "-": if len(stack1) != 0: stack1.pop() else: stack1.append(arr[i]) print(''.j..
백준 알고리즘 - 1966 - 프린터 큐
2021. 8. 18. 11:24
⏰ 코딩테스트/백준 알고리즘
코드 test_case = int(input()) for _ in range(test_case): n,m = map(int, input().split()) queue = list(map(int, input().split())) queue = [(i, index) for index, i in enumerate(queue)] # 튜플 형태로 # [(2,0), (1,1), (4,2), (3,3)] count = 0 while True: if queue[0][0] == max(queue, key=lambda x: x[0])[0]: #맨앞==현재큐의 가장큰중요도 count += 1 if queue[0][1] == m: print(count) break else: queue.pop(0) else: # 맨앞이 현재 ..
백준 알고리즘 - 1874 - 스택 수열
2021. 8. 17. 15:52
⏰ 코딩테스트/백준 알고리즘
추천 문제 풀이 시간 : 30분 틀린 코드 n = int(input()) stack = list() ans = list() num = 1 for i in range(1,n+1): p = int(input()) for j in range(num, n+1): if not stack or stack[-1] != p: # 비어있거나 다를때 stack.append(j) num += 1 ans.append("+") else: # 같을 때 stack.pop() ans.append("-") break print(ans) 틀린 이유 for문과 while 문을 구별해서 잘 쓸 줄 알아야 한다. 카운트 하는 변수가 여러개가 있고, 개별로 늘려갈 때 꼭 for j in range(..) 로 쓰는 방법만 있는 것이 아니라 wh..
백준 알고리즘 - 2798 - 블랙잭
2021. 8. 16. 22:25
⏰ 코딩테스트/백준 알고리즘
10 500 93 181 245 214 315 36 185 138 216 295 접근법 카드의 개수(N)와 넘지 않는 양의 정수(M) 입력 받기 카드 입력 받기 (card) 카드 3장 뽑기 (All) 3장의 합이 500보다 작은 것들 중 가장 큰 것 추출 for 문을 3번이나 써야해서 망설였다. 내 풀이 N, M = map(int, input().split()) arr = list(map(int, input().split())) sum = list() ans = list() for i in range(N-2): a = arr[i] for j in range(i+1, N-1): b = arr[j] for k in range(j+1, N): c = arr[k] sum.append(a+b+c) sum.sort..
백준 알고리즘 - 2920 - 음계
2021. 8. 16. 21:09
⏰ 코딩테스트/백준 알고리즘
헤맨 이유: 하나 하나 다 비교하고, 비교하는 와중에 "ascending"이나 "descending" 을 출력하려고 했다. ascend = True, descend = True 로 미리 설정한 후 그 값이 거짓이면 False로 바꿔주고 비교가 다 끝나고 나서 True나 False 값을 체크해서 출력해주면 된다. if arr[0] < arr[1] < arr[2] < arr[3] < arr[4] < arr[5] < arr[6] < arr[7] : print("ascending") 을 만드는 코드를 짤 수 있었으면 더 좋았지만 ascend 와 descend를 True로 정해놓고 조건에 맞는다면 False로 바꿔주는 방법도 굉장히 좋은 것 같다. 내 풀이 arr = list(map(int,input().spli..
백준 알고리즘 - 1000 - A+B
2021. 6. 28. 22:05
⏰ 코딩테스트/백준 알고리즘
a,b = [int(x) for x in input().split()] print(a+b) 띄어쓰기로 입력 받아서 x에 넣어 준다. 그리고 int 형으로 바꾸어주고 리스트 형태로 저장한다.
백준 알고리즘 - 9663 - N Queen
2021. 3. 14. 15:45
⏰ 코딩테스트/백준 알고리즘
문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 복사 8 예제 출력 1 복사 92 코드 N = int(input()) check = [0] * N answer = 0 def queen(x): # 현재 위치에서 윗줄에 공격할 수 있는 퀸이 존재하는지 확인 for i in range(x): if check[x] == check[i] or abs(check[x] - check[i]) == x - i: return 0 return 1 d..
백준 알고리즘 - 15651 - N과 M (3)
2021. 2. 27. 00:27
⏰ 코딩테스트/백준 알고리즘
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 코드 N, M = map(int, input().split()) out = [] def solve(depth, N, M): if depth == M: print(' '.join(map(str, out))) return for i in rang..