728x90 Algorithm7 자료구조 기초 / BFS & DFS 1. 자료구조 기초 1-1. 스택 (Stack) 선입후출, 입구 == 출구. 컴퓨터에서 함수 호출 시 실행되는 구조와 유사함 list로 구현 가능 # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack = []# # 스택 생성 stack.append(5) # 5 stack.append(2) # 5 2 stack.append(3) # 5 2 3 stack.append(7) # 5 2 3 7 stack.pop() # 5 2 3 stack.append(1) # 5 2 3 1 stack.append(4) # 5 2 3 1 4 stack.pop() # 5 2 3 1 print(stack) # 5 2 3 1 # 뒤집어 출력 print(stack[::.. 2024. 4. 6. 구현 알고리즘 (Implementation Algorithm) 구현(Implementation) 코딩 테스트에서 구현이란 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 구현 문제를 풀기 위해서는 프로그래밍 언어의 문법을 정확히 알고 있어야 한다. 또한 적절한 라이브러리를 찾아서 사용해야 한다. 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. 2차원 행렬(Matrix) 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. 문제 1 : 상하좌우 난이도: 하 | 제한시간: 15분 | 시간제한: 2초 | 메모리 제한: 128MB 여행가 A는 N x N 크기의 정사각형 공간 위에 있습니다. 이 공간은 1 x 1 크기의 정사각형으.. 2024. 4. 3. 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함 그리디 해법은 그 정당성 분석이 중요함 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 문제 1. 거스름돈 거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소의 개수를 구하여라. 풀이 # 거스름돈 n = 1260 count = 0 # 큰 단위의 화폐부터 coin_types = [500, 100, 50, 10] for coin in coin_types: count += n // coin # 거슬러 줄 .. 2024. 4. 1. 실전에서 유용한 표준 라이브러리 cotinue 키워드 global 키워드 1. 실전에서 유용한 표준 라이브러리 내장 함수 : 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공한다. 그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있다. itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공한다. 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용된다. 모든 경우의 수를 고려해야 하는 경우에서 많이 활용된다. 완전 탐색 유형 문제에서 소스 코드를 간결하게 만들어준다. heapq : 힙(Heap) 자료구조를 제공한다. 일반적으로 우선순위 큐 기능을 구현하기 위해 사용된다. 최단경로 알고리즘에서 많이 활용된다. bisect : 이진 탐색(Binary Search) 기능을 제공한.. 2024. 4. 1. 파이썬 문법 - 입출력 1. 입력 1-1. 자주 사용되는 표준 입력 방법 input( ) : 한 줄의 문자열을 입력 받는 함수 map( ) : 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용 ex) 공백을 기준으로 구분된 데이터를 입력 받을 때 list(map(int, input().split())) ex) 공백을 기준으로 구분된 데이터의 개수가 많지 않을 때 a, b, c = map(int, input().split()) 1-2. 빠르게 입력 받기 정수를 받는 경우 import sys a = int(sys.stdin.readline()) a1,a2,a3 = map(int,sys.stdin.readline().split()) data = list(map(int,sys.stdin.readline().split())) >.. 2024. 4. 1. 파이썬 문법 - 자료형(리스트, 튜플, 딕셔너리, 집합) 1. 리스트 리스트 컴프리헨션 2차원 리스트를 초기화할 때 효과적으로 사용 특히 N X M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 유용 Good : array = [[0] * m for _ in range(n)] 아래 bad 코드 : 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식 bad : array = [[0]*m] * n 리스트 관련 기타 메서드 2. 튜플 리스트와 유사하지만 다음과 같은 문법적 차이가 있음 튜플은 한 번 선언된 값을 변경할 수 없음 리스트는 대괄호 []를 이용하지만, 튜플은 소괄호 ()를 이용 튜플은 리스트에 비해 상대적으로 공간 효율적 튜플을 사용하면 좋은 경우 서로 다른 성질의 데이터를 묶어서 관리해야 할 때 최단 경로 알고리즘에서는 (비용, 노트 번호.. 2024. 4. 1. 알고리즘 성능 평가 빅오 표기법 및 알고리즘 실행 시간 알고리즘 문제 해결 과정 1. 지문 읽기 및 컴퓨터적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 요구사항에 따라 적절한 알고리즘 설계하기 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행 시간 요구사항)이다. 시간 제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다. 𝑁의 범위가 500인 경우: 시간 복잡도가 O(N3) 인 알고리즘을 설계하면 문제를 풀 수 있다. 𝑁의 범위가 2,000인 경우: 시간 복잡도가 O(N2) 인 알고리즘을 설계하면 문제를 풀 수 있다. 𝑁의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN) 인 알고리즘을 설계하면 문제를 풀 수 있다. 𝑁의 범위가 10,000.. 2024. 4. 1. 이전 1 다음 728x90 반응형
