kjp0411 님의 블로그

[프로그래머스] 최솟값 만들기 - Java 풀이문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분류정렬그리디배열문제 요약길이가 같은 두 배열 A, B가 주어진다.각 배열에서 숫자를 하나씩 뽑아 서로 곱한 뒤, 그 곱한 값들을 모두 더한다.이때 각 배열의 원소는 한 번씩만 사용할 수 있다.최종적으로 만들어지는 누적합이 최소가 되도록 하는 값을 구하는 문제이다.예를 들어 다음과 같다.A = [1, 4, 2]B = [5, 4, 4]결과 = 29풀이 아이디어이 문제의 핵심은 다음과 같다.작은 값..

[프로그래머스] JadenCase 문자열 만들기 - Java 풀이문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분류구현문자열 처리문자 변환문제 요약문자열 s가 주어졌을 때, 각 단어의 첫 문자는 대문자로 만들고 나머지 문자는 소문자로 만들어 반환하는 문제이다.단, 첫 문자가 알파벳이 아닌 경우에는 그대로 두고, 그 뒤의 알파벳들은 소문자로 처리해야 한다.예를 들어 다음과 같다."3people unFollowed me" → "3people Unfollowed Me""for the last..

[프로그래머스] 최댓값과 최솟값 - Java 풀이문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분류구현문자열 처리최소/최대값 탐색문제 요약공백으로 구분된 숫자 문자열 s가 주어진다.문자열 안에 있는 숫자들 중에서 최솟값과 최댓값을 찾아 아래 형식의 문자열로 반환하는 문제이다."최솟값 최댓값"예를 들어 다음과 같다."1 2 3 4" → "1 4""-1 -2 -3 -4" → "-4 -1""-1 -1" → "-1 -1"풀이 아이디어문자열은 공백 기준으로 숫자가 구분되어 있다.따라서 먼저 s..

기하 알고리즘은 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘입니다.코딩 테스트에서 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀 수 있습니다. 기하의 핵심 이론CCW는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘입니다.세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라고 가정했을 때 CCW 공식은 다음과 같습니다. CCW 공식CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3) CCW 결과 CCW 결과 == 0: 일직선CCW 결과 > 0: 반시계 방향|CCW 결과|: 세 점으로 이루어진 두 백터의 외적값|CCW 결과| / 2: 세 점으로 이루어진 삼각형의 넓이

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻합니다. 동적 계획법의 핵심 이론동적 계획법으로 풀 수 있는지 확인하기점화식 세우기메모이제이션 원리 이해하기TOP - DOWN 구현 방식 이해하기BOTTOM - UP 구현 방식 이해하기동적 계획법의 원리와 구현 방식큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.동적 계획법은 TOP - DOWN 방식과 BOTTOM - UP 방식으로 구현할 수 있다.동적 계획법의 가장 대표적인 문제인 피..

최소 공통 조상은 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드입니다. 최소 공통 조상의 핵심 이론일반적인 최소 공통 조상 구하기1. 먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장합니다.(탐색은 DFS 또는 BFS를 이용해 수행합니다.) 2. 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춥니다.(두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료합니다.) 3. 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복합니다.(처음 만나는 노드가 최소 공통 조상이 됩니다.) 위..

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조 형태가 세그먼트 트리입니다. 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대·최소 구하기로 나눌 수 있습니다.구현 단계는 트리 초기화하기, 질의값 구하기(구간 합, 최대·최소 구하기), 데이터 업데이트하기로 나눌 수 있습니다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듭니다.트리 리스트의 크기를 구하는 방법은 2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 리스트의 크기로 정의합니다. 2. 질의값 구하기3. 데이터 업데이트하기

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성되어 있는 트리입니다.트리의 영역에서 가장 많이 사용되는 형태입니다. 이진 트리의 핵심 이론이진 트리의 종류이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있습니다.편향 이진 트리: 노드들이 한쪽으로 편향돼 생성된 이진트리포화 이진 트리: 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리완전 이진 트리: 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비됩니다.일반적으로 코딩 테스트에서 트리에 담는다고 하면 완전 이진 트리 형태를 떠올리면 됩니다. 이진 트리의 순차 표..

트리는 노드와 엣지로 연결된 그래프의 특수한 형태입니다. 트리의 특징순환 구조(사이클)를 지니지 있지 않고, 1개의 루트 노드가 존재합니다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다.트리의 부분 트리 역시 트리의 모든 특징을 따릅니다.구성 요소설명노드데이터의 index와 value를 표현하는 요소엣지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 노드 트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다. 트라이..