coding tasty house

문제설명 땅과 바다의 값을 입력 받은 다음 총 섬의 개수를 구하는 문제이다. 여러번 테스트 케이스를 입력 받을 수 있도록 코드를 짜야하며, 지도의 너비와 높이가 주어진다. 1은 땅, 0은 바다로 간주한다. 이때 땅은 가로, 세로 뿐만 아니라 대각선으로도 갈 수 있다. 알고리즘 1. 지도의 너비와 높이를 입력받는다 2. 지도의 정보(0과 1)을 입력받는다 3. 상하좌우, 대각선 연결된 섬을 찾는다(dfs 알고리즘 사용) 4. 섬의 개수를 센다 5. 지도를 초기화 한다. 코드 #include #include #include #include using namespace std; #define MAX 51 int graph[MAX][MAX]; bool visited[MAX][MAX]; void dfs(int x..

문제설명 vector에 숫자들이 입력되어 있다. 두 숫자의 절대값 차를 계산하여 가장 작은 값을 결과값으로 낸다. 알고리즘 vector sort vector 전체 순회 및 가장 작은 차(min) 계산 min값 반환 알고리즘은 minimumAbsoluteDifference 함수만 확인하면 된다. 코드 #include using namespace std; string ltrim(const string &); string rtrim(const string &); vector split(const string &); /* * Complete the 'minimumAbsoluteDifference' function below. * * The function is expected to return an INTEGE..

문제설명 첫 줄에 연산의 수를 입력 받고, 나머지 수들을 입력 받는다. 이때 0이 들어올 때는 힙에서 가장적은 수를 출력 시킨다. 만약 힙이 없는 경우에는 0을 출력한다. 0외의 숫자가 입력되는 경우에는 힙에 넣는다. 알고리즘 heap 선언, list 선언 총 숫자의 갯수 입력 0인지 여부 판단 후 list에 원소의 수를 세어보고 0이면 0출력, 그렇지 않는 경우 heap에서 꺼냄 0이 아닌경우 heap에서 가장 작은 수 출력 코드 import heapq as hq import sys temp=[] num= int(sys.stdin.readline()) for i in range (num): n= int(sys.stdin.readline()) if n==0: #0이 들어온 경우 if(len(temp))=..

연결 요소의 갯수 문제설명 첫 줄에 노드의 수 , 간선의 수를 입력 받는다. 총 연결된 요소의 갯수를 출력한다. 알고리즘 노드의 수와 간선의 수를 입력 받는다. 연결 여부를 나타낼 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 >..