INHO 일상

누적합 알고리즘(Prefix sum) 누적합 알고리즘(Prefix sum)은 특정 구간에서 중간의 합계나 평균을 자주 구해야하는 경우에 사용할 수 있는 알고리즘이다. 단순히 반복문을 사용해서 알고리즘을 구현하게 된다면 시간이 많이 소요되고, 코딩 테스트에서 조건으로 주어지는 시간 제한을 지키지 못하는 경우가 생겨나게 된다. 누적합 알고리즘은 이런 시간 초과를 해결하기 위해서 구간별로 누적합을 계산해, 그 누적합을 저장하는 배열을 하나 만드는 방식으로 사용된다. 예를 들어 다음과 같은 배열이 주어졌다고 가정해보자. arr = [1, 8, 7, 4, 3, 5] 위와 같은 배열이 있을때, 각 구간의 누적합을 저장하는 새로운 배열을 아래와 같이 만들어준다. (가장 첫번째 원소로는 값 '0'을 넣어주었다.) pr..

본 포스팅에서는 이진 탐색 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtube.com 파라메트릭 서치 파라메트릭 서치란 최적화 문제를 결정 문제 ('예' 혹은 '아니오')로 바꿔서 해결하는 기법 일반적으로 이런 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다. ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 문제 1) 2023.03.16 - [백준 알고리즘] - 백준 2805번 나무 자르기 문제풀이, 파이썬 백준 2805번 나무 자르기 문제풀이, 파이썬 백준 2805번 : 나무 자르기 문제풀이 [파이썬] 2805번 ..

본 포스팅에서는 이진 탐색 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtube.com 순차 탐색과 이진 탐색 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색의 동작 예시) 이미 정렬된 10개의 데이터 중에서 값이 4인 원소 찾기 시작점 : index 0, 끝점 : [9], 중간점 : [4] (소수점 이하는 제거) 우리가 찾고자 하는 원소 4보다 중간점의 원소 8이 큰 상황임. 따라서 중간점..

본 포스팅에서는 정렬 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtube.com 지난 포스팅에서는 선택 정렬, 삽입 정렬에 대해서 알아보았습니다. 2023.02.22 - [백준 알고리즘] - [알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬 [알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬 본 포스팅에서는 정렬 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtub..

본 포스팅에서는 정렬 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtube.com 정렬 이란? 정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미함. ① 선택 정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 위와 같은 예시의 데이터가 있다고 가정. 처리되지 않은 데이터 중 가장 작은 데이터가 '0'이기 때문에 이 '0'을 선택해 가장 앞의 '7'과 바꾼다. 그럼 위처럼 0은 이미 처리가 된 상태가 되는 것이고, 남은 데이터들 중 다시한번 가장 작은..

2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘 [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘 2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 본 알고리즘 포스팅의 주제인 DFS와 BFS inho3213.tistory.com DFS 알고리즘에 대한 정리는 위 포스팅에서 확인 본 포스팅에서는 BFS 알고리즘에 대한 정리 내용을 담고있습니다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbin..

백준 1541번 : 잃어버린 괄호 문제풀이 [파이썬] 그리디 알고리즘 1541번 문제의 내용은 아래와 같습니다. 잃어버린 괄호 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫..

백준 11399번 문제풀이 : ATM / 파이썬 11399번 문제의 내용은 아래와 같습니다. ATM 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은..

2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 본 알고리즘 포스팅의 주제인 DFS와 BFS 알고리즘에 대해 알기전에, 먼저 '그래프 탐색'이란 무엇인가에 대해서 알아보는 것이 필요하다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고 inho3213.tistory.com 지난 포스팅에서는 스택 자료구조와 큐 자료구조에 대한 내용을 정리했다. 이번 포스팅에서는 본격적으로 DFS 알고리즘에 대해 정리해보고자한다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@do..

본 알고리즘 포스팅의 주제인 DFS와 BFS 알고리즘에 대해 알기전에, 먼저 '그래프 탐색'이란 무엇인가에 대해서 알아보는 것이 필요하다. (본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.) https://www.youtube.com/@dongbinna 동빈나 www.youtube.com 그래프 탐색 이란? 우선 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 그래프에서의 탐색은 하나의 노드를 시작으로 연결된 모든 노드들을 모두 찾는 과정을 말한다. 다음으로 DFS와 BFS에 대해 다루기 전에 '스택'과 '큐'라는 자료구조에 대해 정리해보았다. 1. 스택 자료구조 란? 먼저 들어 온 데이터가 나중에 나가는 형식, 즉 선입선출의 자료구조를 스택 자료..