IT세상

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net dfs를 활용하여 풀었다 #include using namespace std; int n; int graph[26][26]; vector num; int sum = 0; bool dfs(int x, int y){ // 범위 밖인 경우 if(x=n || y=n){ return false; } if(graph[x][y] == 1){ // 집인 경우 sum += 1; // 집 수 +1 graph[x][y..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 방법 길이는 int 형의 범위를 넘어가기 때문에 long long int 형으로 선언해준다 (개수는 상관없음) 문제에서 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 의 예시를 보면, 만들어지는 랜선의 개수를 셀 때 랜선의 길이를 빼는것이 아니라 나눈 몫을 더해주어야 한..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 예제 보고도 문제가 이해안됐는데 이런 뜻이었다 bfs를 이용해서 풀었고 처음에는 출력하는 부분에서 endl 을 썼는데 시간초과가 떴다 그래서 "\n"으로 바꿨더니 통과했다 #include using namespace std; int n; vector graph[100001]; int parent[100001]; void bfs(int n){ queue q; q.push(n); while(!q.empty()){ int x = q.front(); q.po..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 처음에는 n보다 작은 제곱수 중 가장 큰 제곱수부터 차례로 빼는 방법을 사용했는데 그러면 43같은 반례가 나왔다 ex) 43 = 6² + 2² + 1² + 1² + 1² (5개) 43 = 5² + 3² + 3² (3개) 그래서 dp[n]은제곱수 항의 최소개수로 정하고 n에서 작은 제곱수부터 빼주면서 dp[n] = dp[n - 제곱수] + 1 의 최소값을 구했..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 한번에 한계단이나 두계단만 오를 수 있고 연속으로 세계단은 오를 수 없기 때문에 n-3계단에서 n-1을 건너 오는 경우(한계단)와 n-2에서 오는 경우(두계단)의 경우가 있을 수 있다 이 중 점수의 최대값을 구하면 된다 #include using namespace std; int n; int dp[301] = {0}, a[301] ={0}; int main(void) { cin >> n; for(int i=1..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net bfs를 사용하여 풀었고 생각해보니 visited를 안쓰고 if(graph[nx][ny] != 0 && visited[nx][ny]==false) 조건 대신 if(graph[nx][ny] == 1) 조건을 썼어도 됐을 것 같다 #include using namespace std; int n,m; int graph[101][101]; bool visited[101][101]; int dx[] = {-1, 1, 0, 0}; int ..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제는 dfs를 이용해서 풀었다 *이차원배열* arr[0][0]​ arr[0][1]​ arr[0][2]​ arr[0][3]​ arr[1][0]​ arr[1][1]​ arr[1][2]​ arr[1][3]​ arr[2][0]​ arr[2][1]​ arr[2][2]​ arr[2][3]​ #include using namespace std; int w, h; int graph[51][51]; b..

https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 1. 우선 수를 한자리씩 분리한다 참고 : https://develop-me-z.tistory.com/103 [C++] 숫자 한자리씩 분리하기 숫자 쪼개기 10으로 나누면서 10으로 나눈 나머지를 분리해주면 된다 while(a!=0){ int rest = a%10; a /= 10; } develop-me-z.tistory.com 2. 각 자리를 거듭제곱하면서 더해준다 참고 : https://develop-me-z.tistory.com/104 [C++] 수 거듭 제곱하기 (POW 함수) 헤더파일 사용방법 po..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net dp는 수열 a와 같이 초기화해준다 전의 수열 값과 비교하면서 자신의 값보다 작으면 그 값의 dp값에 자신의 값을 더한 것과 자신의 dp값을 비교해 더 큰 값을 넣어주면 된다 #include using namespace std; int n; int dp[1001] = {0}, a[1001] ={0}; int main(void) { cin ..

문제보기 #include using namespace std; int t, n; vector graph[1001]; bool visited[1001]; int result = 0; void dfs(int x){ visited[x] = true; for(int i=0; i> t; // 테스트케이스 수 입력 for(int j=0; j> n; // 순열의 수 입력 for(int i=1; i> x; graph[i].push_back(x); // i와 순열i의 간선 잇기 } for(int i=1; i