DennyAn

-문제- -문제 접근- 이 문제는 2차원 보드에서 1로 표시된 영역을 찾고, 이들로 이루어진 연결된 영역의 개수와 그 중에서 가장 큰 영역의크기를 구하는 문제 입니다.  입력:n x m 크기의 격자가 주어지며, 각 칸은 0 또는 1의 값을 가집니다.문제 접근:탐색 과정에서 같은 칸을 여러 번 방문하지 않도록 하기 위해 방문 여부를 체크할 방문 배열 필요순회격자의 각 칸을 순회하면서, 만약 해당 칸이 1이고 아직 방문하지 않았다면, 새로운 영역의 시작점으로 간주새로운 영역이 발견될 때마다 영역의 개수(num)를 증가영역 탐색 (BFS):BFS(너비 우선 탐색)를 이용하여 해당 영역의 연결된 모든 1들을 방문시작점을 큐에 넣고, 큐가 빌 때까지 반복하며 4방향(상, 하, 좌, 우)으로 인접한 칸들을 검사범위..

-문제--문제 접근-위 문제의 요구사항을 크게 볼 때 조합 생성과 조건 검사 두 가지로 볼 수 있습니다.1. 조합 생성각 암호는 주어진 C개의 문자 중에서 L개를 선택한 조합을 말합니다.2. 조건 검사조건:모음: 최소 1개 이상자음: 최소 2개 이상오름차순 정렬모든 가능한 조합을 생성하고 문제의 조건을 검사하여 출력을 해야되는데 이러한 경우에 백트래킹을 사용하여 구현할 수 있습니다. 3. 백트래킹재귀 함수를 이용하여 인덱스 순서대로 문자를 선택하면서 조합을 구성하고 기저 조건: 선택한 문자의 개수가 L개 가 되었을 때 모음과 자음을 확인하며 조건 검사를 수행해야 합니다.조건 검사 수행 후 만족했다면 문제에서 찾고자 한 가능성 있는 암호를 출력 할 수 있습니다. -전체 코드-#include #include..

-문제-   -문제 접근- 1. 문제 조건위 문제는 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다.퀸이 놓여진 행과 열 그리고 대각선 방향에는 아무것도 놓여있으면 안되는 조건을 가지고 있습니다.2. 문제 접근문제를 처음 봤을 때는 NxN의 체스판이라 당연히 2차원 배열을 생각해보게 되지만 문제의 조건에 조금 더 생각해보면 "각 행에 하나의 퀸만 놓을 수 있다" 라는 조건이 있으므로 각 행에 대해 열 번호만 저장하면 체스판의 모든 좌표를 표현 할 수 있습니다.  예시) n = 3 일때 board[0] =1 하면 0번째 행, 1번째 열에 퀸이 있다를 의미하게 됩니다. 문제 조건 적용을 하면 같은 열에 퀸이 위치 할 수 없기 때문에 board[0] = 0 이면  b..

-문제- -문제 접근-1. 문제 이해 입력 조건:여러 테스트 케이스가 주어집니다.각 테스트 케이스의 첫 번째 숫자 k는 집합 S에 포함된 원소의 개수입니다. (6 k 그 다음 k개의 숫자가 주어지며, 이 숫자들은 오름차순으로 정렬되어 있습니다.입력의 마지막 줄에는 0이 주어지며, 이 경우 테스트 케이스가 종료됨을 의미합니다.출력 조건:각 테스트 케이스마다 집합 S에서 6개를 선택하는 모든 조합을 사전 순으로 출력합니다.각 조합은 한 줄에 출력되며, 조합 사이에는 빈 줄을 하나 출력해야 합니다. 위 문제는 주어진 집합 S에서 6개의 숫자를 골라 모든 조합을 구하는 문제입니다. 2. 접근 방법조합 생성순서에 상관없이 주어진 집합에서 특정 개수의 원소를 선택하는 경우의 수BacktrackingRecursive..

-문제- -문제 접근-1부터 N까지의 숫자 사이에 세 가지 기호(공백, '+', '-')를 삽입하여 생성된 수식의 결과가 0이 되는 모든 경우를 찾아야 하는 문제입니다. 1. 백트래킹백트래킹(재귀) 기법을 사용하여 1부터 N까지 숫자 사이의 (N-1)개 위치마다 가능한 3가지 기호(공백, '+', '-')를 모두 삽입하는 경우의 수를 생성합니다.재귀 호출을 통해 한 단계씩 숫자를 추가하면서 완성된 수식을 만들고, 최종 숫자(N)에 도달하면 해당 수식을 평가합니다.2. evaluate 함수생성된 수식은 공백, '+' 및 '-'를 포함합니다.공백 처리: 공백은 인접한 숫자를 연결하여 하나의 수로 만들어야 합니다. ("1 2"는 12)연산 처리: '+'와 '-'를 만날 때마다, 지금까지 이어진 숫자를 정수로 ..

-문제- -문제 접근-배열 분할:전체 배열의 크기는 2^N × 2^N입니다.배열을 4등분하면 각 사분면의 크기는 2^(N-1) × 2^(N-1)가 됩니다.사분면 판별:현재 배열의 행의 중앙을 기준으로 r의 값이 작은 경우는 위쪽, 큰 경우는 아래쪽입니다.열의 중앙을 기준으로 c의 값이 작은 경우는 왼쪽, 큰 경우는 오른쪽입니다.이를 통해 (r, c)가 속하는 사분면은 아래와 같이 결정할 수 있습니다:0번 사분면 (왼쪽 위): r 1번 사분면 (오른쪽 위): r 2번 사분면 (왼쪽 아래): r ≥ half, c 3번 사분면 (오른쪽 아래): r ≥ half, c ≥ half방문 순서 오프셋 계산:각 사분면은 전체 방문 순서에서 연속적인 블록을 차지합니다.사분면 하나의 크기는 (2^(N-1)) × (2^(N..

-문제-  -문제 풀이-점화식을 주었으며 조건에 맞게 값을 구하면 됩니다.크기가 45보다 큰 배열을 선언하여 루프문에서 피보나치 수를 넣어주고 n번째 값을 구하면 됩니다. -풀이 코드-

-문제- -문제 접근-이 문제는 N번의 정점으로 가는 최단 경로에서 주어진 두 지정 정점(v1, v2)를 거쳐야되는 조건이 들어 있는 문제로두 지정 정점을 지나는 최단 거리를 구하는 문제입니다. 조건:그래프는 방향성이 없는 (양방향) 가중치 그래프입니다.한 번 방문한 정점이나 간선을 다시 방문할 수 있으며 전체 경로는 최단 경로여야 합니다.문제의 조건에 따른 경로의 경우 경우 1: 1 → v1 → v2 → N경우 2: 1 → v2 → v1 → N두 경로 중 더 짧은 경로의 거리를 구하면 된다는 것을 알 수 있습니다. 접근 방식:인접 리스트각 정점을 배열의 인덱스로 관리하고, 각 정점에 연결된 간선들을 구조체(Edge)를 사용하여 저장합니다.다익스트라시작 정점에서 다른 모든 정점까지의 최단 거리를 구하며 ..

-문제- -문제 접근- 문제에서 강산이가 입력한 키에 일반 문자, 백스페이스, 를 순서대로 처리하여 최종 문자열을 복원을 해야 되는 문제입니다.  -문자열 접근-이 문제를 처음 접근할 때 가장 단순한 방법인 일반 문자열을 떠올릴것 입니다.하지만 일반 문자열을 사용하게 되면 중간에 문자를 삽입하거나 삭제하게 되면 모든 문자들을 이동시켜야 하므로 최악의경우 O(n)의 시간복잡도를 가질 수 있기 때문에 매우 비효율적입니다. -두 개의 스택 사용-문제에서 커서의 위치를 중점으로 두 스택으로 좌 우를 관리하면 커서의 이동은 스택 간의 이동으로 구현이 됩니다.push와 pop의 연산은 O(1)이므로 총 시간 복잡도가 입력 키의 개수를 L이라면 O(L)을 가지게 되므로 효율적입니다. 문자열 총 시간 복잡도: 입력 키..

-문제- -문제 접근- 1. 문제이해 입력:첫 줄에 정수 n (1 ≤ n ≤ 100,000): 스택에 넣을 숫자의 개수이후 n개의 줄에 걸쳐, 목표 수열의 각 원소(1 이상 n 이하, 중복 없음)가 주어진다.출력:목표 수열을 만들기 위해 수행한 연산을 한 줄에 하나씩 출력한다.push 연산은  +pop 연산은  -만약 수열을 만들 수 없는 경우에는 NO를 출력한다.2. 문제 접근 스택(LIFO):스택은 마지막에 삽입한 요소가 가장 먼저 삭제됩니다.따라서, 원하는 출력 수열을 만들기 위해서는 스택에 push할 때 반드시 오름차순으로 1부터 n까지 순서대로 넣어야 합니다.연산 결정:목표 수열의 각 target을 하나씩 처리하면서 Push와 Pop으로 나눠 진행합니다.Push 단계:현재 스택에 아직 push하..