전체 글

-내 생각 솔직히 문제에 대한 이해는 어느정도 쉽다고 생각한다. 프렉탈 형태의 별들을 나눠서 생각해보면 규칙은 금방 찾을 수 있을 것이다. 그러나 재귀적으로 이를 구현하는데 있어서 너무 어려워 다른 분들의 코드를 많이 참고했으며, 완전히 이해되지 않았기 때문에 지속적으로 해설해봐야 할 것 같다고 생각한다. -해법 n으로 입력받은 3의 제곱을 이용하여 각 점에 맞게 위치를 움직이는게 중요한 것 같다. 예를들어 n이 3일 경우 별의 시작은 (0,0)부터이며, n이 9일 경우 시작은(0,0) , (0,3) , (0,6) , (3,0) , (3,3) , (3,6) , (6,0) , (6,3) , (6,6) 부터이다. 이와 같은 특징으로 3x3의 크기로 반복해서 출력한다고 생각하면 되는데 재귀 호출시마다 시작점으..

-내 생각 반복문을 통해서 증가시키면서 확인하려고 했으며, 증가 값이 n%10 = 6인 경우, 예를 들어 6일 때는 66을 뒤에 붙이고 마지막 자리는 0~9를 채우는 식으로 하려고 했었는데, 너무 복잡한 방식이었다.... -해법 결국 문제에 답이 있었다. 666이라는 숫자는 무조건 연속해야 하기 때문에 단순히 숫자를 증가시키면서 666이 포함되어있는 경우에 입력받은 n을 감소시키면 되는 거였다... import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n= sc.nextInt(); int num=0; // 증가 숫자 while(n>0) { /..

-내 생각 이 문제 역시 브루트 포스로 분류되어있는 문제로, 문제 자체의 이해는 완벽하다고 생각했다. 요약하자면, m*n 크기의 보드판이 있을 때, 8*8 크기의 체스판으로 뜯어 냈을 때 규칙에 맞추기 위해 칸의 색을 최소한으로 수정해야 한다는 소린데, 이 과정에서 개인적으로 간과한 부분이 바로 체스판의 (0,0)은 하얀색 또는 검은색으로 시작할 때 시작이 하얀색인 과정에서의 횟수와 검은색일 때 횟수 중 최솟값을 찾는 것이었다. 처음에 나는 보드에서 떼어낸 체스판의 시작만을 보고 규칙과 비교하여 횟수를 반환했는데, 그것이 아니라 체스판의 시작이 무엇이든 두 가지 규칙과 비교해봤어야 했다는 소리다. 말로 설명하기 굉장히 힘든데 예를들어 예제 입력 2에서 8x8의 크기로 체스판을 (0,0) ~ (10 - 8..

-내 생각 브루트 포스 분류로 된 문제로 간단하게 요약해보자면, n명의 사람에게 몸무게와 키를 입력받고 다른 사람과 비교하여 자신보다 몸무게와 키가 큰 사람의 수 +1 이 자신의 등수가 되며 이를 공백을 기준으로 출력하는 문제이다. 배열에 저장해 정렬 라이브러리를 사용하면 쉬울 수 있지만, 브루트 포스 방식으로 모든 경우의 수를 따지기 위해 모든 비교를 수행하고자 했다. -해법 모든 사람과 비교하기 위해 반복문 2개를 중첩하였고, 각 경우의 수를 비교하여 자신보다 덩치가 큰 사람이 나올 때 마다 카운트하여 비교가 끝났을 때 +1 하여 자신의 등수를 결정한다. 코드를 보자. import java.util.*; public class Main { public static void main(String[] a..

-내 생각 우선 알고리즘 공부를 시작하면서 자연수 n이 있을 때 각 자리수를 추출하는 방식은 공부했기 때문에 알고 있어서 푸는데 어려움은 없었다. 다만 반복문을 만들 때 범위를 어디까지 해야할까 생각해봤는데 자연수n의 범위가 1부터 1,000,000까지 였기 때문에 최소한 1,000,000을 넘는 생성자는 없다고 생각했다. 1,000,000의 경우에는 1,000,000+0+0+0+0+0+0+1 = 1,000,001이기 때문에 문제에서 주어진 자연수n의 범위를 초과하게 된다. -해법 비교적 간단하기 때문에 코드만 보고 이해가 가능할 것 같다. import java.util.*; public class Main { public static boolean create(int x,int n) { // 생성자를 ..

-내 생각 완전 탐색(브루트 포스) 알고리즘 분류에 있는 문제이다. 브루트 포스 알고리즘은 모든 경우의 수를 탐색하는 알고리즘이므로 문제에서 3장의 카드를 뽑는다 했으므로, 3장의 카드에 들어올 수 있는 모든 경우의 수를 따져보고자 했다. 이때, 3장의 카드는 5, 6, 7이나 6, 5, 7 이나 어차피 최종적으로 모두 합친 값으로 m과 비교해야하기 때문에 탐색을 위한 반복문 3개 중 두 번째와 세 번째 반복문은 항상 앞의 반복문보다 +1 된 상태로 시작하게 한다. 또한 끝나는 부분은 세 장은 세 자리의 숫자를 의미하므로 첫 번째 반복문은 2번째, 3번째 자리의 숫자만큼 공간이 있어야 하므로 끝까지 비교하지 않고 끝에서 -2 한 인덱스 까지만 비교하게 하며 2번째 반복문 역시 마찬가지다. 문제에 대한 해..

-다이나믹 프로그래밍이란? 솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구..

-이진트리란? 트리의 한 종류로써 대표적인 비선형 자료구조의 형태로 1개의 데이터에 대해 0, 1, 2개의 자식 노드를 가지는 트리를 말한다. 이진트리는 일반적으로 탐색을 할 때 많이 사용하는데 그 이유는 특정 데이터를 탐색하고자 할 때 좌, 우로 나뉘어서 탐색하기 때문에 한쪽을 일방적으로 제외할 수 있어 빠른 탐색속도를 가지게 된다. 이진트리의 구현은 일반적으로 배열과 노드를 이용해 구현이 가능하지만, 완전 이진트리를 제외하고는 배열을 사용할 때 많은 메모리 낭비가 발생하기 때문에 노드로 구현하는 것이 좋다. -이진트리의 순회방식 이진트리의 순회방식으로는 3가지가 존재하는데 1)전위순회, 2)중위순회, 3)후위순회이다. 이는 탐색하는 순서에 따라 구분되며 D를 현재의 노드, L을 왼쪽 자식노드,R을 오..

-내 생각 알고리즘 초보자로서 그리디 알고리즘에 진입하고 나서부터 무언가 굉장히 헷갈리고 자신감이 사라졌다.. 문제를 이해하는데 많은 시간이 걸리지 않았지만, 어떻게 해결해야 할지 너무 막막해서 곧장 다른 분들의 블로그를 통해 문제를 정확하게 이해할 수 있었다. 똑같은 크기의 2차원 배열 A, B가 일치할 때까지의 변환 연산의 횟수를 구하는 것이 핵심인데 변환 연산은 3X3의 고정된 크기로만 변환이 가능하다. 처음에 다른 블로거 분들의 설명을 봤을 때는 '왜 (0,0)부터 뒤집기 시작하지?' 생각했는데, 생각해보면 3X3으로 고정되어있기 때문에 뒤집은 똑같은 3X3의 공간을 다시 뒤집는 바보 같은 짓(정말 똑같은 공간, 걸치는 공간은 몇 번이든 뒤집어질 수 있다.)을 제외하면 결국에는 각 원소가 뒤집어 ..

- 크루스 칼(Kruskal) 알고리즘이란? 크루스 칼 알고리즘이란, 각 정점을 최소 비용으로 연결시키는 최소 비용 신장 트리를 만드는 대표적인 알고리즘으로 일반적인 그래프에서 각 정점을 연결하는 간선에 비용을 추가해 최소 비용으로 모든 정점을 순환하는 그래프로 만드는 것이다. 크루스칼 알고리즘으로 그래프를 구현할 때 비용은 최소가 되어야 하기 때문에 두 정점과 그 간선에 소모되는 비용을 하나의 클래스로 정의하여 비용을 기준으로 오름차순 정렬을 한 후 가장 적은 비용부터 차례대로 정점을 연결해 나가면 된다. 또한 각 정점에서 사이클이 발생하지 않고, 간선의 수가 정점의 수 -1 개가 연결될 때까지 진행한다. 정점의 수 -1 개의 간선이 연결되면 모든 정점이 연결될 수 있기 때문이다. 이때 사이클의 발생여..