coding tasty house

연결 요소의 갯수 문제설명 첫 줄에 노드의 수 , 간선의 수를 입력 받는다. 총 연결된 요소의 갯수를 출력한다. 알고리즘 노드의 수와 간선의 수를 입력 받는다. 연결 여부를 나타낼 graph인 2차배열, 방문여부를 나타낼 배열을 N+1크기만큼 만든다. 간선의 연결 관계를 입력 받고, (2,1)인경우 (1,2)에도 값을 넣는다. 반복적으로 조회하여 방문하지 않은 경우 (False인 경우) dfs 함수에서 동작한다. 연결의 수를 출력시킨다. import sys sys.setrecursionlimit(10000) # 깊이 우선 탐색 def DFS(v): visited[v]=True for e in graph[v]: if not visited[e]: DFS(e) N, M = map(int, sys.stdin.r..

좌표 압축 문제설명 좌표 압축의 개념을 사용하여 주어진 좌표를 압축한 결과를 출력한다. 예제를 보고 좌표 압축의 개념에 대해서 설명하도록 하겠다. 먼저 5개의 수를 입력받고, 좌표 값을 입력 받는다. 첫번째 예제의 경우 크기순으로 나타낸다고 보면 된다. -10이 값이 제일 작기때문에 0번째 인덱스, -9는 1 이런식의 값을 가지게 된다. 다만 유의해야할 점은 중복 된 값이 들어올 수 있다는 점이다. 2번째 예제의 경우 좌표의 값이 중복 되는 케이스이다. 999, 1000이 중복되어 나오는데 이 역시도 포함해서 결과가 나오는 것을 확인할 수 있다. 알고리즘 총 좌표의 수 값을 입력 받는다. list에 좌표 값을 입력 받는다. set(집합)개념을 사용하여 중복좌표 값을 제거하고, 오름차순으로 정렬한다. di..

공유기 설치 문제설명 공유기를 설치하는데, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 값을 구하자 알고리즘 값을 각각 입력 받고 오름차순으로 정렬한다. left를 1로, right를 최대 거리(제일 큰 값-제일 작은 값)로 설정한다. 이분 탐색 알고리즘을 사용하는데, 현재 집의 거리와 mid를 비교하여 더 크면 prev값을 업데이트하고 count를 증가시킨다. count가 알맞은 값이 오면 종료 시킨다. #include #include #include #define MAX 200001 using namespace std; int arr[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, C; cin >> ..

평범한 배낭 문제설명 가방의 최대 수용량을 넘지 않는 범위 내에서 가장 가치가 높은 물건을 가져올 때, 최대 가치를 구하자 알고리즘 값을 각각 입력 받는다. 이중 반복문을 사용하는데, 바깥은 가방의 정보를 저장한 index, 안쪽은 무게 K까지 돈다. i번째 가방의 무게를 조회하고 현재 가방의 무게를 넘으면 이전 값, 그렇지 않으면 max함수로 비교하여 dp그래프를 채운다. 배열의 가장 마지막 값을 출력한다. #include #include #include #include using namespace std; #define MAX 100001 #define MAXN 101 int N, K; int dp[MAXN][MAX]; int main() { ios_base::sync_with_stdio(0); ci..

가장 긴 증가하는 부분 수열 문제설명 가장 긴 증가하는 수열의 길이를 구한다. 알고리즘 값을 각각 입력받고 dp의 값을 길이만큼 1로 초기화 해준다. 이중 for문 안에서 arr값을 하나 불러오고 밖의 for문의 인덱스 만큼 다시 0부터 인덱스까지 값을 조회한다. 값을 비교하여 현재 구하고자 하는 곳의 값이 이전의 수열 인덱스 값보다 큰 경우 max값을 찾아서 업데이트한다. 업데이트할 때 현재의 dp값, 그리고 이전의 dp값 중에 가장 큰 값에 1을 더하고 큰 값을 저장한다. dp중에 가장 큰 값이 최장길이이다. #include #include #include #define MAX 1001 using namespace std; int arr[MAX]; int dp[MAX]; int main() { ios..

RGB거리 문제설명 집에 빨강,초록,파랑으로 색을 칠하려 한다. 위의 사진에서 규칙을 확인하고 모든 집을 칠하는 비용의 최솟값을 출력하라. 알고리즘 값을 각각 입력받고 dp의 값을 저장할 부분인 result에 초기 값을 입력 받은 값으로 설정해준다. 반복문으로 나머지 부분을 각 색깔에 맞춰서 해당 색은 사용하지 않은 가장 작은 전 값에 현재 색을 더해준다. N만큼 진행하고 가장 끝 행에 값들 중 가장 작은 값을 출력시킨다. #include #include #include #define MAX 1001 using namespace std; int N; int graph[MAX][3]; int result[MAX][3];//결과 값을 저장하기 위한 배열 int main() { ios_base::sync_wi..

LCS 문제설명 주어진 두 문자열에서 최장 부분 수열을 구해 출력 시킨다. 알고리즘 값을 각각 입력받고 입력 받은 문자열에 편의를 위해 0을 추가해서 붙인다. 각 첫행 첫열은 0으로 초기화한다. 비교하는 기준 문자열에서 같으면 해당 칸의 대각선 값 +1을 표에 넣는다. 비교하는 기준 문자열에서 다르면 왼쪽, 또는 위의 값 중에 더 큰 값을 찾아서 넣는다. 해당 테이블이 가장 오른쪽 아래 값이 정답이 될 수 있다. #include #include #include #include #define MAX 1001 using namespace std; int lcs[MAX][MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); string A,B; cin >..

곱셈 문제설명 주어진 수 A,B,C가 입력되면 A를 B번 곱한 수를 C로 나눈 나머지를 출력하자 알고리즘 값을 각각 입력받고 POW함수에 인자를 전달해준다. B(제곱 수)가 0이면 1을 반환하고 1이면 A%C를 준다. 위의 두 경우가 아니면 B를 2로 나누고 그 함수의 나머지를 구한다. 위의 값을 짝수일때는 제곱해서 나머지를 구한다. 홀수인 경우 다시 A를 곱해서 제곱수를 짝수로 만들어서 나머지를 구해준다. #include #include //modular 연산 XYmodM=(XmodM*YmodM)mod M using namespace std; long long A, B, C; long long int POW(long long A, long long B, long long C) { if (B == 0) ..

인구 이동 문제설명 각 도시간의 인구이동이 일어나는 데 필요한 일자를 구하자 알고리즘 값을 각각 graph 이차원 배열에 입력 받는다. 무한루프 안에서 여러번 인구이동을 확인하기 위해서 visited 를 초기화하고, 방문 여부 체크를 초기화한다. 방문한적 없는 도시를 만나면 그 도시의 인구수, 현재 연합된 도시의 수, 그리고 도시의 좌표를 저장한다. bfs함수를 실행한다. bfs함수에서는 4방향 다 방문해보고 gap이 L과 R사이에 있는 경우 방문하고 인구수를 구하고 방문 표시를 한다. bfs함수를 돌고 난 뒤 총 나라가 2개이상이면 연합이 결성되었다는 의미로 인구 재분배를 해준다. 연합이 결성되면 결과를 1 증가시키기 위해서 checker를 true해준다. 각 점을 다 돌고 나오면 checker여부를 ..

최소비용 구하기 문제설명 각 도시들의 정보를 입력받고, 출발도시에서 도착도시까지 가는데 드는 최소 비용을 구하자. 알고리즘 값을 각각 입력 받는다. pair형태의 백터 배열에 시작점, 도착점 ,cost를 입력받는다. dist 배열을 INF로 초기화 시켜준다. priority_queue를 사용하여 현재 비용, 시작 도시를 넣어준다. 우선순위 큐에서 비용을 끄내는데 부호를 음수로 설정하고, 현재 도시를 꺼낸뒤 큐에서 지운다. 현재 거리비용이 만약 지금 꺼낸 거리의 비용보다 작으면 넘어간다. 반복문으로 이웃한 부분의 비용과 값을 확인한다. 확인한 값이 최소경로인 경우 거리를 갱신해주고 다시 큐에 넣는다. #include #include #include #include #include #define MAX 10..