알고리즘 문제를 풀면 BFS문제가 많이 출제가 되는 것을 알 수 있다. BFS의 사전적 정의를 생각해보면 Breadth-First Search 너비 우선 검색으로 너비를 우선적으로 검색하는 알고리즘이다. 너비를 구한다는 것이 무슨 말일까? 간단히 생각해서 범위를 확장을 시킨다는 의미다. 확장을 시키려면 어떻게 하는것이 가장 효율적일까? 이것도 생각할 문제이긴 하지만 일반적으로 가장 효율적인 방식은 바이러스 처럼 점염을 시키는 것이 가장 빠를 것이다. 최근에 발생한 바이러스는 코로나바이러스다. 코로나 바이러스의 감염 방식은 여러가지가 있지만, 내가 생각할때 코로나 바이러스가 빠르게 확산을 시킬 수 있었던건 근처에 있는 사람에게 공기중으로 감염이 된것이 빠르게 확산을 시킨 이유가 아닐까 싶다. 이걸 다른 말..
나머지 연산 3 % 2 = 1 말한다. 위 식은 다음과 같다. ((2%2) + (1%2) %2 ) => (0 + 1) % 2 => 1 곱하기도 가능하다. ((3%2) * (1%2) %2 ) => (1 * 1) % 2 => 1 하지만 아쉽게도 나눗셈은 되지 않는다. 사실 나머지 연산을 중심으로 하는 문제는 거의 없다. 다만 이것은 주로 숫자가 너무 커서 나눠야 되는 상황에 유용하다고 한다. 대표적인 문제 www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net - 1로만 이뤄졌다는 뜻은 1, 11,111,1111을 말한다. 약수..
링크드 리스트는 마치 서로 연결되었다는 느낌을 주는 자료구조입니다. 링크드 리스트는 다음과 같이 그릴 수 있습니다. 특이하게 값뿐만 아니라 다음이 어떤 값인지 알고 있습니다. 단순히 나열하는 ArrayList와 비슷하면서 다른 느낌을 줍니다. 위 그림은 링크드 리스트에 node가 한개일때를 보여줍니다. 그렇다면 3~4개로 늘어나게 되면 어떻게 될까요? 이런식으로 그릴 수 있습니다. 생성 하얀선을 통해 다음값의 값을 알아내는 느낌입니다. 이제 구현해 봅시다. 처음에는 노드는 한개라고 생각해봅시다. public class LinkedList { private Node head; private Node tail; private int size; private class Node { int value; Node..
int[][] locateBy90(int[][] key) { int n = key.length; int[][] clone = new int[n][n]; for(int i = 0; i
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 이 문제는 사이클의 갯수를 구하는 문제이다. 예를들어 이런 그래프가 있다고 가정해보자. 그리고 연결되어 있는 노드의 갯수를 세보자 정확히 2개가 나온다. 왜냐하면 노드 1과 노드 2가 연결..
참고 문제 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 이 문제를 풀다가... 숫자를 회전을 해야하는 상황이 발생하였다. 원래는 String배열에 값을 넣은뒤 값을 이동시키는 방법을 사용했었는데 이 방법을 사용할시 시간 초과가 발생하였다. 그렇기 때문에 이 방법을 인터넷에서 방법을 찾았다. 시간이 조금 지나고 나니 정답으로 처리되었다. new Node((n % 1000 ) * 10 + n / 1000 , str + "L"), new Node((n % 10) * 1000 + (n / 10),..
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 ..
위상 정렬은 정렬 알고리즘의 일종이라고 한다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용되는 알고리즘이라고 한다. 예를 들어, 커리큘럼이 다음과 같이 존재한다고 가정하자. 위 그림을 보면 B를 배우기 위해서는 A가 반드시 필요하는 것을 알 수 있다. 위상 정렬을 알기 전에 진입차수라는 것을 알 필요성이 있다. 진입 차수란 특정한 노드로 '들어오는' 간선의 갯수를 의미한다. 따라서 위상 정렬은 다음처럼 동작한다. 1. 진입 차수가 0인 노드가 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드을 큐에 넣는다. 이것을 코드로 표현해보자. void topol..
크루스칼 알고리즘의 다른 말로는 최소 신장 트리 알고리즘이라고 한다. 그러면 신장 트리는 무엇일까? 신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 사실 이건 트리의 성립 조건이라고 한다. (내가 생각할 때 신장 트리는 몇 개의 선만 더 추가 되면 사이클이 되는게 일반적인 트리와 차이점인 것 같다.) 보통 크루스탈 알고리즘은 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있을때 사용이 된다고 한다. 이런식으로 각 노드를 방문하려면 23,25.13의 비용이 발생한다고 한다. 이들을 모두 방문하는 경우중 가장 작은 것이 무엇이냐라고 물어보는 것 과 최소 트리값을 찾는 것 은 같다. 즉, 23 + 13 이 된다 위 그림은 3개중 하나가 제거 되야 크루..
솔직히 아직 이것을 왜 사용해야하는지 잘 모르겠다. 일단 설명을 해보자. 서로소는 서로 나누었을 때 1이 나오는 값을 뜻한다. 예를들어 5와 8이라는 숫자를 봤을 때 이들은 서로소이다. 즉, 최대 공약수가 1인 경우가 서로소 라는 뜻이 된다. 만약에, 3이랑 27 같은 경우 최대 공약수가 3이기 때문에 서로소 가 아니다. 서로소 집합을 구하려면 2가지 방법이 필요 하다고 한다. 1. 합집합 연산을 확인라여, 서로 연결된 두 노드를 확인한다. 2. 모든 합 집합 연산을 처리 할 때까지 1번 과정을 반복한다. 현재 전체는 위와 같다. 그리고 현재 합집합은 다음과 같이 나와 있다. 이제 1과 4, 2와 3등은 하나의 집합이 된다. 여기서 중요한 점은 숫자가 낮은 숫자가 부모 노드라고 한다. 초기 부모 노드의 ..
문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 ..
다이나믹 프로그래밍은 쉽게 말해 점화식이용하는 알고리즘이다. 점화식을 구하는 방법은 2가지가 있는데 탑다운 방식과 보텀업 방식이 있다. 탑다운 : -> 큰 문제를 해결하기 위해 작은 문제를 호출 한다. public class Top_Down { static long d[] = new long[100]; static long fibo(int x) { System.out.print("f(" + x + ')' + " "); if (x == 1 || x == 2) { return 1; } if (d[x] != 0) { return d[x]; } d[x] = fibo(x-1) + fibo(x-2); return d[x]; } public static void main(String[] args) { System.o..