N

N과 M (4) 성공분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 512 MB 10231 8310 6815 81.715% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 15650과 같은 DFS 문제 eunchanee.tistory.com/118 (백준 c++) 15650 N과 M(2) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. DFS를 이용해 문제를 풀면 된다..! 백트래킹 기법. 1부터 N까지 순회하면서 check 배열로 방문 여부를 확인하고 값을 넣어주면 된다. #include #include #include using namespace std; in..

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..

DFS 문제. 전역변수로 bool형 visited[10001]을 선언하여 false로 초기화. 마찬가지로 vector answer, int max_count = 0으로 선언하여 사용하기 쉽게 만든다. 우선 sort를 수행한다. 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택하기 편하도록 하기 위함이다. 그리고 임시변수 tmp를 선언하고, dfs 함수에 전달. 처음에는 "ICN"에서 출발하기 때문에 dfs(tickets, tmp, "ICN", 0)으로 호출한다. dfs함수를 재귀적으로 호출. for문을 돌면서 start와 같으면서 방문하지 않았다면 visited[i] = true로 바꿔주고, dfs 함수에 다음 목적지를 전달하도록 해주면 알아서 재귀적으로 답을 찾아준다. #include ..

dfs를 이용하여 문제를 풀어야 한다. 형태는 void dfs(vector& numbers, int target, int sum, int count) 이다. 처음 시작할 때는 sum은 0, numbers의 인덱스를 0으로 시작한다. dfs 내부) 우선 종료 조건을 선언하자. numbers의 익덱스를 나타내는 count가 numbers.size()인지 확인하면 된다. 그리고 현재 sum이 target과 같으면 answer++을 해주고 return을 시키면 알아서 카운팅이 된다. 만약 count가 numbers.size()보다 작다면 계속 탐색을 해야한다. 현재 sum에 + numbers[count]와 - numbers[count]를 하여 target과 같은지 탐색하면 끝..! #include #includ..

우선 numbers를 내림차순으로 정렬을 하도록 하였다. 그러면 numbers의 최대값이 나오고, int형으로 변환하여 max 변수에 저장하였다. 그리고 for문과 전역변수로 선언한 prime 배열을 이용하여 2 ~ max 사이에 있는 소수를 false로 바꿔주도록 한다. (for문과 배열을 이용하여 소수 찾는 형태는 외워두면 알고리즘 문제에서 유용하게 쓸 수 있다..!) for(int i = 2; i