Step-by-Step

문제를 풀다보면 특정 값으로 나눈 나머지값을 구하라는 문구를 많이 접하게 되었다. 자료형 범위를 넘어가지 않도록 조건을 제시해 준 것인데, 만약 전체 곱의 나머지를 구하라고 하면, 전체 곱이 나오기 전에 오버플로우가 발생할 수 있다. 이때 사용하는 것이 모듈러 연산이다. 모듈러 연산 (Modular Arithmetic) 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산 모듈러 합동 (Modular Congruent) 두 A,B 숫자가 M을 모듈러한 결과 값이 같다면 모듈러 합동관계라고 한다. A mod M = b mod N A ≡ B mod M 모듈러 합동식 A = B + K * M (K는 정수) 이 식에서 B를 이항하게 되면, A - B = K * M 두 정수 A, B와 양의 정수 M에 대해 다음..

거리두기를 잘 지켜서 앉아있는지 확인하기 위한 코드를 구현하는 문제이다 제한사항을 보면, P는 사람 O는 빈테이블 X는 파티션이다 모든 값은 5X5로 주어지고, 어느 한 곳에서라도 거리두기가 지켜지지 않으면 0이 된다 처음에는 너비우선 탐색만 이용하였는데, 파라미터 전달이 너무 많고 가독성이 떨어져서 효율적인 코드 작성을 하기 위해 인터넷을 참조하여 여러 클래스와 메소드를 이용하였다 사용한 클래스와 메소드 정리 1. isCorrect : 각 배열이 거리두기를 잘 지키고 있는지에 따라 값 리턴 - 0 or 1 2. bfs : 해당 배열의 특정 부분(P값)을 중심으로 조건에 따라 거리두기가 잘 지켜져 있는지 확인 3. Point : bfs에서 사용할 x, y값의 좌표를 담은 클래스 - 검사할 좌표를 담기 위..

처음에는 ArrayList를 이용해서 배열을 넣고, 완전 탐색을 이용하였다 하지만 시간 초과 + 정답 오류 가 계속 반복되어 나타나는 걸 보고 구글링을 시도하였다.....(최후의 수단) 제한 조건을 자세히 보면 number의 값이 1,000,000자리까지 나올 수 있는데, 완전 탐색을 이용하면 최악의 경우에 1,000,000C999,999의 경우의 수가 나올 수 있기 때문에 절대 사용 금지이다 풀이 방법은 다음과 같다 class Solution { public String solution(String number, int k) { StringBuilder sb = new StringBuilder(); int idx = 0; int max = 0; for(int i=0; i

탐욕 알고리즘(Greedy Algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그때마다 최적의 방법을 선택하여 최종 해답에 도달하는 방법 매 순간마다 최적의 선택을 하더라도 최종적 해답이 최적이라는 보장은 없다 (각 순간의 지역적 선택이 최적일지는 몰라도 전역적으로 봤을때는 최적의 선택이 아닐 수 있다) 탐욕 알고리즘 적절한 사용 탐욕 알고리즘은 아래 두 경우에 사용할 때 좋은 해결방안이 된다 탐욕 선택 속성(Greedy Choice Property) : 매 순간의 탐욕적인 선택이 최종 답의 최적의 선택이 됨 최적 부분 구조(Optimal Substructure) : 부분 문제를 최적화하는 것이 전체를 최적화하는 것임 즉 탐욕 알고리즘을 사용할 때는 ..

동적계획법(Dynamic Programming : DP) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 최적부분구조와 같은 문제에서 효과를 발휘함 ★ 최적 부분 구조(Optimal Substructure) 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성 동적계획법 사용 동적 계획법을 적용하기 위한 예시를 가져왔다 여기서 조건은 f(a,b) = f(a-1,b) + f(a,b-1) (a,b>=1) f(0,0) = 1 자연수 n에 대하여 f(n,0)=f(0,n)=1 여기서 주목해야 하는 점은 f(1,1)이다 f(2,2)는 f(1,2)와 f(2,1)의 합으로 나타낼 수..

맹목적 탐색 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법 대표적인 맹목적 탐색 : 너비우선탐색(BFS), 깊이우선탐색(DFS) 너비우선탐색 (BFS;Breadth First Search) 하나로 시작 정점을 방문한 후 시작 정점에 인접함 모든 정점들을 우선 방문하는 방법 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어있는 모든 길을 탐색하는 방법 너비우선탐색은 트리나 그래프를 방문 또는 탐색하는 방법으로 순서는 다음과 같다 1. 루트에서 시작 2. 루트의 자식 노드들을 [1]에 저장 3. [1]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [2]에 저장 4. [2]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [3]에 저장 5. 위의 과정을..

여러 알고리즘 유형들을 파악하기 앞서 알고리즘이라는 것에 대해 정리해보려고 한다 알고리즘 (Algorithm) 문제를 해결하기 위한 절차나 방법 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set) 반복되는 문제를 풀기 위한 작은 프로시저(procedure;진행절차) 알고리즘 조건 알고리즘은 아래의 조건을 만족해야 한다 입력 - 알고리즘은 0 도는 그 이상의 외부에서 제공된 자료가 존재한다 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다 효과성 - 알고리즘의 모든 연산들은 사람이 유한한 시간 내 정확하게 수행할 수 있을정도로 충분히..

하노이의 탑 (Tower of Hanoi) 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여있다 아래 두 가지 조건을 만족시키며 탑 전체를 다른 기둥으로 옮겨 다시 쌓는 게임이다 1. 한 번에 한 개의 원판만 옮길 수 있다 2. 큰 원판이 작은 원판 위에 있어서는 안 된다 원리 알고리즘 강의를 들을때 분명 배웠던 내용이지만 (머리가 기억하지 못하니ㅠ_ㅠ ) 다시 공부를 했다 글만 보고는 원리를 한 번에 이해하기 힘들기 때문에 글을 읽은 다음 항상 영상을 찾아보곤 한다 재귀함수랑 하노이의 탑을 이해하기 위해 봤는데 도움이 많이 되었다 [출처:얄팍한 코딩사전] https://www.youtube.com/wat..