https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr - 처음 작성한 잘못된 풀이class Solution { public int solution(String name) { int answer = 0; char[] cName = name.toCharArray(); char[] aName = new char[cName.length]; int cursor = 0; int a = aName.length; ..
코딩 테스트를 공부할 때여러 알고리즘이 사용되지만 그 중에 가장 기초가 되는 알고리즘이 오늘의 주제인 탐욕법이다. 하지만 막연하게만 알고 자세한 정의는 하지 못하는 것 같아 이번 기회에 제대로 알아보고자 한다. ※ 그리디 알고리즘(탐욕법)의 정의▶ 그리디 알고리즘은 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 방법을 의미▶ 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안됨 ※ 그리디 알고리즘(탐욕법)의 조건 ▶ 선택 조건이 탐욕스러워야 함- 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 함- 여기서 '안전하다'라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것을 의미=> 문제를 풀 때 그리디 알고..
https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net ※ 문제 설명 - 이 문제는 투 포인터 알고리즘 개념을 활용하여 풀 수 있는 문제이다. - 연속되는 수들의 합으로 입력한 수를 만들 수 있는 가지 수를 구하는 문제이다. ※ 투 포인터 ? - 배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘 - 투 포인터의 시간복잡도는 빅오 표기법을 사용하면 O(n)이며, 선형..
자료구조 파트의 두 번째 파트인 구간 합이다. 구간 합을 처음 들었을 때는 그냥 어떤 범위 안 값들의 합을 반복문 이용해서 구하는 거 얘기하는건가..? 라는 생각이 들었다. 근데 공부하면서 구간 합 공식이라는 것을 처음 알게되었다. ㅋㅋ... ※구간 합 ▶ 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. ▶ 예를 들어 어떠한 배열의 특정 범위에 있는 값들의 합을 구하고 싶을 때, 이 값을 빨리 구할 수 있는 알고리즘이다. ▶ 이 알고리즘은 코딩 테스트에서 사용 빈도가 높다. ★ 합 배열 → 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. → 합 배열은 다음과 같이 배열의 값을 하나씩 더해서 각 인덱스까지의 합을 저장한 배열이다. → 합 배열을 만드는 공..
