반응형 [코딩테스트] 요약 문제 해결 순서- 문제는 쪼개서 읽기- 제약사항 파악하기- 테스트 케이스 고려하기- 입력값 분석하기- 핵심 키워드 분석하기- 데이터 흐름 + 구성 파악하기 Pseudo-Code- 자연어로 작성- 동작 중심으로 문제 해결 순서로 작성 시간복잡도- 알고리즘이 문제를 푸는 연산횟수와 입력의 관계를 표현- Big-O Notation: 최악의 경우를 고려한 시간복잡도 표기법시간복잡도최대 연산 횟수n!102^n20n^3200n^23000n*log(n)100만n1000만log(n)10억 자료형- 부동소수점 오차주의(sys.float_info.epsilon)- 데이터 타입은 mutable(list, dict, set)과 immutable(tuple, int, float, str)로 나뉨 함수- lambda expre.. 2024. 7. 6. [코딩테스트] 정렬 정렬 문제 추천- 문자열 내 마음대로 정렬하기(Lv1)- 정수 내림차순으로 배치하기(Lv1)- K번째 수(Lv1)- 가장 큰 수(Lv2)- 튜플(Lv2)- 지형 이동(Lv4)+)- 파일명 정렬(Lv2)- H-Index(Lv2)문자열 내 마음대로 정렬하기def solution(strings, n): answer = [] answer = sorted(strings, key=lambda x: (x[n], x)) return answer정수 내림차순으로 배치하기def solution(n): answer = 0 answer = sorted(list(str(n)), reverse=True) answer = int("".join(answer)) return answerK번쨰 수d.. 2024. 7. 6. [코딩테스트] 해시 해시 ADTclass Hash: def __init__(self, size:int = 10): self.keys[size] = [i for i in range(size)] self.values[size] = [None for _ in range(size)] self.size = size def hash(self, data): 문제 추천- 완주하지 못한 선수(Lv1)- 할인 행사(Lv2)- 오픈 채팅방(Lv2)- 베스트 앨범(Lv3)- 신고 결과 받기(Lv1)- 메뉴 리뉴얼(Lv2)+)- 의상(Lv2)- 압축(Lv2)완주하지 못한 선수def solution(participant, completion): answer = '' membe.. 2024. 7. 5. [코딩테스트] 큐 큐- FIFO(First In First Out): 먼저 들어간 데이터가 먼저 나오는 구조- 작업 대기열이나 이벤트 처리에 사용 ADTclass Queue: def __init__(self, size:int =10): self.data = [None for _ in range(size)] self.front = -1 self.rear = -1 self.size = size def isEmpty(self): -> bool if self.front == self.rear return True else: return False def isFull(self).. 2024. 7. 5. [코딩테스트] 스택 스택- FILO(First In Last Out): 먼저 들어간 데이터가 나중에 나오는 구조- 함수 호출시 메모리의 스택에 사용 ADTclass Stack: def __init__(self, size:int = 10): self.data = [None for _ in range(size)] self.top = -1 self.size = 10 def isEmpty(self): -> bool if self.top == -1: return True else: return False def isFull(self): -> bool if self.top == (se.. 2024. 7. 5. [코딩테스트] 배열 / 연결리스트 배열- 연속된 메모리를 이용한 자료구조- 같은 자료형의 묶음 ADTclass Array: def __init__(self, size:int = 10): self.data = [None for _ in range(size)] self.size = size def isEmpty(self): def isFull(self): def insert(self, index, data): if self.data[index] = data def add(self, data): if def remove(self, index): self.data[index] = Non.. 2024. 7. 5. [코딩테스트] 특징 및 소개 코딩테스트 코딩테스트 사이트- 프로그래머스: 네이버, 카카오 등 IT 기업들의 코딩테스트 사이트- 백준 온라인 저지- solved.ac: 백준 온라인 저지를 단계별로 분류- SW Expert Academy: 삼성 코딩테스트 사이트- Softeer: 현대 자동차그룹 코딩테스트 사이트이론시간복잡도 공간복잡도 2024. 7. 5. [코딩 테스트] 11. 심화 자료구조 Index 1. 우선순위 큐와 힙 2. 트리 3. 바이너리 인덱스 트리 4. 참고자료1. 우선 순위 큐와 힙우선순위 큐- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조- 데이터를 우선 순위에 따라 처리하고 싶을 때 사용- 삽입/삭제시 O(logN)- heap 정렬은 O(NlogN) 구현 종류1) 리스트 이용해 구현2) heap을 이용해 구현 Heap- 완전 이진 트리 자료구조: root 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 tree- Heap에서는 항상 root 노드를 제거- Min Heap / Max Heap 힙 정렬def heap_sort(iterable): h = [] result = [] for val in iterable: he.. 2023. 10. 17. [알고리즘] 10. 기타 알고리즘 Index 1. 소수 판별 2. 에라토스테네스의 체 3. 투 포인터 4. 구간 합 5. 최소 공통 조상 5. 참고자료 1. 소수 판별소수(Prime Number)- 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 # 시간 복잡도: O(N)def is_prime(x): for i in range(2, x): if x % i == 0: return False return True # 시간 복잡도: O(sqrt(N))import mathdef is_prime(x): for i in range(2, int(math.sqrt(x)) + 1): if x % i == 0: return False return True 2. 에라토스테네스.. 2023. 10. 5. [알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료1. 서로소 집합 자료구조Disjoint Sets- 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find)- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조- 두 종류의 연산을 지원- - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산- - Find: 특정한 원소가 속한 집합이 어떤 집합인지- 연결성을 통해 집합의 형태를 확인 (동작 과정)1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - A'를 B'.. 2023. 10. 5. 이전 1 2 다음 반응형
