본문 바로가기

알고리즘22

[알고리즘/Python] 항상 작은 숫자 2개를 활용하고 싶을 때 (list, heapq) 1. 문제 상황 및 해결 방법주어진 문제는 리스트에서 가장 작은 두 숫자를 반복적으로 찾아 합치고, 이를 다시 리스트에 추가하여 최종 비용을 계산하는 것입니다.기존 코드에서는 리스트를 반복적으로 정렬하여 가장 작은 두 숫자를 찾고 제거합니다.이 코드로 문제에 제출하니 시간 초과가 떠서 해결방안을 고민했습니다.n = int(input())nums = list(map(int, input().split()))cost = 0while (len(nums) > 1) : # 리스트 정렬하여 가장 작은 두 숫자 구하기 nums.sort() n1 = nums.pop(0) n2 = nums.pop(0) # 드는 비용 업데이트 cost += (n1+n2) # 두 숫자를 리스트에서.. 2024. 5. 30.
[알고리즘] 스택과 큐의 개념 및 구현 안녕하세요. 개발감자입니다! 코딩 테스트를 준비하면서 책을 보며 공부하고 있습니다. 책을 보며 공부한 내용을 간단히 정리해보았습니다. 코딩 테스트를 준비하는 다른 분들께 도움이 되었으면 합니다 코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고 코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트 product.kyobobook.co.kr 1. 스택 스택의 개념 티슈와 같이 쌓는 개념 선입후출 : 가장 처음에 넣은 것이 가장 마지막에 나온다. stack = [] stack.append(value) # 요소 추가 last_value = stack.pop() .. 2024. 4. 19.
[알고리즘] 배열의 개념 및 구현 ( 데이터 추가, 삭제 ) 안녕하세요. 개발감자입니다! 코딩 테스트를 준비하면서 책을 보며 공부하고 있습니다. 책을 보며 공부한 내용을 간단히 정리해보았습니다. 코딩 테스트를 준비하는 다른 분들께 도움이 되었으면 합니다 코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고 코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트 product.kyobobook.co.kr 1. 배열 배열 인덱스와 값을 일대응 대응해 관리하는 자료 구조 인덱스는 0부터 시작 2차원, 3차원 배열도 저장 가능 → 차원과는 무관하게 메모리에 연속 할당 arr = [0,1,2,3] arr = [0 for _ in.. 2024. 4. 16.
[알고리즘] 파이썬 기본 문법 정리 안녕하세요. 개발감자입니다! 코딩 테스트를 준비하면서 책을 보며 공부하고 있습니다. 책을 보며 공부한 내용을 간단히 정리해보았습니다. 코딩 테스트를 준비하는 다른 분들께 도움이 되었으면 합니다 코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고 코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트 product.kyobobook.co.kr 0. 파이썬 기본 문법 정리 빌트인 데이터 타입 정수형 양과 음의 정수, 0을 포함 정수형 산술 연산 a , b = 1, 2 print(a+b, a-b, a//b, a%b) # 더하기, 빼기, 몫, 나머지 print(a*.. 2024. 4. 16.
세그먼트 트리 개념 및 구현 / 코딩테스트 주요 5대 알고리즘 안녕하세요! 개발감자입니다. 오늘 세그먼트 트리 개념과 코딩테스트에서 구현하는 방법에 이야기해볼게요. 세그먼트 트리를 알아보기에 앞서 트리의 개념이 헷갈리는 분이 계신다면, 아래의 포스팅을 참고하시길 바랍니다. [알고리즘 마스터] 14. 트리와 트라이 안녕하세요! 개발감자입니다🥔 오늘은 알고리즘 중 트리와 트라이에 대해서 정리하고 백준 문제를 통해 구현해보는 시간을 가져보도록 하겠습니다. 1. 트리 알아보기 트리는 그래프의 특수한 qkrrmsdud.tistory.com 1. 세그먼트 트리의 개념 세그먼트 트리(Segment Tree)는 구간 쿼리를 빠르게 처리하기 위한 자료구조로, 주로 배열과 같은 일차원 데이터에 대한 구간 합을 효율적으로 구하는 데 사용됩니다. 세그먼트 트리는 완전 이진 트리의 형태를.. 2024. 1. 18.
이진트리의 개념과 종류 / 전위순회, 중위 순회, 후휘 순회 알아보기 안녕하세요! 개발감자입니다. 오늘 이진트리의 핵심이론과 이진트리를 순회하는 방법에 이야기해볼게요. 이진트리를 알아보기에 앞서 트리의 개념이 헷갈리는 분이 계신다면, 아래의 포스팅을 참고하시길 바랍니다. [알고리즘 마스터] 14. 트리와 트라이 안녕하세요! 개발감자입니다🥔 오늘은 알고리즘 중 트리와 트라이에 대해서 정리하고 백준 문제를 통해 구현해보는 시간을 가져보도록 하겠습니다. 1. 트리 알아보기 트리는 그래프의 특수한 qkrrmsdud.tistory.com 1. 이진 트리의 개념 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조를 말합니다. 각 노드는 부모 노드와 왼쪽 자식 노드, 오른쪽 자식 노드를 가질 수 있습니다. 이진 트리는 데이터 검색, 정렬, 계층 .. 2024. 1. 18.
[알고리즘 마스터] 14. 트리와 트라이 안녕하세요! 개발감자입니다🥔 오늘은 알고리즘 중 트리와 트라이에 대해서 정리하고 백준 문제를 통해 구현해보는 시간을 가져보도록 하겠습니다. 1. 트리 알아보기 트리는 그래프의 특수한 형태로 노드와 에지로 연결되어있습니다. 1-1. 트리의 특징 1) 순환구조가 아니며, 1개의 루트 노드가 존재합니다. 2) 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다. 3) 트리의 부분 트리 역시 트리의 모든 특징을 따릅니다. 1-2. 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드를 연결하는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 : 두 노드 사이 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이 관게에서 하위 노드에 해.. 2024. 1. 16.
[알고리즘 마스터] 13. 정수론 (소수, 오일러 피, 유클리드 호제) 안녕하세요, 개발감자입니다! 오늘은 알고리즘 중 에 대해서 정리해보는 시간을 가져보겠습니다. 1. 정수론이란 무엇일까요? 수학에서 정수론은 말 그대로 수의 성질을 탐구하는 분야를 의미합니다. 정수론 굉장히 방대한 범위를 가지고 있습니다. 하지만, 코딩 테스트에서는 모든 분야는 나오지 않고, 아래에 나올 내용인 소수 구하기, 오일러 피, 유킬리드 호제법이 가장 빈출되는 분야라고 합니다. 이 분야들을 집중으로 다뤄보는 시간을 가져보도록 하겠습니다. 2. 정수론 알고리즘 2-1. 소수 구하기 소수는 약수가 1과 자기 자신뿐인 수를 의미합니다. 예를 들어 2,3,5,7,11 등이 습니다. 코딩테스트에서 소수를 구할 때에는 라는 대표적인 소수 판별법을 활용합니다. 의 원리는 다음과 같습니다. 1) 구하고자 하는 .. 2024. 1. 13.
[알고리즘 마스터] 12. 스택과 큐 안녕하세요. 개발감자 박그냥입니다!🥔 오늘은 알고리즘 중 에 대해 정리해보도록 하겠습니다. 스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 가장 기본적이면서도 중요한 자료구조입니다. 이 두 가지 자료구조는 데이터를 저장하고 조작하는 방식에 있어서 서로 다른 특징을 가지고 있습니다. 아래의 그림은 개발감자가 복습하며 그려본 그림입니다. 참고하여 학습에 도움이 되셨으면 좋겠습니다. 1. 스택(Stack) 1-1 특징 선입후출(LIFO, Last-In-First-Out) 구조를 가지고 있습니다. 가장 최근에 추가된 요소가 가장 먼저 제거됩니다. 스택에 요소를 추가하는 작업을 "push", 제거하는 작업을 "pop"이라고 합니다. 주요 동작: push, pop, top(가장 상단 요소 확인), empty(.. 2024. 1. 8.
[알고리즘 마스터] 11. 슬라이딩 윈도우 안녕하세요. 개발감자 박그냥입니다!🥔 오늘은 알고리즘 중 슬라이딩 윈도우에 대해 정리해보도록 하겠습니다. 1. 슬라이딩 윈도우 개념 10. 투포인터와 연결되는 개념입니다. 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음에, 범위를 유지한 채로 이동하며 문제를 해결합니다. 투 포인터 알고리즘과 매우 비슷하며 원리도 간단합니다. 개념을 백준 문제를 통해 이해해보도록 하겠습니다. 2. 슬라이딩 윈도우 관련 문제풀이 2-1. 슬라이딩 윈도우 백준 문제 - 12891 2-2. 문제 풀이 import sys input = sys.stdin.readline N, M = map(int, input().split()) A = list(input().strip()) # 개행 문자 제거 num_A, num_C.. 2024. 1. 7.
[알고리즘 마스터] 10. 투 포인터 안녕하세요. 개발감자 박그냥입니다!🥔 오늘은 알고리즘 중 투 포인터에 대해 정리해보도록 하겠습니다. 이 포스팅은 책 를 참고하여 제작되었습니다. 1. 투 포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다고 합니다. 굉장히 간단한 알고리즘입니다. 백준의 문제 중 투 포인터를 활용하는 문제를 풀며 이해해보도록 할까요? 1-1. 투 포인터 백준 문제 2018번 연속된 자연수의 합 구하기 1-2. 문제 풀이 투 포인터라는 것은 말 그대로 포인터(가르키는 것)이 2개라는 의미입니다. 위의 문제에서 투 포인터를 각각 자연수의 합의 가장 작은 숫자와 가장 큰 숫자를 가르키는 것으로 활용합니다. 두 개의 포인터를 이용해서 내가 원하는 값이 나왔는지 계속 확인하고, 내가 원하는 값이면 가지수에 +1을 해주며 가.. 2024. 1. 5.
코딩테스트에서 가장 기본적인 파이썬 코드 정리 (입력, 누적합 등) 안녕하세요. 개발감자 박그냥입니다!🥔 오늘은 코딩 테스트에서 가장 기본적인 파이썬 코드를 정리해보도록 하겠습니다. 제가 공부하면서 계속 업데이트할 예정입니다 ㅎㅎ 1. 입력받을 때 import sys N = int(input()) # 하나만 입력 받을 때 M, K = map (int, input().split()) # 2개를 한 번에 입력 받을 때 A = list(input()) # 공백없이 입력받아 리스트로 저장할 때 A = list(map (int, input().split())) # 공백 포함해 입력받아 리스트로 저장할 때 2. 2차원 리스트 생성하는 방법 (행 4 열 3인 리스트 생성하는 예시) A = [[0 for col in range(4)] for row in range(3)] 3. 파이썬에.. 2023. 12. 31.

티스토리툴바