DennyAn

-문제- -문제 접근-1. 문제 조건 정리벽돌 속성:밑면의 넓이 (정사각형이므로 한 변의 길이와 관계없이 넓이만 고려)높이무게제약 조건:회전 불가: 벽돌을 회전시켜 다른 면을 밑면으로 사용할 수 없음고유성: 밑면 넓이와 무게는 모두 서로 다름쌓는 규칙:밑면이 작은 벽돌 위에 밑면이 큰 벽돌을 올릴 수 없음무게가 가벼운 벽돌 위에 무게가 무거운 벽돌을 올릴 수 없음 출력: 탑에 사용된 벽돌 수와, 탑의 위에서 아래로의 벽돌 번호즉, 탑에서 위로 갈수록 밑면 넓이와 무게가 모두 감소해야하며 벽돌을 조건에 맞게 쌓아최대 높이의 탑 구성해야 되는 문제입니다.  2. 정렬(Sorting)탑의 밑바닥(제일 아래)에는 가장 넓은 밑면과 무게가 가장 큰 벽돌이 오도록 하기 위해 정렬합니다.방법:벽돌들을 밑면 넓이가 큰..

-문제- -문제 접근- 이 문제는 각 곡마다 볼륨을 바꿀 수 있는 두 가지 선택(더하거나 빼기)을 이용하여, N개의 곡을 순서대로 연주할 때 마지막에 도달할 수 있는 볼륨 중 최댓값을 구하는 문제입니다. (단, 항상 볼륨은 0 이상 M 이하) 입력:N: 연주할 곡의 개수S: 시작 볼륨M: 최대 볼륨V[1…N]: 각 곡 전에 조절할 수 있는 볼륨 차이규칙:i번째 곡을 연주하기 전, 현재 볼륨 PPP가 있다면 두 가지 선택이 있음:볼륨을 P + V [i] 로 변경볼륨을 P − V [i] 로 변경단, 변경된 볼륨은 반드시 0 이상 M 이하여야 함출력:모든 곡을 순서대로 연주한 후, 가능한 볼륨들 중 최댓값만약 어떤 선택을 해도 중간에 범위를 벗어나서 연주할 수 없는 경우가 있다면, -1 출력DP정의:dp[j]..

-문제-  -문제 접근- 문제를 보면 지원이는 동주라는 빌런으로 인하여 00타일과 1 타일만을 사용하여 전체 길이가 N이 되는 2진 수열을 만들어야됩니다. 2진 수열을 만드는 경우의 수를 구하고 그 값을 15476으로 나눈 나머지를 출력해야 합니다. 1. 타일로 수열을 생각하기    1-1. 수열의 길이        "1"타일은 길이가 1이고 "00"타일은 길이가 2이며 길이가 N인 수열을 만들기 위해서는 두 개의 타일을 적절히        배치하여 길이의 합이 N이 되어야 합니다.    1-2. 경우의 수 도출          수열의 시작점이 "1"타일일 경우와 "00"타일일 경우가 존재하며            "1타일" = 남은 길이 N-1           "00"타일 = 남은 길이 N-2     ..

-문제-  -문제 접근-n가지 종류의 동전(무한히 사용 가능)을 사용하여, 합이 k원이 되는 경우의 수를 구해야 됩니다. 조건:각 동전은 원하는 만큼 사용 가능.순서만 다르면 같은 경우로 취급.(조합으로 계산을 해야 함) 접근:k원 이라는 목표 금액을 만드는 경우의 수를 점진적으로 구하는 방식으로 접근해야하며 점화식을 구성해야 합니다. dp[j]: 금액 j원을 만들 수 있는 경우의 수  dp[0] =1 : 0원을 만드는 경우로는 아무 동전도 사용하지 않는 한 가지 경우가 있으므로 1로 초기화 해줍니다. 점화식:dp[j] += dp[j-c] (단 j>=c)현재 동전 c를 사용하기 전에 j-c원을 만드는 모든 경우에 동전 c를 추가하면 j원이 된다를 의미합니다. 한마디로 이 식은 동전 c를 추가하기 전, j..

-문제- -문제접근- 위 문제는 주어진 자연수 n을 1로 만들기 위해 필요한 최소 연산 횟수를 DP를 이용해 구하는 문제입니다. 아래의 조건이 중요하며 확실하게 인지를 해야 합니다. n에서 1을 빼는 연산n이 2로 나누어 떨어지면 2로 나누는 연산n이 3으로 나누어 떨어지면 3으로 나누는 연산 d[1] =0 : 1은 이미 목표 값이기에 1을 1로 만드는데 필요한 연산 횟수는 0입니다. 1은 0번의 횟수를 갖기에 for문은 i를 2부터 n보다 작거나 같을 때로 잡아서 위의 조건을 적용시켜줍니다. 1번 조건d[i] = d[i - 1] + 1; : 가장 기본적인 연산인 1을 빼는 것이며 i를 1로 만들기 위한 연산 횟수는 i-1을 1로 만드는 최소 횟수에 1을 더한 값입니다. 2번 조건if (i % 2 == ..

-문제- -문제 접근-1번 컴퓨터로부터 감염되는 컴퓨터 수를 구하는 문제의  DFS(깊이 우선 탐색) 문제입니다. N: 컴퓨터의 수 (1번 ~ N번)M: 네트워크 연결 수 (간선 개수)network: 각 노드(컴퓨터)에 연결된 다른 노드(컴퓨터)의 목록visited: 방문 여부(감염 여부) 체크icom: 감염된 컴퓨터 개수(1번 컴퓨터 제외)  -전체 코드- push_back(): 벡터의 뒤(back) 쪽에 새로운 원소를 추가할 때 사용합니다. dfs 함수: -visited[cur] = true;현재 노드(cur)가 방문(감염) 되었다고 표시 -인접 리스트(network[cur])로 연결된 모든 노드(next) 확인 -감염되지 않은(!visited[next]) 노드 발견 시: icom++ (새롭게 감염되..

-문제-    -문제 접근-  이 문제는 집의 좌표가 주어졌을 때, C개의 공유기를 설치하여 가장 인접한 두 공유기 사이의 거리를 최대로 하는 문제입니다. 즉 가장 인접한 두 공유기 사이 거리가 최대가 되는 배치를 찾아야 합니다.공유기 C개가 사이 거리 X이상이 되도록 배치가 가능한가? = True/False(bool) 판별 필요 = 이진 탐색   1. 입력 받은 집 좌표를 오름차순 정렬  2. 탐색 범위 설정-left(시작) 공유기 사이 간격의 최솟값-right(끝) 가장 오른쪽 끝 좌표 - 가장 왼쪽 좌표(공유기 사이 간격 최대값)  3. 이진탐색 과정mid = (left+right) /2  : 공유기 사이 최소 거리를 mid로 잡는다.  -C개 이상의 공유기 설치 가능left = mid +1: 거리..

-문제-  -문제 접근-노드의 수 만큼 트리를 저장하고, 전위/중위/후위 순회하는 문제입니다. -전체 코드- -코드 설명- -최대 26개의 노드를 배열에 저장 - return &Tree[data - 'A']; 문자열(알파벳)에 'A' -25를 하여  인덱스로 변환하여 Tree 배열에서 반환A=0 번 인덱스, B= 1번 인덱스  -순회는 루트 노드를 언제 방문하는가로 생각하면 됩니다.Preorder: 선 방문Inorder: 중간 방문Postorder: 끝 방문  -END-

-문제 접근-문서에서 특정 단어를 중복 없이 최대 몇 번 찾을 수 있는가? 를 묻는 문제입니다. -전체 코드- -END-

-문제-  -문제 접근-어떤 높이 이상인 지역이 몇 개의 안전한 영역으로 나눠지는지 찾는 문제이며 BFS/DFS를 활용하여 연결된 영역 갯수 찾는 문제입니다. 저는 DFS로 풀었으며 높이(강우량)에 따른 안전한 영역의 최대 개수를 찾는 것이 키 포인트입니다. 1. 최대 높이 설정 2. 각 높이(강우량)에 대해 안전 영역 갯수 찾기.3.모든 높이(강우량)에 대해 최대 안전 영역 갯수를 갱신하면서 찾기. 한마디로 모든 높이에 따른 안전 영역 갯수를 비교하고 갱신하여 최대 안전 영역 개수를 찾으면 됩니다. -전체 코드- -코드 설명-  위에 dx, dy는 상하좌우 이동을 하기 위해서 사용하였으며 x를 열, y를 행으로 생각하시면 이해하시기 편하실 겁니다.그렇게 하여서 dx가 -1, 1인 경우 열을 의미하여서 ..