본문 바로가기
반응형

백준61

[백준] [수학] 터렛 1002 (파이썬) 문제 접근 고등학교 때 배운 수학 중 원의 특성에 대해 알고 있어야 이 문제를 풀 수 있다. 처음엔 단순이 거리로 비교할 수 있을 것이라 생각하고 피타고라스 정리로 접근하여서 실패하였으나 원으로 바꿔서 풀이에 성공하였다. 스케치 코드 # 터렛 import sys, math T = int(sys.stdin.readline().rstrip()) for _ in range(T): data = list(map(int, sys.stdin.readline().rstrip().split())) # x1,y1,r1,x2,y2,r2 jo = data[0:3] baek = data[3:] # 조규현 백승환 터렛 근무 직원 # 이석원 (명령자) 조규현 백승환에게 류재명의 위치를 찾으라 # 조규현 좌표, 류재명과의 거리 (x.. 2021. 3. 15.
[백준] [DP] 계단오르기 2579 (파이썬) 문제설명 dp 테이블을 무엇으로 설정할지 정하여 점화식을 구하는 것이 관건인데 스스로 풀지 못하였다. 잘못접근 한뒤로 구글링 해서 올바르게 접근하였다. 스케치 코드 # 계단오르기 import sys n = int(sys.stdin.readline().rstrip()) score = [0] # 0 층 점수 0을 넣어주기 for _ in range(n): score.append(int(sys.stdin.readline().rstrip())) # 1층부터 ~ N층까지 점수 넣어주기 dp = [0 for _ in range(n+1)] # 값이 0인 dp 테이블 초기화 dp[0] = score[0] dp[1] = score[1] if n >= 2: #index 오류 안되게 조건 추가 dp[2] = max(scor.. 2021. 3. 15.
[백준] [조합] N과 M(2) 15650 (파이썬) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 문제 설명 nCm을 뽑아서 출력해주면 된다 (조합) itertools 라이브러리를 사용하면 간단하게 구할 수 있다. 2021.03.15 - [Algorithm & Data structure] - [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 .. 2021. 3. 15.
[백준] 색종이 만들기 2630 (파이썬) 코드 # 색종이 만들기 # 쿼드 트리 문제 # 처음 리스트를 쪼개서 작은 리스트를 만드려고 했는데 이방식은 어리석은 방식이었다. 전체에서 범위만 제한해서 원하는 부분에 접근할 수 있다. import sys n = int(sys.stdin.readline().rstrip()) graph = [] for _ in range(n): graph.append(list(map(int,sys.stdin.readline().rstrip().split()))) # 잘라진 하얀색 색종이의 개수와, 파란색 색종이의 개수를 출력한다. w_cnt = 0 b_cnt = 0 # 색종이의 칠해져있는 여부를 검사한다. 1이라면 temp_cnt 를 만들어서 파란색 으로 칠해진 개수를 검사한다. # 만약 칠해져있는 것이 없다면 그것은 하.. 2021. 3. 15.
[백준] [정렬] 통계학 2108 (파이썬) 개념 2020.11.24 - [Algorithm & Data structure] - [알고리즘] 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 정리 [알고리즘] 선택정렬, 삽입정렬, 퀵정렬, 계수정렬 정리 정렬 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨앞에 있는 데이터와 바꾸는 것을 반복한다 시간 복잡도는 O(n^2) 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적합 seongbindb.tistory.com 코드 정렬 시킨 이후에 문제를 풀어야한다. 최빈 값 구현이 까다롭다. # 통계학 분류 # 시간 제한메모리 제한제출정답맞은 사람정답 비율 # 2 초256 MB4349810336847926.622% # 문제 # 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 .. 2021. 3. 14.
[백준] [우선탐색] DFS와 BFS 1260 (파이썬) 개념 2021.03.07 - [Algorithm & Data structure] - [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조( or 재귀함수)를 이용한다 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 seongbindb.tistory.com 스케치 코드 import sys from collections import deque def bfs(graph,start, visited_bfs): q = deque([start]) # 1 visited_bfs[start] = True while q: v = q.po.. 2021. 3. 14.
[백준] [큐,덱] 큐2 18258 (파이썬) 코드 from collections import deque import sys input = sys.stdin.readline def func_queue(s): if 'push' in s: num = int(s[5:]) q.append(num) if 'pop' in s: if not q: print(-1) else: print(q.popleft()) if 'size' in s: print(len(q)) if 'empty' in s: if not q: print(1) else: print(0) if 'front' in s: if not q: print(-1) else: print(q[0]) if 'back' in s: if not q: print(-1) else: print(q[-1]) n = int(in.. 2021. 3. 14.
[백준] [스택] 괄호 9012 (파이썬) 스케치 코드 # 괄호 import sys n = int(sys.stdin.readline().rstrip()) def checkVps(s): q = [] for x in s: if not q: # q가 비어있다. if x == ')': return 'NO' else: q.append(x) else: if x == '(': q.append(x) else: q.pop() if not q: return 'YES' else: return 'NO' for _ in range(n): print(checkVps(sys.stdin.readline().rstrip())) 2021. 3. 14.
[백준] [스택] 제로 10773 (파이썬) (시간 초과 방지 코드) 시간 초과가 안되게 주의 해야한다. 2021.03.14 - [Programming/Python] - [파이썬] 코딩테스트 시간 초과시 해결 방법 sys.stdin.readline().rstrip() 코드 # 제로 import sys input = sys.stdin.readline k = int(input()) st = [] for _ in range(k): num = int(input()) if num == 0: st.pop() else: st.append(num) print(sum(st)) 2021. 3. 14.
[파이썬] 코딩테스트 시간 초과시 해결 방법 sys.stdin.readline().rstrip() 코드 구현을 제대로 한 것 같은데 시간 초과로 통화 못하는 경우가 존재한다. 방법 1 input() 입력값을 빠르게 받을 수 있는 함수로 변경한다. 같은 코드이나 시간이 3초이상 차이나는 것을 확인 할 수 있다. import sys input_data = sys.stdin.readline().rstrip() # 기존 인풋 방식 input_data = input() 방법 2 코드를 python3에서 pypy로 제출한다. 단 시간은 단축하기 위해서 내부적으로 메모리를 많이 잡아먹기 때문에 메모리 초과에 주의해야 한다. 2021. 3. 14.
[백준] [조합] 다리놓기 1010 (파이썬) 스케치 코드 다리가 교차한다는 건 순서를 고려하겠다는 순열이라고 생각하면된다 문제에서는 다리가 교차되면 안된다 하였으니 조합식으로 풀면 된다. itertools 라이브러를 활용해서 풀어 보고 싶었으나 단순 개수를 구하는 문제이므로 시간 초과가 났다. 팩토리얼 함수, 조합 함수를 만들어서 코드를 구현하였다. # 다리 놓기 (조합을 구해야하는데 시간이 0.5초) # 1 itertools 라이브러리 이용 시간 초과실패 # from itertools import combinations T = int(input()) def factorial(n): result = 1 for i in range(1, n+1): result *= i return result def combinations(a,b): result = .. 2021. 3. 14.
[백준] [조합] 이항계수 11050 (파이썬) 코드 이항계수는 조합문제라고 할 수 있다. 이항계수 k 분의 n 인 분수가 있으면 조합 nCk 와 동일하다. # 이항 계수1 # recursion 재귀 에러 난다... def factorial(n): if n 2021. 3. 14.
[백준] 최소공배수 1934 (파이썬) 코드 유클리드 호제법을 사용하여 쉽게 구할 수 있다. 2021.03.14 - [Algorithm & Data structure] - [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 유클리드 호제로 최대 공약수 구하기 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다 최소공배수 = 두 seongbindb.tistory.com # 최소 공배수 # a > b 를 만족해야 한다. def gcd(a,b): if a % b == 0: return b else: gcd(b, a % b) t = int(input()) for _ in range(t): x.. 2021. 3. 14.
[백준] 최대공약수와 최소공배수 2609 (파이썬) 코드 유클리드 호제법으로 최대공약수를 구하면 최소공배수는 쉽게 구할 수 있다. 2021.03.14 - [Algorithm & Data structure] - [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 유클리드 호제로 최대 공약수 구하기 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다 최소공배수 = 두 seongbindb.tistory.com # 유클리드 호제로 최대 공약수 구하기 # 유클리드 호제법 # 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다. # 이때 A와 B의 최대공약수는 B와 R의 최대 공약수.. 2021. 3. 14.
[백준] 약수 1037 (파이썬) 스케치 코드 n = int(input()) arr = list(map(int,input().split())) arr.sort() # 약수가 무작위로 주어질 수 있기 때문에 sort가 필요하다 if len(arr) == 1: print(arr[0] ** 2) else: print(arr[0] * arr[-1]) 2021. 3. 14.
반응형

티스토리툴바