104%

이게 초등부 문제라는게 ... 참 대단한것 같다. 우선 스도쿠가 무엇인지는 문제에 나와있으니까 쉽게 이해할수있을거라고 생각한다. 우선 빨간색 부분이 비어있을때 형광펜으로 칠해진 부분에서는 절대 같은 숫자가 나와서는 안되는것이 스도쿠의 규칙이다. 나는 처음에, 빨간색 부분에 여러개의 숫자가 올 수 있다는것을 놓친 상태에서 그냥 단순 반복문으로 형광색으로 칠해진 부분에 없는 숫자가 무엇인지 찾아서 그 숫자를 빨간 부분에 박아 넣었다. 이렇게 하니까 당연히 틀렸다. 문제를 잘 못 이해한것이다.빨간색 부분에 여러개의 숫자가 올 수 있다는것을 알게 되었고 이 문제는 결국 dfs를 활용한 완전 탐색 문제구나라는 생각이 들었다. 왜냐면 이런 빨간색 부분이 전체 판에 여러개가 있을 수 있고 각 빨간색 부분은 여러개의 ..

시간복잡도T(n) = n^2+n+1;와 같이 표시 한다. 입력 데이터의 개수 n에 대해서 이 알고리즘을 수행했을때 얼마만큼의 시간이 걸릴지 대략적으로 파악할 수 있다.즉 만약 3개의 입력 데이터가 존재한다면 9+3+1=13 정도의 연산 횟수가 필요하다는 것이다. 이 시간복잡도를 통해서 이 알고리즘이 얼마나 오래 걸릴지 추정해볼수있다. 빅오 표기법(O(n)) 위의 시간복잡도 함수 T(n)에서 사실 최고차항이 시간복잡도 계산에 가장 큰 영향을 미친다.즉, 대략잡아서 보면 입력데이터 n의 개수가 늘어남에따라서 n^2+n+1중에서 n+1항은 어차피 이 함수의 결과에 영향을 덜 주기 때문에 최고차항만을 가지고 시간복잡도를 대략적으로 측정해보자는것이다. 그럴때 사용하는것이 빅오 표기법,세타 표기법, 오메가 표기법등..

카운팅 정렬 배열 A = {4 8 3 2 1 10} 이 있다고 할때 Arr 0 1 2 3 4 5 6 7 8 9 10 N이 1만이고 K가 1억이라고 해보자. 그럼 이 알고리즘은 그냥 1억짜리 알고리즘이다. 그러니까 N과 K가 비슷하거나 비례할때만 사용하는것이 좋은 알고리즘이다. 기수 정렬 (Radix sort) 기수 정렬은 각 배열의 원소의 1의 자리를 기준으로 정렬을 쭉 해주고 그다음은 10의자리를 기준으로, 그다음 100의자리..이런식으로 배열 내의 원소중 가장 길이가 긴 원소까지 반복해서 정렬을 해야 하는 알고리즘이다. 무슨 말이냐면 100 4 5 20 30 4000 20 1 3 이런 배열이 있다고 하자. (A) 이 배열에서 기수 정렬을 하려고 할때 먼저 1의 자리를 기준으로 정렬한다. 그럼 첫번째 ..

이 문제는 dp로도 풀수 있고 비트마스크로도 풀 수 있는 문제이다.dp로 풀 경우에는 각 열을 증가시키면서 새롭게 나타나는 새로운 패턴을 더해주어야 한다. dp로 푸는 방법은 이해가 잘 안가서 포기 했고, 대신에 비트마스크를 활용해서 풀었다. http://joonas-yoon.blogspot.kr/2016/03/2718.html이블로그에서 너무 잘 설명해 놔서 따로 설명하진 않겠다. 재귀 호출하면서 중복된 호출을 피하기 위해서 메모이제이션 까지 구현해야 하는 상당히 좋은 문제인듯하다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include using namespace std;i..

클릭 위의 링크에 이분 매칭에 대해서 너무 잘 설명 되어 있기 때문에 한번 읽고 오는 것을 추천한다. 위의 문제는 해석해보면 다음과 같다. 1,2,3,4,5번 총 5명의 사람이 있고 1,2,3,4,5의 총 5개의 작업이 존재한다. 각각의 작업과 각각의 사람이 1:1로 매칭되어 어떤 한 사람이 한 작업을 처리할수 있게끔 매칭하는것이 목적이다. 예를 들어 위의 예제에서1번 사람은 1,2번 작업을 처리할수 있고2번 사람은 1번 작업만을 처리할수 있다고 예제 입력이 되었다. 이 상황에서 1번사람이 2번작업을 처리하고 2번사람이 1번작업을 처리하게끔 매칭 시켜주면 된다. 이분 매칭이라는 의미는 어떤 그래프에서 노드들의 그룹을 두개로 나눴을때 각 그룹내에서는 엣지가 생기지 않고 그룹끼리의 엣지만 존재하게끔 노드를 ..

재귀를 연습하기 좋은 문제. 하노이 탑은 유명한 재귀 호출 문제이다.규칙은 다음과 같다 기둥이 3개가 있는데 1번 기둥에 1,2,3번 원판이 꽂혀있다. 1

이 문제는 굉장히 장황하게 써있지만 해석을 해보자면 다음과 같다. 예제를 예로 설명 하면 맨처음에 6과 3이 입력되는데, 이 6은 노드의 개수이다. 총 6개의 노드가 있는데, 그 다음줄에 보면 1 4 3 이 입력된다. 1->4를 갈수 있고 4->3으로 갈수 있다는 의미이다. 마찬가지로 6->2 2->5 5->4 2->3 과 같은 그래프를 얻어 낼 수 있다. 위상 정렬이라는 것은 그래프에서 노드들의 순서를 뽑아내는 작업이다. 예를 들어 그래프가 6->2 2->5와 같이 연결되어 있다면 6번 노드를 처리한다음에야 2번 노드를 처리할수 있고 2번노드를 처리한 다음에야 5번노드를 처리할수 있다는 의미이다. 이런식으로 쭉 나열하게 되면 6번 2번 1번 5번 4번 3번 순서대로 처리를 하면 위의 조건을 모두 만족시..

이 문제는 플로이드 와샬 알고리즘을 적용시키는 엄청 기본적인 문제이다. 플로이드 와샬 알고리즘은 All pair Shortest Algorithm이다. 다시말해서, 어떤 점에서 다른 모든 점으로 가는 최단경로를 모두 구하는 문제이다. (어떤 쌍에 대해서도 최단경로를 알 수 있음) 3중 for문을 사용하기 때문에, 시간복잡도는 O(n^3)이다. 이전 포스팅에서 자바로 구현한 플로이드와샬 알고리즘에 설명이 자세히 나와있으니 참고 바란다. 위의 문제에서는 1 4 와 같은 형식으로 사람1과 사람4가 친구라는것을 표현하고 있다. 이것을 알고리즘에서는 그냥 노드1 노드4의 가중치가 1이라고 표현해놓고 플로이드 와샬 알고리즘을 적용시키면 된다. 소스코드123456789101112131415161718192021222..