전체 글 (10) 썸네일형 리스트형 A. 탐욕법 (Greedy) 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 핵심은 문제를 풀기 위한 최소한의 아이디어를 떠올리는 것이다. 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있는지 파악해야 한다. 대체로 정렬 알고리즘과 짝을 이루는 경향이 있다. 해법을 찾았을 경우에 해법의 정당성에 대해서 검토해야 한다. 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하자. 그러나 이 해결책이 최선이라는 것은 보장되지 않는다. 반복되는 패턴을 일반화하자. [big-o] 실전 압축 빅오. 그런데 예시를 곁들인. 선형식은 언젠가 상수를 뛰어넘게 된다. 예를 들어 파일의 크기에 따라 전송시간이 증가한다면 선형 시간으로 증가한다고 볼 수 있다. 반면에 파일의 크기와는 상관없이 일정한 전송시간을 가진다면 상수 시간을 가진다고 볼 수 있다. 실행 시간에는 다양한 변수가 포함 될 수 있다 big-o 시간의 상한을 나타낸다. 이것은 작거나 같은 부등호와 비슷한 관계가 있다. 예를들어 김잼민의 나이가 X살 이라고 하고, 사람의 최대 수명이 130살이라고 하자. 이것은 X [백준/BOJ 1074] Z (Java) https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 규칙성을 발견하는게 쉬우면서 어려웠다. 4개의 구역으로 쪼개진 영역을 재귀적으로 방문하는 형식으로 값을 구하면 되겠지 싶었다. 이동볌위는 결국 현재 재귀의 깊이에서 2^N-1만큼 발생하기 때문에 이동하는 값을 1까지 줄여놓는다면 ( 2^0 ) 한칸씩 움직이는 형태로 쪼개낼 수 있다고 생각했다. 또한 재귀 시 파라미터로 필요한 값은 x, y좌표 그리고 현재 재귀에서 이동할 가중치 값이 필요로.. [백준/BOJ 1662] 압축 (Java) https://www.acmicpc.net/problem/1662 입력 예시를 K(Q)라는 규칙에 따라서 쪼개본다면 다음과 같다. 3 3(56 2(7 1(9) ) ) 쪼개진 문자열을 규칙에 맞춰서 변환하는 과정은 다음과 같다. 3 3(56 2(79) ) 3 3(5679 79) 3 567979 567979 567979 반복되는 패턴을 보면서 저 패턴을 일반화 한다면 재귀적으로 문제를 해결 할 수 있겠다고 가닥을 잡았다. 재귀함수를 구현하는 키를 여는괄호와 닫는괄호로 정했다. 또한 반복의 대상이 되는 문자열을 추출하기 위해서 괄호의 여는 부분과 닫는 부분의 index가 필요했다. import java.util.HashMap; import java.util.Map; import java.util.Scanner.. [백준/BOJ 11729] 하노이 탑 이동 순서 (Java) 문제 분석 세 개의 장대가 있다 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 제약 조건에 따라 원판을 첫 번째 장대에서 세 번째 장대로 옮긴다. 제약 조건 한 번에 한개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이동 횟수는 최소가 되어야 한다. 출력 양식 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. K개의 줄에 걸쳐 두 정수 A B를 빈칸을 두고 출력한다. A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻. 발상 가장 밑에 원판이 목적지에 가려면 그 원판을 제외한 나머지 원판들은 순서대로 목적지가 아닌 다른 곳에 쌓여 있어야 한다 재.. 이전 1 2 다음
