나머지 연산 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
참고 문제 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),..
위상 정렬은 정렬 알고리즘의 일종이라고 한다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용되는 알고리즘이라고 한다. 예를 들어, 커리큘럼이 다음과 같이 존재한다고 가정하자. 위 그림을 보면 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등은 하나의 집합이 된다. 여기서 중요한 점은 숫자가 낮은 숫자가 부모 노드라고 한다. 초기 부모 노드의 ..
다이나믹 프로그래밍은 쉽게 말해 점화식이용하는 알고리즘이다. 점화식을 구하는 방법은 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..
확실히 다익스트라 알고리즘에 비하면 쉽긴하다. 다익스트라가 음수는 되지 않는다는 문제점이 있었는데 이걸로 사용하면 될것 같다, 플로이드 워셜의 핵심 코드는 for(int k = 1; k
static void dijkstra(int start) { Queue q = new PriorityQueue(); q.offer(new Node(start,0)); distance[start] = 0; while(!q.isEmpty()) { Node shortest = q.poll(); int dist = shortest.distance; int now = shortest.index; if (distance[now] < dist) { continue; } for(int i = 0; i
우선순위 큐는 일반적인 큐와 달리 철저히 우선순위에 의해 동작한다. 우선순위를 설정하는 방법은 여러가지가 있다. 간단하게 우선순위를 정할 경우, 리스트를 이용해도 된다. List list = new ArrayList(); Collections.sort(list); 이런식으로 작성하면 리스트로 우선순위 큐를 만들 수 도 있다. 하지만 리스트로 이용할시, 많은 시간이 발생한다. 그래서 리스트보다는 힙 자료구조를 이용해서 우선순위 큐를 이용한다. 즉, 이름은 큐이지만 사실은 힙인듯 싶다. 보통 힙 알고리즘은 이런식으로 시작된다. 하지만 이건 아직 힙 정렬을 하지 않는 상태다. 위는 완전 이진 트리라고 하는데 이 부분은 추후에 설명할지도 모르겠다. 아무튼 힙 정렬은 2가지로 구분되는데, 최소 힙정렬과 최대 힙 ..
static void dijkstra(int start) { d[start] = 0; visited[start] = true; for(int j = 0; j 검색 -> 최소 -> 검색... 이런식으로 동작되는 것 같습니다. 뭐 이건 이해가 되지 않아도 상관없습니다. 마지막으로 방문은 그 노드에 방문해서 생기는 것이 아니라 그 노드에서 시작할때 발생하는 겁니다. 다익스트라 알고리즘은 최단거리를 구하는 알고리즘으로 잘 알려져 있지만, 간선(노드와 노드 사이)의 길이가 음수라면 불가는하..