본문 바로가기
[BOJ 2677] 단지번호 붙이기 (2) #include#include#include using namespace std; vector v;int N,cnt;int small_cnt;int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};int arr[30][30] = {0,}; int isVisited[30][30] = {0,}; void dfs(int i, int j){ isVisited[i][j] = 1; for(int k=0; k0 && ny>0 && nx
[Algorithm] 외판원 순회 2098번제출맞은 사람숏코딩풀이풀이 작성풀이 요청재채점/수정채점 현황내 소스강의질문 검색외판원 순회시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB109712271132626.185%문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한..
[Algorithm] 순열 복습 #include using namespace std; int t,n;int isVisited[7];int answer[7]; // 3!과 2!의 모든 경우의 수를 재귀함수를 이용하여 연습하자! void dfs(int depth){ if(depth == n+1){ for(int i=1; i
[Algorithm] 순열 분석 문제서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 입력첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) ) 출력각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다. 예제 입력4 2 예제 출력ab ac ad ba bc bd ca cb cd da db dc [접근] 순열을 스왑..
[BOJ 1242] 소풍 소풍 실패시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB5791369826.776%문제동호와 동호네 반 친구들은 산정호수로 소풍을 갔다. 총 N명이 소풍에 참가했는데, 산정 호수에는 있는 것이 별로 없어서 무대에 올라가기로 했다.무대에 올라간 N명은 1번부터 N번까지 시계방향으로 원형으로 앉았다. 그런 후에, KIN 이란 게임을 시작했다. 이 게임은 1번부터 시작된다. 그리고 한 명씩 시계방향으로 1, 2, ... , M까지 센다. M을 말하는 사람은 퇴장 당한다. 그 후에는 다음 자리에 앉아있는 사람이 1부터 다시 센다. 동호도 이 게임에 K번 학생으로 참가한다. 동호는 자기가 몇 번째로 퇴장 당하는지 궁금해졌다.예를 들어, 5명의 학생이 참가하고 M=2이고, 동호는 3번 학생이라고 하면..
[BOJ 1158] 조세퍼스 문제 조세퍼스 문제시간 제한메모리 제한제출정답맞은 사람정답 비율2 초256 MB156477867592551.928%문제조세퍼스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 이다.N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)출력예제와 ..
[Algorithm] 순열 문제서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 입력첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 26, 0 ≤ r ≤ n ) 출력각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다. 예제 입력4 2 예제 출력ab ac ad ba bc bd ca cb cd da db dc #include#include#in..
[BOJ] 2677 단지번호붙이기 단지번호붙이기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 27242 10442 7068 38.476% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤2..

티스토리툴바