그냥혀유 그냥혀유

순열과 조합을 사용하는 문제가 굉장히 자주 등장한다. 순열과 조합을 구하는 탬플릿 사이 사이에 원하는 연산만 추가하면 된다. 이를 정리해두고 자주 보고, 연습해서 필요할 때 빠르게 구현하려고 적어둔다. 1.순열   1.1 순열 - 원소 중복 x  private static void RecursivePermutation(int depth){ //BASE CASE if(depth == r){ //.. 여기서 순열이 완성되면 할 일 // 대표적으로 +1해서 경우의 수를 count한다던지 // 아니면, 해당 순열에 해당하는 값을 쭉 나열한다던지.. }else{ //RECURSIVE CASE ..

달이 차오른다, 가자.  시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB181897592515338.747%문제지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지..

숨바꼭질 시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB247267727514612325.857%문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾..

미로 탐색  시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초192 MB201348921445855744.220%문제N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.입력첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄..

트리의 부모 찾기 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB83195371892614042.465%문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.예제 입력 1 복사71 66 33 54 12 44 7예제 출력 1 복사461314예제 입력 2 복사121 21 32 43 53 64 74 85 95 106 116 12예제 출력 2 복사11233445566  풀이import java.io..

그래프비선형 자료구조 그래프는 정점(V)와  간선(Eege)로 이루어진 자료구조이다. G(V,E)   - 정점(Vertex)는 노드(node)로 표현될 수 있다.  그래프 관련 용어  - 정점의 차수 (Degree)   -> 정점에 연결된 간선의 수  - outDegree / inDegree  -> 정점으로부터 나가는 간선을 outdegree, 정점으로 들어오는 간선을 indegree라고 한다.  - 가중치 그래프(Weighted Graph)    -> 간선에 자중치 혹은 비용이 할당된 그래프         연결된 정점들 간 탐색에 드는 비용이나, 연결 강도를 표현한다.        *가중치 그래프 구현시 객체로 묶어서 표현하면 가독성 좋은 코드를 작성할 수 있다. - 경로 (path)   -> 정점에 ..

N과 M (8)  시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB26145212511820481.261%문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 ..

N과 M (7) 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB22250174521429178.760%문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 1..