1. int[,] vs int[][]int[,] - 다차원 배열int[,] arr = new int[3, 4]; // 3행 4열 고정arr[0, 0] = 1;모든 행의 열 크기가 동일메모리가 연속적으로 할당선언 시 0으로 자동 초기화크기 구하기arr.GetLength(0); // 3 → 행의 수arr.GetLength(1); // 4 → 열의 수int[][] - 가변 배열 (jagged array)int[][] arr = new int[3][];arr[0] = new int[4]; // 각 행마다 크기 다르게 가능arr[0][0] = 1;각 행의 열 크기가 달라도 됨행마다 개별적으로 메모리 할당크기 구하기arr.Length; // 3 → 행의 수arr[0].Length; // 4 → 0번..

https://www.acmicpc.net/problem/1753문제 설명방향 그래프에서 시작점 K에서 다른 모든 노드까지의 최단 거리를 구하는 문제이다.다익스트라 알고리즘이란?하나의 시작점에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.핵심 아이디어아직 방문하지 않은 노드 중누적 거리가 가장 짧은 노드를 선택해서 처리!동작 과정그래프:1 --2-- 2| |4 1| |3 --1-- 4시작점: 1dist = [0, ∞, ∞, ∞] 1 2 3 41단계: dist가 가장 작은 1번 선택 → 2번 갱신: dist[2] = 0+2 = 2 → 3번 갱신: dist[3] = 0+4 = 4 dist = [0, 2, 4, ∞]2단계: dist가 가장..

https://www.acmicpc.net/problem/12015문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 의 길이를 구하는 문제이다.A = {10, 20, 10, 30, 20, 50}LIS = {10, 20, 30, 50} → 길이 4N이 최대 1,000,000이므로 시간 제한 1초 안에 풀려면 효율적인 알고리즘이 필요하다.1차 구현 - DP (O(N²))아이디어dp[i] = arr[i]로 끝나는 LIS의 최대 길이dp[i] = max(dp[j] + 1) (j 코드using System;public class BaekJoon{ static void Main() { int N = int.Par..

https://www.acmicpc.net/problem/1005문제 설명N개의 건물을 짓는 데 각각 건설 시간이 주어진다. 일부 건물은 선행 건물이 모두 완성되어야만 지을 수 있다. 특정 건물 W를 완성하는 데 걸리는 최소 시간을 구하는 문제이다.핵심 개념 - 위상정렬 (Topological Sort)위상정렬이란?방향 그래프에서 선행 관계를 위반하지 않고 노드를 순서대로 처리하는 알고리즘이다.예를 들어 "A를 한 뒤에 B를 할 수 있다"는 관계가 있을 때, 반드시 A → B 순서로 처리한다.동작 원리위상정렬은 진입 차수(inDegree) 를 이용한다.진입 차수 = 해당 노드를 가리키는 간선의 수 = 선행 건물의 수1. 진입 차수가 0인 노드(선행 건물 없음)를 큐에 넣기2. 큐에서 노드를..

문제 설명N명의 학생이 각자 프로젝트를 함께하고 싶은 학생을 단 한 명만 선택한다. 학생들이 팀을 이루려면 반드시 사이클을 형성해야 한다.팀이 될 수 있는 조건은 다음 두 가지이다.자기 자신을 선택한 경우 (1인 팀)s1→s2→s3→...→sr→s1 처럼 서로가 서로를 선택해 사이클을 이루는 경우어느 팀에도 속하지 못하는 학생의 수를 구하는 것이 목표이다.사이클 탐지각 학생에서 나가는 간선이 정확히 1개이므로, 그래프를 따라가다 보면 사이클이 존재한다.따라서 사이클에 속한 학생들을 찾아 팀원으로 등록하고, 나머지를 세면 된다. 1차 구현 - 재귀 DFS구현using System;using System.Collections.Generic;public class Program{ static int[] ..

https://www.acmicpc.net/problem/22857문제 설명길이가 N인 수열 S에서 원하는 위치의 원소를 최대 K번 삭제할 수 있다. 삭제 후 수열에서 짝수로만 이루어진 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.예를 들어 수열이 1 2 4 3 6 8 5 2이고 K=1이라면, 홀수 3을 삭제하면 2 4 6 8이 연속하게 되어 답은 4가 된다.핵심 아이디어 - 슬라이딩 윈도우문제 변환"짝수 연속 부분 수열을 최대한 길게 만들기 위해 홀수를 K개 삭제한다"는 것은 곧 다음과 같이 바꿔 생각할 수 있다.홀수가 K개 이하인 윈도우 중 짝수의 개수가 가장 많은 것을 찾아라.이 발상이 핵심이다. 삭제 대상은 항상 홀수이므로, 윈도우 안에 홀수가 K개를 초과하지 않는 범위에서 최대한 넓은 ..

문제 설명본 문제는 열쇠와 문이 존재하는 미로에서 시작점(0)부터 출구(1)까지의 최단 이동 횟수를 구하는 문제이다.미로의 구성 요소는 다음과 같다..빈 칸 (이동 가능)#벽 (이동 불가)a~f열쇠 (이동 가능, 처음 방문 시 획득)A~F문 (대응하는 열쇠 보유 시에만 이동 가능)0시작 위치1출구단순한 BFS 문제처럼 보이지만, 열쇠의 보유 여부에 따라 이동 가능 여부가 달라지기 때문에 일반적인 BFS로는 풀 수 없다. 경로마다 획득한 열쇠가 다를 수 있으므로, 열쇠 상태를 BFS 상태에 포함시켜야 한다.핵심 아이디어 - 비트마스크 BFS왜 비트마스크인가?열쇠의 종류는 a~f 최대 6가지이다. 각 열쇠의 보유 여부를 1개의 정수(비트마스크) 로 표현할 수 있다.비트 위치: 5 4 3 2 1 0..

문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🌳 최소 스패닝 트리(MST)란?그래프의 모든 정점을 연결사이클 없음간선 가중치의 합이 최소가 되도록 만든 트리 ❌ 다익스트라와 MST 비교 다익스트라 MST 한 정점에서 다른 정점까지 최단 거리모든 정점을 최소 비용으로 연결누적 거리 기준간선 비용 기준경로 문제구조 문제👉 이 문제는 경로가 아니라 연결 구조를 묻는 문제이므로다익스트라가 아닌 Prim / Kruskal을 사용해야 한다. +다익스트라는 시작점에 따라 결과가 다르지만,프림 ..

빌드하는 과정에서 많은 버그가 발생했다... 1. GPGS와 애드몹 플러그인 충돌 문제✔해결 방법: 애드몹 패키지를 삭제하고 다시 Import할 때ExternalDependencyManager폴더를 체크 해제함 2. 키스토어 관련KeytoolException: Failed to read key **** from store "C:\UnityKeyStore\user.keystore"Get Key failed: Given final block not properly padded✔ 해결 방법: 빌드할 때 keystore을 설정하고 비밀번호를 정확하게 입력 3. 타겟 버전 관련WARNING: minSdkVersion (23) is greater than targetSdkVersion (16) for varian..

문제 풀이법DFS와 DP로 풀 수 있다.DFS는 길을 따라 내려가면서 탐색을 하고, DP로는 중복 계산을 방지하며 이미 구한 경로의 수를 저장한다. dp[x][y] = (x,y)에서 (N-1, M-1)까지 도달할 수 있는 경로의 개수탐색을 하다가 이미 방문했던 좌표에 다시 간다면,dp[x][y]를 반환해서 경로의 개수를 알아낸다. 1. (x, y)가 도착점 (N-1, M-1)이면 경로 1개를 찾은 것이므로 1을 반환한다.2. dp[x][y]가 이미 계산된 적 있다면((x,y)에 방문한 적이 있음)→ 이 칸에서 출발하는 경로 수는 이미 구해진 상태이므로 dp[x][y]를 그대로 반환3. dp[x][y]가 -1이면 dp[x][y] = 0으로 초기화4. 상하좌우 3방향을 돌면서 내리막길이 가능하면 → d..