본문 바로가기
반응형

코딩테스트/파이썬68

[백준] [다익스트라] 최단경로 1753 (파이썬) 문제접근 특정한 지점(start) 값이 주어지고 최단경로를 구하는 문제이므로 다익스트라 알고리즘을 적용하여 문제를 푼다. 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘 $O(ElogV), O(V^2)$ 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출 seongbindb.tistory.com 스케치 코드 # 최단 경로 , 다익스트라 알고리즘 사용 import heapq import sys input = sys.stdin.readline .. 2021. 3. 17.
[백준] 단지번호붙이기 2667 (파이썬) 문제설명 기본적인 아래와 같은 DFS 문제와 거의 유사하지만 추가해야 하는 조건이 있다. 2021.03.14 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] [우선탐색] DFS와 BFS 1260 (파이썬) [백준] [우선탐색] DFS와 BFS 1260 (파이썬) 개념 2021.03.07 - [Algorithm & Data structure] - [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) [알고리즘] DFS와 BFS (깊이 우선탐색과 너비 우선탐색) DFS (깊이 우선탐색) 그래프에서 깊은 부분을.. seongbindb.tistory.com 스케치 코드 # 단지 번호 붙이기 def dfs(x,y): global temp if x = n or y = n:.. 2021. 3. 16.
[백준] [분할정복] 쿼드트리 1992 (파이썬) 문제설명 아래 색종이 만들기 문제와 아주 유사한 문제였다. 부분적인 조건만 추가해서 DFS 방식으로 풀어주면 된다. 2021.03.15 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 색종이 만들기 2630 (파이썬) [백준] 색종이 만들기 2630 (파이썬) 코드 # 색종이 만들기 # 쿼드 트리 문제 # 처음 리스트를 쪼개서 작은 리스트를 만드려고 했는데 이방식은 어리석은 방식이었다. 전체에서 범위만 제한해서 원하는 부분에 접근할 수 있다. import s seongbindb.tistory.com 코드 # 쿼드트리 import sys def quadTree(x,y,size): # 전체 갯수를 센다. color = matrix[x][y] if (size == 1): pr.. 2021. 3. 16.
[백준] [DP] 가장 긴 바이토닉 부분 수열 11054 (파이썬) 스케치 코드 최장 증가 부분수열 (LIS)에 대한 이해가 필요하다. # 가장 긴 바이토닉 부분 수열 # LIS 문제 n = int(input()) arr =list(map(int,input().split())) dpH = [1 for _ in range(n)] # 증가하는 부분 dpL = [1 for _ in range(n)] # 감소하는 부분 for i in range(n): for j in range(i): if arr[i] > arr[j]: dpH[i] = max(dpH[i], dpH[j]+1) arr.reverse() # 가장 긴수열을 용이하게 구하기 위해서 뒤집니다. for i in range(n): for j in range(i): if arr[i] > arr[j]: dpL[i] = max(d.. 2021. 3. 16.
[백준] 요세푸스 문제0 11866 (파이썬) 스케치 코드 기본적으로 큐를 활용해서 문제를 풀면 되지만 K번째 값을 뽑는 도중 Q가 K보다 작아지게 될 때를 유의하여 처리하여야 한다. Q < K 작은 구간은 나눗셈으로 인덱스를 뽑아서 구현하였다. 출력양식 공부가 필요해보인다. 2021.03.18 - [Programming/Python] - [파이썬] print() 원하는 양식으로 출력하기 (백준 11866 요세푸스 문제) [파이썬] print() 원하는 양식으로 출력하기 (백준 11866 요세푸스 문제) 출력 원하는 방식으로 출력해야 할 때 필요한 코드들이다. 백준 11866 요세푸스 문제를 풀 때 막힌 부분이 출력이어서 정리한다. 2021.03.16 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 요세 seongb.. 2021. 3. 16.
[백준] 잃어버린 괄호 1541 (파이썬) 스케치 코드 문제를 잘 이해하지 못하였다. 0부터 시작할 수 있다라는 문구가 003 002가 될 수 있다는 말로 전혀 생각못했다. 백준 문제풀이 예제가 너무 불친절 한 것 같다... # 잃어버린 괄호 # 최소로 만드려면 -가 등장하면 괄호를 열고 -가 또 등장하면 괄호를 닫는다. # 파이썬 eval() 사용한다. #수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. # 03 04 05 설명이 부족하다... # 실패코드 001 002 등을 고려하지 않음 expression = list(input()) check = True # (를 입력해야 하는 상태 for i in range(len(expression)): if expression[i] == '-': if check: e.. 2021. 3. 16.
[백준] [브루트포스] 분해합 2231 (파이썬) 문제접근 범위가 100만으로 제한된 다는 것은 많은 탐색을 요구할 때 보통 100만으로 주어진다. 여러 생성자를 담아서 그 중에서 작은 값을 구하는 것 코드 # 분해합 n = int(input()) divide_list = [0,1,10,100,1000,10000,100000,1000000] # 연산을 할 배열을 미리 생성한다. arr = [] # 생성자 리스트 for i in range(1,n): # 1부터 자기보다 작은 수를 탐색한다. next_num_list = [i] # 생성자를 만들 리스트 temp_num = i # 계산을 수행할 번호 for j in range(len(str(i)),0,-1): # ex) 100이면 1의자리 10의자리 100의자리 총 3번 탐색해야하므로 위와 같이 범위를 설정한.. 2021. 3. 15.
[백준] [조합] 블랙잭 2798 (파이썬) 문제접근 조합의 합을 가지고 원하는 target값에 가장 가까우면서 target값 보다 작은 값을 구해주면 된다. itertools 라이브러리를 사용하면 보다 쉽게 풀 수 있다. 2021.03.15 - [Algorithm & Data structure] - [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutati seongbindb.tistory.com 코드 import sys from itertoo.. 2021. 3. 15.
[백준] [수학] 터렛 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.
반응형

티스토리툴바