개발 성장 일기 :)

(실버3) DP 감 좀 익히려고 푸는 문제들! https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 생각해보니, 2차원 배열로 풀면 더 깔끔하게 풀 수 있다, d[41][2] d[x][0] : 숫자 x의 0의 갯수 d[x][1] : 숫자 x의 1의 갯수 d[0][0]=1 / d[0][1]= 0 d[1][0]=0 / d[1][1]=1

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Bottom-up 방식과 Top-down 방식이 있다. 아무래도 생각하면서 풀기에는 Bottom-up 방식이 더 쉬운 것 같다. + 똑같이 풀어도 Top-down은 계속 시간초과가 나는데.. 아직 해결 못함 * dp[N] 의 최솟값은 dp[N-1]+1 / dp[N/3]+1 / dp[N/2]+1 중 최솟값이다. 아래는 Bottom-up 방식,, for문을 통해서 계속해서 나아가는 방식! 아래는 top-down 방식 함수내에서, 재귀처럼 계속 호출하는 것이다. ?????? 왜 시간초과 나냐구???????? 오랜만에..

(실버1) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 장마철에 내리는 비는 0부터 100 까지로 설정 (* 비가 안내리는 경우도 있다고 맨 뒤에 써있음.. 이것때문에 마지막 99%에서 틀렸다고 나와서 한참 찾았다..) 2. check함수는 매번 false 로 초기화 시켜줘야하며, ( * 이중 for문으로 초기화 시켰는데, check= new boolean[N][N] 을 사용해서 초기화하면 더 간단한 코드.) - dfs를 실행시키고, 실행 시..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net dfs함수를 호출할 때 마다, 양의 갯수 늑대의 갯수를 초기화 하고 (num_o, num_v) dfs함수 내에서 양의 갯수와 늑대의 갯수를 계산하고 호출이 끝나면 갯수를 비교해서 최종 양의 갯수와 늑대의 갯수를 구한다 (ans_o, ans_v) 1) 양의 갯수 > 늑대의 갯수 : 최종 양의갯수 += 양의 갯수 2) 양의 갯수

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net Step1. 현재 종이 사이즈 안에서 모든 배열의 값이 같은지 확인 : 여기서는 sameCheck 함수 사용 1-1. 같다면, 종이 사이즈 안에서 어떤 값인지 확인 후 ( 1 or -1 or 0 ) 갯수 증가시키기. num1, num2, num3 Step2. 종이를 다시 9등분 해야 하는 함수가 필요 1-1. 현재 위치가 x,y 일 때 아래의 좌표로 총 9번 나뉘어야 ..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 현재 자기값보다 큰 값으로 다음값을 선택해야한다. -> for문에서 현재 인덱스값부터 시작하면 된다. 2. 재귀함수에서 파라미터값을 어떤값을 넣을까? - int? - String? - List ? -> int 형의 현재 인덱스값을 파..

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 1. 재귀함수 돌릴 조건 - 첫번째 시작하는 숫자는 0부터 9까지 모든 숫자가 가능하므로 - 0 부터 9 까지 모든 수를 재귀함수로 돌린다. for(int i=0;i

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net * 풀이 방법 1. 모든 배열을 구해본 후 2. 배열의 차이, abs의 합계의 최대값을 비교한다. * 나는 왜 백트래킹으로 접근했는가? - 우선 모든 배열의 순열을 구한 후에, 아닌 경우 다시 뒤돌아가서(BACK) 구해야 했기 때문에, 백트래킹으로 풀어야 한다고 판단. ===========================내가 나중에 다시 확인하려고 적어두는 내용들====================..

실버1 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 음식물이 있는 칸에 인접된 정점을 모두 탐색해야 한다. -> 모든 정점을 탐색하여 최적의 거리를 구한다 -> DFS 또는 BFS 사용 1. 음식점이 있는 좌표를 arr[x][y]= 1 로 저장 2. arr[x][y]=1 이면서 아직 방문하지 않은 좌표는 DFS 알고리즘을 통해 인접한 정점의 갯수를 구한다. 3. 정점의 갯수를 반환하여 결과값과 비교 ..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이방법 백트래킹 사용 ( 정점을 지나는 경우의 수를 찾고, 아닌 경우 다시 돌아간다.) 1. 모든 정점을 다 지나야 하는 모든 경우의 수를 구하기. 이 때, W[i][j] = 0 인 경우 이동할 수 없음. 2. 모든 정점을 다 지난 후, 최솟값을 구하고 비교하기. 모든 정점을 다 지난 후 제일 첫번째로 돌아와야함 ( 마찬가지로, W[i][j]= 0인 ..