본문 바로가기

코딩테스트46

SQL SQL을 풀면서 사용했던 팁들을 정리하자. 1. DATE_FORMAT(원하는컬럼, "%Y-%M-%D") DATE의 FORAMT이 시간이나 년도까지 나와있다면, 이를 간단하게 년도,달,일로 변경하여 준다. 2. MONTH(DATE컬럼), YEAR(DATE컬럼) DAY도 있다. 해당 컬럼의 달과 년 값을 비교할때 사용한다. 3. 모든 쿼리 이후 결합은 UNION ALL을 사용하자. JOIN은 쿼리 이후 결합으로 보기는 힘들다. 이를 조심하자. 서브쿼리 서브쿼리 시 주의 할 점 1. HAVING에서 집계함수 사용시, SELECT에서 묶인 후에 각 행마다 다른 속성을 사용할 수 없다. 2. 서브쿼리는 WHERE절에서 = 로 비교시 1개의 COLUMN밖에 비교할 수 없다. 2개이상을 원할때는, IN을 사용하자. .. 2024. 3. 13.
프로그래머스로 풀이 사이트 변경 기존, 각 문제별 풀이를 진행하기 위해 백준에서 코딩테스트를 진행하였는데, 이제 조만간 찾아오게 될 실전 코딩 테스트를 위해 , 이 환경을 변경하였다. 이로 인한 주의사항을 정리하자 1. input을 넣을 필요가 없다. 기존 백준에선 직접 input을 넣어주어야 했는데, 프로그래머스에서는 이가 주어졌다. 그러므로 input을 넣을 필요가 없고, sys를 import 하여 시간을 단축시키는 tip을 사용할 수 없게 되었다. 2. print도 할 필요가 없다. def solution안에 있는 return의 값으로만 출력이 정해지므로, 따로 출력을 진행할 필요가 없다. 3. DFS,BFS시 GLOBAL보단 모든 내용을 매개변수로 받는것이 좋아졌다. import sys sys.setrecursionlimit(1.. 2024. 3. 13.
BFS/DFS 다시.. 백준 6118 결국 돌아왔다.. BFS로. import sys from collections import deque N,M = map(int,sys.stdin.readline().split()) graph = [ [] for _ in range(N+1) ] for i in range(M) : a,b= map(int,sys.stdin.readline().split()) graph[a].append(b) graph[b].append(a) #간곳이면 0 처리 visited = [0] * (N+1) def BFS(x): q= deque() q.append(x) visited[x] = 1 while q: comefrom = q.popleft() for i in graph[comefrom]: if visited[i.. 2024. 3. 6.
TREE 관련 문제 먼저, BINARY TREE에 대한 개념을 잡고 가자. 비선형의 자료구조로써. ROOT -> 단말노드 등의 구조를 가진다. 왼쪽의 값보다는 부모의 값이 크고, 오른쪽보단 부모의 값이 작다. 자료구조의 형태는 이해했으나, 이를 어떻게 활용하는지, import heapq, heapq.heappush(array,50)혹은 heappop처럼 활용하는지 보도록 하자! 백준 11725 import sys sys.setrecursionlimit(1000000) N = int(sys.stdin.readline()) Nlist =[[] for _ in range(N+1)] for i in range(N-1): a,b=list(map(int,sys.stdin.readline().split())) Nlist[a].appen.. 2024. 3. 3.
dp - 심화 2 백준 1793 import sys dp = [ 0 for _ in range(251)] dp[0] = 1 dp[1] = 1 dp[2] = 3 for i in range(3,251) : dp[i] = dp[i-1] + (dp[i-2]*2) while(True) : try : N= int(sys.stdin.readline()) print(dp[N]) except: break 2*N을 채우는 방법은, dp[i-1] (전 거를 채우는 방법 + 세로로 한줄) + dp[i-2]*2(3개가 아니라 2개인 이유는, 다 세로인 경우는 앞에 포함된다. 로 쉽게 풀었다. 자꾸 java와 혼동하여 try catch로 하는데, try : except:임을 기억하자. 백준 1003 import sys dp = [0] * 41 d.. 2024. 2. 27.
큐 (심화편) 백준 11279 import sys N = int(sys.stdin.readline()) answerqueue = [] for i in range(N) : comein = int(sys.stdin.readline()) if comein == 0 : if len(answerqueue) == 0 : print(0) else: answerqueue.sort() print(answerqueue.pop()) else : answerqueue.append(comein) Queue를, list를 활용해서 구현하였다. 다만 이때 시간 복잡도가 N*O(NLOGN)으로써 , 1000000000000정도가 된다. (N제약이 100000) 즉, 정렬을 따로 하지 않고도, 최대나 최소를 얻어낼 수 있는 자료구조를 사용하는 것이.. 2024. 2. 26.
분할 정복 (쿼드 트리) 백준 1992 import sys N = int(sys.stdin.readline()) Narr = [] for i in range(N) : Narr.append(list(map(int,sys.stdin.readline().strip()))) def DFS(x,y,size) : global answerarr color = Narr[x][y] for i in range(x,x+size) : for j in range(y,y+size) : if Narr[i][j] != color: print("(",end= "") DFS(x,y,size//2) DFS(x,y+size//2,size//2) DFS(x+size//2,y,size//2) DFS(x+size//2,y+size//2,size//2) print(")".. 2024. 2. 25.
그리디 알고리즘 경주마같은, 상남자 같은 문제라고 생각하면 개념이 쉽다. 문제에서 생각했던 것처럼, 동전으로 값을 맞출때 가장 큰 금액부터 넣으면 되는 경우 이다 . 가장 큰 값의 동전부터 , 지금 최선인 것부터 일단 진행하는 것이다. 어떻게 최적의 해가 될 수 있을까? 당연히, 당상 최적이 항상 전체의 최적은 아니다 . 선택의 조건 ? 1. 현재 선택이 이후 선택에 영향을 주지 않는다. a->b->c로 갈때, a->b로 어떤 비용으로 가든, b->c로 가는데 영향을 주지 않는다 2. 부분의 최적해를 모으면 전체의 최적이 된다. a->c까지의 최적해는, a->b+b->c의 최적이된다. 백준 11047 import sys N,K = map(int,sys.stdin.readline().split()) coinlist = [.. 2024. 2. 21.
DP2 - 수열의 값을 계산하기 백준 11659 import sys N,M = map(int,sys.stdin.readline().split()) Nlist = [0]+list(map(int,sys.stdin.readline().split())) for i in range(M) : answerlist = list(map(int,sys.stdin.readline().split())) sumnum = 0 for j in range(answerlist[0],answerlist[1]+1) : sumnum = sumnum+Nlist[j] print(sumnum) N,M이 1000000이 되며, 이로 인해 시간복잡도가 거의 O(100000000000)일 것으로 예상된다. 이는 당연히 시간제한 1초에게 걸릴 것이다. 그래서 풀이를 변경하였다 . N.. 2024. 2. 20.
DP 재 개념 DP가 너무 어려워 개념을 재정리하겠다. DP는 기본적으로, 모든 조합을 만들때, 계산을 줄이기 위함이다. 73824, 73875 등등 DFS의 모든 총합을 구하는 문제일때는 원하는 배열의 DP[I][J]의 값이 DP[I-1][J]에 입력받은 배열 array[i][j]를 더한값을 담으면 최대의 값을 구할 수 있다. 이렇게 구하면, 이전 행만 활용해 이번행을 연산할 수 있고, 그 시작점은 구하지 않아도 된다. *즉, 다음 행이 이전 행의 값 계산을 포함한다. 연산을 기억해놓고 푸는 것이다 1) DFS/BFS로 풀 수 있지만 N이 너무 크다 2) 중복적인 연산이 일어났을때 3) 시간제약이 많을때 DP는 정말 많은 풀이를 해야 한다. 특히, DP와 같은 나만의 연산 정보를 담을 것을 담아서 , 풀이를 진행하는.. 2024. 2. 12.

티스토리툴바