문제: 개미전사난이도중풀이 시간30분시간 제한1초메모리 제한128MBA. 문제개미 전사는 메뚜기 마을의 식량창고를 몰래 공격한다.메뚜기 마을의 식량창고는 일직선으로 되어 있다.각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.개미 전사는 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.식량창고 4개가 아래와 같이 존재한다고 가정한다.[1, 3, 1, 5]이때 개미 전..

이전에 정리해둔 글이 있지만 이코테 책을 읽고 다시 정리합니다. [종만북] Dynamic Programming / DP / 동적 계획법 Algorithmic Problem Solving Strategies  개인적으로 읽고 정리한 요약입니다. 아래 링크에 문제 풀이 예제가 있습니다. GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study Algorithm Book Study. Contribute t chanhhh.tistory.com 이책에서는 DP의 첫 분단의 제목을 [중복되는 연산을 줄이자]를 메인으로 설명하고 있다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많..

Greedy 사용 [Swift] Greedy / 그리디 / 탐욕 알고리즘 그리디 알고리즘이란? Greedy algorithm은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으 chanhhh.tistory.com 지원자의 서류심사 성적으로 sort하면 O(NlogN)으로 maxInterviewRank로 where절을 사용해서 아래와 같은 코드로 2NlogN의 시간을 가지고 문제를 풀 수 있지만, 아래의 코드는 백준의 Swift 의 느린 입력으로 인해 시간초과를 받을 수 밖에 없다 let T = Int(readLine()!)! for _ in 0..= 48, now

그리디 알고리즘이란? Greedy algorithm은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 한마디로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들이다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(opti..

알고리즘의 성능을 나타내는 척도. 시간 복잡도와 공간 복잡도로 나눌 수 있다. - 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 - 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양 빅오 표기법 빅오 표기법 명칭 O(1) 상수 시간(Constant time) O(logN) 로그 시간(Log time) O(N) 선형 시간 O(NlogN) 로그 선형 시간 O(N^2) 이차 시간 O(N^3) 삼차 시간 O(2^n) 지수 시간 시간 복잡도 데이터의 개수 N이 천만개(10^7)를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것으로 예상할 수 있다. 데이터의 크기나 탐색 범위가 백억이나 천억(10^10 ~10^11)을 넘가는 경우 O(logN)의 시..