코딩 테스트 (29) 썸네일형 리스트형 이것이 코딩 테스트다 :: 이진 탐색 순차 탐색 시간복잡도 : O(N) N개의 데이터를 차례대로 하나씩 확인하는 방법 이진 탐색 시간복잡도 : O(logN) 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. N개의 데이터를 절반씩 좁혀가며 데이터를 탐색하는 방법 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)이다. 퀵 정렬과 공통점이다. 재귀함수 이용하는 방법과 반복문을 이용하는 방법 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자. 시작점과 끝점은 모두 index를 의미한다. // 기호나 int형변환은 모두 단방향(정수 부분 남김)으로 동작하.. [알고리즘 파이썬] 다이나믹 프로그래밍 다이나믹 프로그래밍 * 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 * Dynamic은 아무 의미가 없다. 1. DP (중복O) 2. 분할 정복 : Divide & Conquer (D&C) (중복X) overlapping subproblem : 부분문제가 겹치는 경우 -> 피보나치 수 optimal substrucure : 최적부분 구조 -> 문제의 정답을 작은 문제의 정답에서 구할 수 있다. -> 서울 대전 대구 부산 갈 때, 대전에서 부산가는 빠른 길은 대구를 거쳐야 한다. Top-down Bottom-up [알고리즘 파이썬] input 속도 높이기 input 자체가 굉장히 많기 때문에 input 함수로 풀면 시간 초과가 날 수 있다. 따라서 sys.stdin.readline()으로 바꿔서 푼다. # input 대신 사용 sys.stdin.readline() # 개행문자 제거, 한 줄 입력받아 출력하는 소스코드 sys.stdin.readline().rstrip() # input으로 가져온 값 형태 변환 map(int, sys.stdin.readline().split()) # String으로 받아서 한번에 map으로 형변환 하기 map(int, sys.stdin.readline().split()) 이것이 코딩 테스트다 :: 구현 코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룬다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 이것이 코딩 테스트다 :: 그리디 단순하지만 강력한 문제 해결 방법이다. 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘과 자주 짝을 이뤄 출제된다. 탐욕적인 해결법이 존재하는지 고민해보자. 해결 방법을 찾을 수 없다면, 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다. 문제풀이 [프로그래머스 Python] - 괄호변환(2020 KAKAO BLIND RECRUITMENT) def make(arr): # 변수정의 cnt1 = 0 cnt2 = 0 state = True # Main # 빈 문자열 반환 if arr == []: return [] for idx,val in enumerate(arr): if val == '(': cnt1 += 1 else : cnt2 += 1 if cnt1 == cnt2 : break; elif cnt1 < cnt2 : # cnt2가 더 크면 올바르지 않은 괄호 문자열 print("올바르지 않은 괄호 문자열") state = False # 반환값 비교 u = arr[0:idx+1] v = arr[idx+1:] if len(v) == 0: answer.append((state,u)) return answer else : answer.append((s.. [알고리즘 파이썬] 인접 행렬과 인접 리스트 그래프 용어 정리 경로 : 정점 A에서 B로 가는 경로 사이클 : 정점 A에서 다시 A로 돌아오는 경로 단순경로(사이클) : 같은 정점을 두 번 이상 방문하지 않는 경로(사이클) 차수 : 정점과 연결되어 있는 간선의 수 In-degree : 들어오는 간선의 수 Out-degree : 나가는 간선의 수 인접 행렬과 인접 리스트 1. 인접행렬 (Adjacency-matrix) - 인접 행렬이란, 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다. - 대각 성분을 기준으로 대칭인 성질을 갖는다. - Adj_mat[i][j] : 노드i 에서 노드j로 가는 간선이 존재할 경우 1이고 아니면 0이다. 2. 인접 리스트 (Adjacency-list) - 각 노드에 연결된 노드를.. [용어정리] 개발용어 1. 레거시 함수, 레거시 코드 Legacy Code란 무엇이고 언제 어떻게 사용하는가? 사전적 의미에서 보면 유산, 산물이라는 의미를 가진다. 즉 누군가 떠나면서 남겨둔 코드 -> 기존의 코드들을 상속받아 개발하는 개발자의 상황에서 레거시 코드라는 용어를 사용 2. NYPC = nexon youth progamming challenge 3. SCPC 4. 삼성소프트웨어멤버십 5. DP, 백트래킹 이전 1 2 3 4 다음