본문 바로가기

CS/알고리즘8

[코드트리챌린지] 늦었지만 09.05 ~ 09.11 공부 기록..! 목차 2023/09/05 실력 진단 결과 진단을 시행하였는데, 시뮬레이션 문제 풀이 속도가 느렸고, 개념과 문제 5개를 추천받아 풀이함. 1. 방향에 맞춰 이동 풀이 전략 - 동서남북에 대한 dx, dy를 미리 선언해준 뒤, 움직이려는 방향에 움직일 거리를 곱해 더해준다 코드트리 해설 참고 - 시간복잡도 O(n) - 공간복잡도 O(1) 풀이 코드 n = int(input()) moves = [] for _ in range(n): m,c = input().split() moves.append((m, int(c))) x, y = 0, 0 directions = {'W':0, 'S':1, 'N':2, 'E': 3} dx, dy = [-1, 0, 0, 1], [0, -1, 1, 0] # W S N E for m.. 2023. 9. 12.
[이코테] 동적계획법 (Dynamic Programming) 개념 및 문제 풀이 정리 본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다. 포스팅 내 코드 블록은 깃허브에서 찾을 수 있음. 수정 필요 목차 개념 정리 동적계획법(Dynamic Programming)이란? 메모리를 활용하여 시간 효율성을 비약적으로 향상시키는 방법 두 가지 조건할 때 사용할 수 있음 이미 계산한 결과를 메모리에 저장하여, 다시 계산하지 않도록 함 Top-down 방식과 Bottom-up 두 가지 접근 방식이 있는데, Bottom-up 방식을 지배적으로 사용하는 편 DP의 조건 최적 부분 구조 (Optimal substructure): 큰 문제를 작은 문제로 쪼갤 수 있어야 함 중복되는 부분 문제 (.. 2023. 8. 28.
[이코테] 이진 탐색 본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다. 포스팅 내 코드 블록은 깃허브에서 찾을 수 있음. 목차 1. 이진 탐색 순서대로 정렬된 배열이 있을 때, 가능성을 반씩 줄여가며 목표 값을 탐색하는 알고리즘 선형 탐색은 최대 O(N)의 시간복잡도를 가지나, 이진 탐색은 O(logN)의 시간복잡도를 가짐 파이썬 이진 탐색 라이브러리 bisect_left: 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환 bisect_right: 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환 이진 탐색 코드 from bisect import bisect_left.. 2023. 8. 24.
[이코테] DFS & BFS 본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다. 포스팅 내 코드 블록은 깃허브에서 찾을 수 있음. 꼭 필요한 자료구조 기초 스택 (Stack) 선입후출, 입구 == 출구. 컴퓨터에서 함수 호출 시 실행되는 구조와 유사함 list로 구현 가능 # stack stack = [] # 스택 생성 stack.append(v) # 스택에 데이터 삽입 stack.pop() # 스택에서 데이터 꺼내기 큐 (queue) FIFO(선입선출). 터널 구조 시간복잡도를 위해 deque(덱)을 사용하는 것이 적절함 # queue from collections import deque queue = deque() .. 2023. 8. 22.
백준 1920번 수 찾기 문제 풀이 Python 문제 정의 수 찾기 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력: 자연수 N, N개의 정수, 자연수 M, M개의 수 출력: 존재하면 1, 존재하지 않으면 0 문제 해석 문제 자체는 m개의 아이템이 n개 아이템이 있는 배열에 포함되어 있는가? 라는 간단한 문제이나, M과 N의 크기가 커질수록 매우 많은 시간이 소요되어 선형 탐색으로 풀면 시간 초과가 발생함. 따라서 이진 탐색을 통해서 해결한다! 시간 복잡도 m개의 요소에 대해서 평균적으로 logn 번 탐색하게 되므로 O(mlogn) 으로 추정됨. 구현 def binary_search(array, elem): pl = 0 pr = len(array)-1 wh.. 2023. 8. 10.
백준 11047번 동전 0 문제 풀이 Python 문제 정의 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력: N, K, 동전의 가치(N개, 오름차순, 배수) 출력: K원을 만드는데 필요한 동전 개수의 최솟값 문제 해석 K를 만드는 데 필요한 동전의 최소 개수를 구해야 함. 입력의 정의를 통해 거스름돈 문제와 같은 문제이나, 입력 형식만 약간 다른 것으로 파악됨. 즉, 그리디 알고리즘을 통해 해결할 수 있음. 시간 복잡도 Big-O O(N)이 되는데 이 때의 N은 동전의 수! 구현 n_k = input() n, k = int(n_k.split(' ')[0]), int(n_k.s.. 2023. 8. 10.

티스토리툴바