Grusie 안드로이드 개발 기술 블로그

이번에 알아 볼 알고리즘은 구현이다. 구현 알고리즘이란? - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제를 풀이할 때 구현은 매우 필요하다. 모든 문제를 구현이라고 생각 할 수 있으나, 그 중 구현이 어렵거나 구현에 초점을 맞추는 문제들이 있다. 즉, 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제라고 생각하면 된다. 예시 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 알고리즘은 간단한데, 코드가 길어지는 문제 시뮬레이션 문제 완전 탐색 완전탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로..

알고리즘 첫 번째, 누적합의 이론을 공부하고 예제들을 풀어보려고 한다. 누적 합 : 일정 구간의 누적 합을 구하는 문제이다. 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간 복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(N)으로 해결 할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있다. 예를 들어, 크기가 5인 arr배열에서 3번 index와 5번 index 구간의 구간합을 구한다고 가정하면, 누적합은 arr[0~b]까지의 누적합 - arr[0~a-1까지의 누적합]으로 표현 할 수 있다. b - a 구간의 누적합을 구하기 위해선 b..

경력은 코딩테스트보다 과제전형이나 면접에서 많이 갈리겠지만, 대기업을 위해 공부를 한다면 코딩테스트라는 진입장벽이 존재한다.필자도 경험을 해보긴 했으나, 항상 합격을 못 했었기에, 공부를 새로 진행해보려고 한다.최근들어 백준 문제를 풀어 실력이 좀 늘었다고 생각하였으나, 아직 DP와 최단거리 등 이해가 안 가고 풀지 못하는 부분들이 있어, 공부하며 기록하여 내껏으로 만들어 보려고 한다. 개념학습에 관한 유튜브 강의가 이런저런 있었으나, "개발자 장고"님의 코딩테스트 필수 알고리즘이 도움이 되었다.https://www.youtube.com/watch?v=pvufY7rK7VA&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB"개발자 장고"님의 코딩테스트 필수 알고리즘 이론 공부들을 이해..