나작코

다이나믹 프로그래밍(Dynamic Programming)이란, 계산된 결과를 기록하고 재활용하여 문제의 답을 구하는 알고리즘입니다. 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서 중간 계산 결과를 기록하기 위한 메모리를 필요로 합니다. 한 번 계산한 부분을 다시 계산하지 않아도 돼서 속도가 빠르다는 장점이 있습니다. 동적 계획법이라고도 불립니다. 다이나믹 프로그래밍에는 타뷸레이션(Tabulation)과 메모이제이션(Memoization) 두 가지 방법이 있습니다. 먼저 타뷸레이션은 하위 문제부터 풀면서 올라가는 상향식 접근 방법으로, 모두 계산하면서 차례대로 진행합니다. 반대로 메모이제이션은 큰 문제에서 하위 문제를 확인해가며 진행하는 하향식 접근 방법으로, 계산이 필요한 순간 계산하면서 진행합..

문제 설명 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준을 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. 제한사항 strings는 길이 1 이상, 50 이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100 이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다. 입출력 예 strings n return ["sun", "b..

분할 정복(Divide and Conquer)이란 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘입니다. 예를 들어 합병 정렬, 퀵 정렬, 이진 검색 등이 있습니다. 분할 정복은 세 가지 과정으로 이루어집니다. 문제를 하나 이상의 작은 부분들로 '분할'하고, 부분 문제를 해결하여 '정복'하고, 부분에서 해결한 문제를 '조합'하여 원래 문제의 답을 구하는 것입니다. 이는 재귀함수를 이용하여 구현할 수 있습니다. 문제를 나누어서 처리하기 때문에 어려운 문제도 해결할 수 있고, 병렬 처리에 이점이 있다는 장점이 두드러집니다. 그러나 재귀 호출 구조를 이용하기 때문에 잦은 분할 시에는 메모리를 많이 사용하거나 동작이 느려질 수 있다는 단점이 있습니다. 분할 정복 구현 코드(최댓값 찾기) public sta..

문제 설명 정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다. 각 query마다 순서대로 s

스택(Stack)이란 후입선출(Last In First Out; LIFO), 즉 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용합니다. 예를 들어 함수 콜 스택, 수식 계산, 인터럽트 처리 등이 있습니다. 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어집니다. 스택의 동작 예시 다음과 같습니다. ↓push() ↑pop() 3(3) 3(1) 2(2) 2(2) 1(1) 1(3) 일반 숫자는 원소, 괄호 안 숫자는 순서를 의미합니다. 예를 들어, push는 1, 2, 3 순서대로 원소가 삽입되었습니다. 그러나 pop으로 원소를 꺼내고자 할 때에는 3, 2, 1과 같이 삽입할 때의 역순으로 원소를 꺼내게 됩니다. 스택에서는 항목을 위에서 push하..

에라토스테네스의 체란, 마치 체로 치듯이 수를 걸러낸다고 해서 붙여진 이름입니다. 고대 그리스의 수학자 에라토스테네스가 만들어낸 방법입니다. 이는 소수(Prime number)를 빠르고 효율적으로 찾을 수 있는 알고리즘입니다. 자세한 설명은 코드와 함께 상세하게 작성한 게시글이 있으므로 생략하겠습니다. [프로그래머스 코딩테스트] 소수 찾기(Java) https://sigfriede.tistory.com/114

문제 설명 직사각형 형태의 그림 파일이 있고, 이 그림 파일은 1 x 1 크기의 정사각형 크기의 픽셀로 이루어져 있습니다. 이 그림 파일을 나타낸 문자열 배열 picture과 정수 k가 매개변수로 주어질 때, 이 그림 파일을 가로 세로로 k배 늘린 그림 파일을 나타내도록 문자열 배열을 return 하는 solution 함수를 작성해 주세요. 제한사항 1

MVC 모델이란 프로그램의 처리 역할을 나누어서 프로그램을 작성하는 방법입니다. 역할은 모델(Model: M), 뷰(View: V), 컨트롤러(Controller: C)의 세 종류로 분류합니다. 이렇게 분류함으로써 프로그램 독립성이 높아집니다. 역할 분담을 통해 효율적인 개발, 개발하는 엔지니어의 분업화가 용이, 설계 변경에 유연하게 대응 가능하다는 장점이 있습니다. 모델은 비즈니스 로직(Business Logic)을 담당합니다. 컨트롤러에서 뷰에 넘겨주는 표시용 데이터 등을 저장하는 객체입니다. 뷰는 사용자 입력과 결과 출력 등 시스템에서 표현 부분을 담당하며 웹 애플리케이션에서는 주로 화면을 담당합니다. 컨트롤러는 서비스 처리를 담당하는 모델과 화면 표시를 담당하는 뷰를 제어하는 역할을 합니다. 사용..

투 포인터(Two Pointer)란 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘입니다. 포인터는 첫 번째 원소에 둘 다 배치하여 같은 방향에서 시작하는 방법과 각각 첫 번째 원소와 마지막 원소에 배치하여 서로 다른 방향에서 시작하는 방법이 있습니다. 이를 이용하여 다중 for문의 복잡도를 줄일 수 있습니다. 투 포인터 구현 코드(첫 번째 원소에서 시작) public static int[] twoPointers(int[] array, int target) { int p1 = 0; int p2 = 0; int sum = 0; int[] result = {-1, -1}; while (true) { if (sum > target) { sum -= array[p1++]; } else if (p..

문제 설명 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 이용한 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return 하는 solution를 완성해주세요. 제한사항 n은 10,000 이하의 자연수 입니다. 입출력 예 n result 15 4 class Solution { public int solution(int n) { int answer = 0; int start = 1; int sum = 0; ..