본문 바로가기

coding-test

 (6)
[이것이 코딩 테스트다] CH06. 정렬 선택 정렬 매번 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 수행하여 오름차순으로 정렬하는 방법 # 선택 정렬 예시 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): #i=0부터 min_index = i for j in range(i+1, len(array)): #j=1부터 if array[min_index] > array[j]: min_index = j #가장 작은 원소의 index를 min_index에 저장 array[i], array[min_index] = array[min_index], array[i] #swap print(array) 시간복잡도 = O(N²), N + (N-1) + ... + 2 의 빅오표기법 삽입 정렬 데이터를 적절한..
[이것이 코딩 테스트다] CH05. DFS/BFS 스택 Stack - 선입후출 First in Last out 구조 또는 후입선출 Last in First out 구조 # 스택 예제 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 큐 Queue - 선입선출 First in First out 구조 # 큐 예제 from collections import deque queue = deque() queue.append(5) queue.append(2) queue.appen..
[이것이 코딩 테스트다] CH04. 구현 C/C++에서 변수의 표현 범위 Python에서 리스트 크기 - 보통 Python이 C언어에 비해 난이도는 낮지만, 동작 속도가 느리다. 예제 4-1. 상하좌우 시뮬레이션 유형: 개체를 차례대로 이동시킴. 여행자 A가 가장 왼쪽 위 = (1,1)에서 상, 하, 좌, 우 방향으로 이동하는 계획서에 따라 도착 지점의 좌표를 출력하시오. (단, N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.) X, Y = 1, 1 N = int(input()) plans = input().split for moving in plans: if moving == 'L': if Y ==1: continue #해당 반복 벗어남. Y -= 1 elif moving == 'R': if Y == N: continue Y += ..
[이것이 코딩 테스트다] CH03. 그리디 1. 당장 좋은 것만 선택하는 그리디 # 예제 3-1. 거스름돈 ## N원을 거슬러 줄 때 거슬러 줘야 할 동전의 최소 개수를 구하여라. (단, N은 항상 10의 배수이다.) N = input("거스름돈 N원을 입력하시오.: ") n = int(N) coin_types = [500, 100, 50, 10] count = 0 for coin in coin_types: count += n//coin n %= coin print(N, "원을 거슬러 줄 때 최소 동전의 개수는", count, "개 이다.") 시간 복잡도 = O(K), 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다. 2. 큰 수의 법칙 # 실전 3-2. 큰 수의 법칙 ## 배열의 크기 N, 숫자가 더해지는 횟수 M, ..
[이것이 코딩 테스트다] CH01. 코딩 테스트 개요 복잡도 단순히 '복잡도'라고 한다면, 보통은 '시간 복잡도'를 의미한다. 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양 수행 시간 측정 소스코드 import time start_time = time.time() # 측정 시작 # 프로그램 소스 코드 end_time = time.time() # 측정 종료 print("time: ", end_time - start_time) # 수행 시간 출력
[이것이 코딩 테스트다] 시작하며, 여러가지 프로그래밍 언어를 공부했지만, 알고리즘 공부를 집중적으로 한 적은 없다. 전반적으로 코딩 테스트에 대한 지식을 쌓고, 알고리즘을 공부를 하기 위해 이 책을 구매했다. 앞으로 이 책을 공부하면서 백준 등 여러 코딩 테스트도 함께 풀어볼까 한다.

티스토리툴바