본문 바로가기
반응형

코딩테스트94

[프로그래머스] 기능 개발(level 2) (파이썬) 문제 접근 간단한 문제로 생각했으나 문제를 잘 못 파악한 것이 코드를 잘못작성하는 것으로 이어졌다. 문제파악을 잘하는 것이 중요할 것 같다 # https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 # 내가 푼 것 (1차) from collections import deque import math from collections import deque import math def solution(progresses, speeds): answer = [] q = deque() time = 0 # 누적된 시간을 나타냄 for i in range(len(speeds)): day = math.ceil((100 - progresses[i].. 2021. 5. 10.
[프로그래머스] 주식가격(level 2) (파이썬) 문제접근 스택 큐 유형이며 level2 문제였으나 이중 반복문으로 충분히 풀 수 있을 것 같아 이중반복문으로 구현하였다. 스택 큐 쪽으로는 문제접근 방식이 생각나지 않는다. https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr def solution(prices): answer = [0] * len(prices) for i in range(len(prices)): for j.. 2021. 5. 7.
[백준] 01타일 1920 (파이썬) 문제접근 n에 대한 예시가 여러개 주어진 것으로 봐서 규칙이 있을거라 생각하였다. 피보나치 수열과 동일한 규칙을 찾았고 규칙에 맞게 점화식을 풀면 된다. 스케치 코드 # 수 찾기 import sys input = sys.stdin.readline def binary_search(start, end, target, arr): while start 2021. 3. 19.
[백준] N과 M (1) 15649 (파이썬) 문제 접근 n 개중에서 m개를 뽑는데 순서를 고려해서 뽑는다 = 순열 문제 파이썬 라이브러리를 사용해서 쉽게 풀었다. 2021.03.15 - [Algorithm & Data structure] - [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutati seongbindb.tistory.com 코드 # N과 M from itertools import permutations n,m = map(int,i.. 2021. 3. 19.
[백준] 수 찻기 1920 (파이썬) 문제접근 어떤 수열에서 특정 값이 있는지 없는지를 찾는데 수가 크다면 이진탐색을 고려해 봐야했다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 이진탐색 (이분탐색) # 수 찾기 import sys input = sys.stdin.readline def binary_search(start, end, target, arr): while start 2021. 3. 19.
[백준] 곱셈 2588 (파이썬) 문제접근 1안: 방식은 음 뭔가 복잡하다 2안: 문제 조건이 3자리 자연수를 입력값으로 준다고 명시돼 있으므로 쉽게 풀 수 있다 # 곱셈 a = int(input()) b = input() b = list(b) b.reverse() zero = '' arr = [] for i in b: c = str(a*int(i)) arr.append(c+zero) zero = zero + '0' print(a*int(i)) total = 0 for j in arr: total = total + int(j) print(total) # 2안 # 문제 조건이 3자리 자연수를 준다고 명시돼 있으므로 조금더 쉽게 풀 수 있다. n = int(input()) m = int(input()) m = str(m) print(n * .. 2021. 3. 18.
[백준] [백트래킹] N-Queen 9663 (파이썬) 문제 접근 처음 보는 유형이 었고 공부를 해도 잘 몰라서 유투브 '코드랩' 님의 백트래킹 강의를 참조하였다 백트래킹 기본 개념 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 백트래킹 [알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대 seongbindb.tistory.com 코드 # N - Queen # 참조 코딩랩 import sys input = sys.stdin.readline def queen(row, col): for i in range(row): #.. 2021. 3. 17.
[백준] [다익스트라 알고리즘] 최단경로 1753 (파이썬) 문제접근 주어진 V E의 범위가 큰 편이기 때문에 시간 복잡도를 고려했을 때 다익스트라 알고리즘을 적용해서 풀어야 한다고 파악했다. 또한 특정지점 (주어진 시작점)에서 다른 지점으로 까지 가는 최단 경로를 구하기 때문에 모든 정점에 대해 최단 경로를 알 수 있는 플루이드 워셜 알고리즘 시간복잡도와 문제를 보았을 때 적합하지 않았다. 최단 경로 알고리즘에 대해 정리한 글을 참조하면 도움이 될 것 같다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘.. 2021. 3. 17.
[백준] [다익스트라] 최단경로 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.
반응형

티스토리툴바