알고리즘 문제 해결

백준 15591번 - MooTubeMooTube는 N개의 영상이 서로 연결된 그래프(트리 구조)에서, USADO(연결 강도)라는 가중치를 가지고 있다.사용자가 특정 영상에서 시작하여 USADO가 k 이상인 영상의 개수를 찾는 문제.Q개의 질의가 주어지며, 각 질의는 (

백준 18428번 - 감시 피하기N x N 크기의 복도에서 T(선생님), S(학생), X(빈칸)이 배치되어 있다.선생님은 상, 하, 좌, 우 방향으로 감시를 할 수 있으며, 장애물 O가 있으면 감시를 막을 수 있다.장애물 3개를 설치하여 학생이 감시를 피할 수 있는 경

백준 18427번 - 함께 블록 쌓기N명의 학생이 있으며, 각 학생은 M개 이하의 블록을 가지고 있음.블록의 높이는 다양하며, 각 학생이 가진 블록 리스트가 주어짐.학생마다 최대 한 개의 블록만 선택 가능하며, 학생 순서대로 쌓아야 함.목표: 블록을 쌓아 높이 H를 만

백준 10021번 - Watering the FieldsN개의 농장이 2차원 좌표로 주어지고, 각 농장을 연결하는 비용이 유클리드 거리의 제곱((x1 - x2)^2 + (y1 - y2)^2)으로 결정됨.특정 비용 C보다 작은 간선은 선택할 수 없음.최소 비용으로 모든

백준 17025번 - 얼음 깨기 대회N x N 크기의 격자에서 - 여러 개의 얼음 덩어리가 존재할 수 있으며, 각 덩어리는 4방향(상하좌우)으로 연결된 - 목표: 가장 큰 얼음 덩어리의 크기(answer1)와 그 덩어리의 둘레 길이(answer2)를 구하는 문제.만약

📌 백준 5558번 - チーズ (Cheese)🐭 N마리의 생쥐가 치즈를 1부터 N까지 순서대로 먹어야 하는 문제🐭 생쥐는 상하좌우로 이동 가능하며, 장애물(X)이 존재🐭 목표: 생쥐가 S에서 출발하여 치즈 1~N을 먹고 최종 도달하는 최소 시간 구하기✅ 입력

🔗 문제 링크: 백준 11964번 - Hot Dogs?목표 점수 T 가 주어지고, 두 가지 점수 획득 방법 A, B가 주어진다.한 번에 A점 또는 B점을 얻을 수 있음.추가적으로 /2 연산을 한 번만 수행 가능 (현재 점수를 절반으로 줄이는 것).T 이하에서 최대 점

🔗 문제 링크: 백준 18430번 - 무기 공학N × M 크기의 격자에서 부메랑 모양의 무기를 배치하여 최대한 강한 무기를 제작하는 문제.부메랑은 네 가지 형태로 배치 가능하며, 2 × 중심값 + 나머지 두 값으로 점수를 계산.서로 겹치지 않게 배치해야 하며, 최대

백준 1043번 - 거짓말N명의 사람이 있고, M개의 파티가 열린다.어떤 사람이 진실을 알고 있다면, 그 사람이 참석한 모든 파티에서는 거짓말을 할 수 없다.각각의 파티에는 여러 사람이 참여할 수 있으며, 서로 연결될 수 있다.최대한 많은 파티에서 거짓말을 할 수 있는

백준 10159번 - 저울N개의 물건이 있고, M개의 비교 결과가 주어진다.각 비교 결과는 "A가 B보다 무겁다"는 형태.모든 비교 결과를 바탕으로, 각 물건이 무게 비교를 할 수 없는 개수를 출력하는 문제.connInfo\[i] 리스트를 사용하여 i번 물건보다 무거운

🔗 문제 링크N개의 방이 있으며, 각 방에는 특정한 규칙이 존재한다.1번 방에서 시작하여 N번 방에 도착하는 것이 목표.방의 종류는 다음과 같다:L (Leprechaun, 요정): 최소 X 골드가 필요하며, 만약 부족하면 X 골드로 채워줌.T (Troll, 트롤):

🔗 문제 링크 N x N 크기의 농장이 주어지고, 길(R)과 소(K)의 위치가 주어진다. 각 칸은 (x, y) 좌표로 표현되며, 길이 없는 곳은 자유롭게 이동 가능하다. 길이 존재하는 경우, 해당 방향으로 이동할 수 없다. 서로 만날 수 없는 소들의 쌍의 개수

Iks라는 소셜 네트워크 회사에서는 비표준 관리 시스템을 사용하고 있으며, 특정 직원이 다른 직원들을 직접 또는 간접적으로 관리하는 체계를 갖추고 있다. 두 가지 유형의 명령어를 처리해야 한다.1\. T A B: 직원 A와 B의 위치를 교환한다.2\. P E: 직원 E

🔗 문제 링크외판원 순회 문제는 모든 도시를 한 번씩 방문하고 시작 도시로 돌아오는 최소 비용 경로를 찾는 문제임.이 문제는 NP-Hard 문제에 속하며, 비트마스킹과 동적 계획법(DP)를 이용한 기법이 주로 사용됨.접근법:DFS를 사용하여 모든 경로를 탐색하고, 방

🔗 문제 링크두 문자열 A와 B가 주어졌을 때,두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS) 을 구하는 문제임.예를 들어, A = "ACAYKP", B = "CAPCAK"인 경우 LCS는 "ACAK"임.방법:LCS의 길이

🔗 문제 링크이 문제는 R×C 크기의 격자 위에서 진행됩니다.격자에는 나의 로봇("I")과 상대 로봇들("R")이 배치되어 있으며,주어진 이동 명령에 따라 나의 로봇이 이동할 때마다 상대 로봇들은나의 로봇을 향해 그리디하게 한 칸씩 이동합니다. 🤖➡️특히, 상대 로

첫번쨰 시도\-하나의 dfs에서 3가지의 정답을 모두 도출할 수 있게따로 나눠서 해결하는 것은 중복이라고 생각해서 한번에 처리하려함결과 : 시간초과예를 들어서, A구역과 B구역이 서로 벽으로 붙어있는 상황이라면 A구역에서 벽을 허물면서 탐색을 진행하고, 또 B의 구역에

전력난 (6497)전력난 문제는 여러 도시와 이들을 연결하는 도로들이 주어졌을 때,모든 도시가 연결된 상태를 유지하면서 불필요한 도로의 전력 소비를 줄여절약할 수 있는 전력의 총합을 구하는 문제입니다.입력: 각 테스트 케이스마다 도시의 개수(N)와 도로의 개수(M)가

퍼즐 문제는 3×3 보드에 배치된 숫자와 빈칸(0)을 이동시켜, 목표 상태인 123456780을 만드는 최소 이동 횟수를 구하는 문제입니다.문제 링크: 1525 퍼즐입력:3×3 보드에 각 칸마다 0(빈칸)과 1~8의 숫자가 주어집니다.목표:빈칸을 인접한 숫자와 교환하여

🔗 문제 링크문제에서는 회전이 불가능한 직육면체 벽돌들을 이용하여 탑을 쌓는 상황을 다룹니다.각 벽돌은 밑면 넓이, 높이, 무게 정보를 가지며,탑을 쌓을 때 아래 조건을 만족해야 합니다:밑면 조건: 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.무게 조건:

이번 포스팅에서는 백준 13398번: 연속합 2 문제를 해결하면서 겪었던 시행착오와 개선 과정을 공유하고자 함. ✨문제에서는 n개의 정수로 이루어진 수열이 주어짐.연속된 구간의 합 중 최대값을 구해야 하는데, 단 한 개의 원소를 제거할 수 있는 조건이 추가됨. 😲(단

문제에서는 격자판에 있는 두 개의 레이저 통신 지점(문자 C)을 연결하는 경로를 찾되,경로 상에서 꺾이는 횟수(즉, 거울 사용 횟수)를 최소화하는 것이 목표입니다.격자에는 벽(\*)이 존재하여 이동이 제한되고, 레이저 빔은 한 방향으로 쭉 진행하다가거울을 사용해 방향을

이 문제에서는 N x M 크기의 0과 1로 이루어진 맵에서, 1로만 이루어진 가장 큰 정사각형을 찾는 문제였음.주어진 맵에서 가장 큰 정사각형의 넓이를 구해야 했음.처음에는 동적 계획법(DP)을 사용해 문제를 풀기로 했음.각각의 칸에서, 그 칸을 우측 하단으로 하는 가

이번 포스팅에서는 백준 3190번 "뱀" 문제를 DFS를 이용하여 해결했던 과정을 공유함.뱀이 이동하면서 사과를 먹으면 몸이 늘어나고, 자신의 몸이나 벽에 부딪히면 게임이 종료되는 문제였음.특정 초마다 주어지는 방향 전환 명령에 따라 뱀의 이동을 시뮬레이션하여 최대 이

📌 문제 링크아이템 줍기 - 프로그래머스 2D 좌표 평면에서 사각형의 경로를 따라 이동하며 최단 거리로 아이템을 획득해야 함.이동은 테두리(경계선)에서만 가능하며, 사각형 내부로는 진입할 수 없음.최단 거리 경로를 찾아야 하므로 BFS(너비 우선 탐색)이 적절하지만

첫번째 접근 방법은 dist라는 친구들의 이동거리가 담긴배열에서 모든 weak 정점에서 출발했을때에 나올 수 있는 모든 경우를 저장즉 1이라는 지점에서 1,2,3,4 라는 dist친구들이 출발했을때에 어디까지 취약점을 발견할 수 있는지를 저장하는 것이다.1에서 출발했고

주어진 문제의 조건을 보고 브루트포스 알고리즘을 사용해서 일일이 조건에 대해서 확인하면 시간초과가 발생한다.문제에 효율성을 체크한다는 말도 있었기때문에 브루트포스는 생각하지않고 어떻게하면 효율적으로 해결할 수 있을까 생각주어진 속성은 언어, 분야, 숙련도, 음식, 점수

문제를 읽고 바로 생각한것은 시작지점에서 BFS 알고리즘을 사용해서 k번 안에 탈출 지점에 도달할 수 있는 모든 경우의 수를 확인한다.입니다.시간 초과 발생k의수가 <2500 으로 시간초과가 발생하는 듯합니다!다른 방법을 생각한것은 탈출한 경로를 문자열로 나타내었

스타 수열이 되기위함의 가장 중요한 조건은 어떠한 부분 수열을 앞에서 부터 2개씩 묶었을때에 교집합 원소가 한개이상있어야하고 첫번쨰와 두번째 원소는 달라야 한다는 점이다.처음으로 생각한 방법은 500000크기의 배열을 만들어주고 0~500000미만의 원소들이 공통으로

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요. 라고 주어졌기때문에 바로 BFS를 떠올렸다. 중요하게 생각해야될것들 이동하는것과 회전하는데에

📌 문제 링크:퍼즐 조각 채우기 - 프로그래머스 빈칸(0)으로 이루어진 game_board가 주어지고, 퍼즐 조각(1)으로 이루어진 table이 주어진다. table에 있는 퍼즐 조각을 회전하여 game_board의 빈칸을 채울 수 있다. 최대한 많은 빈칸을 채

입국심사 - 프로그래머스각 심사관이 한 명을 심사하는 데 걸리는 시간이 다를 때, 주어진 n명의 사람이 심사를 받는 최소 시간을 구하는 문제입니다.일반적으로 이분 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용합니다.하지만 이 문제에서는 답이 될 수 있는 값(resul

가장 먼 노드 - 프로그래머스n개의 노드로 이루어진 양방향 그래프가 주어진다.1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제.이 문제는 그래프에서 1번 노드로부터 가장 먼 거리의 노드 개수를 구하는 문제이므로BFS(너비 우선 탐색)를 사용하여 최단 거리를 구

순위 - 프로그래머스n명의 선수가 1대1 경기 결과를 기반으로 순위를 결정할 수 있는 선수 수를 구하는 문제입니다.A 선수가 B 선수를 이겼다면, A는 B보다 순위가 높다.하지만 경기 결과만 주어졌을 때, 순위를 확실하게 알 수 있는 선수만 카운트해야 함.✔ 모든 선수

// 첫번째는 모든 경우의 수를 확인하기 위해서 dfs를 사용// 트리플로 얻을 수 있는 최고 점수 60점과 불을 맞춰서 얻는 50점, 그리고 20에서 60사이 의 트리플 경우, 20에서 40 사이 더블 경우, 20 이하의 싱글 경우를 나눠서 모든 경우로 진행// 하지

1부터 N까지의 숫자 중에서 5개의 숫자를 뽑아 암호를 만든다.주어진 질문(q)은 각각 5개의 숫자로 이루어진 배열이다.각 질문에 대해 정답 배열(ans)의 값은 해당 질문과 암호의 교집합 요소 개수이다.이 조건에 맞는 암호의 개수를 반환하는 문제이다.문제 링크 🔗완

2차원 문자열 배열인 storage와 문자열 배열 requests가 주어진다.각 requests의 첫 글자는 제거해야 할 알파벳이며, 해당 알파벳이:단일 문자이면 외부와 연결된 해당 알파벳만 제거한다.문자열이면 해당 알파벳 전체를 제거한다.외부와 연결되었다는 것은 해당

트리가 주어지고 각 노드의 값은 정수로 이루어져 있다.트리는 두 가지 조건에 따라 홀짝 트리로 구분된다:홀짝 트리: 루트 노드를 기준으로 각 노드의 값과 자식 노드의 개수가 같은 홀짝성이어야 한다.(예: 루트가 짝수이면 자식 개수도 짝수, 루트가 홀수이면 자식 개수도

🔗 문제 링크A도둑과 B도둑이 팀을 이루어 모든 물건을 훔치려고 합니다. 하지만 두 도둑 중 누구도 경찰에 붙잡히지 않도록 흔적을 최소화해야 합니다.물건을 훔칠 때:A도둑이 훔치면 info\[i]\[0]개의 A의 흔적이 남습니다.B도둑이 훔치면 info\[i]\[1]

🔗 문제 링크전기줄 문제는 두 개의 전봇대에 서로 연결된 전기줄들이 주어질 때,전기줄들이 서로 교차하지 않도록 하기 위해 최소 몇 개의 전기줄을 제거해야 하는지를 구하는 문제임.문제를 해결하는 핵심은 교차하지 않는 전기줄들의 최대 개수(즉, 최대 부분 수열)를 찾고,

🔗 문제 링크내려가기 문제는 세 개의 숫자가 있는 N개의 줄이 주어질 때,위에서 아래로 내려오면서 인접한(혹은 바로 옆) 숫자들 중 하나를 선택해최대 합과 최소 합을 구하는 문제임.즉, 한 줄에서 선택한 숫자의 인접한 번호(같은 열 또는 바로 옆 열)로만 이동할 수

🔗 문제 링크이 문제는 고대의 주문서에 기록된 모든 주문(알파벳 소문자 11글자 이하로 구성된 모든 문자열)이다음 규칙에 따라 정렬되어 있다고 가정합니다.길이가 짧은 주문부터 기록됨.길이가 같으면 사전 순으로 기록됨.예를 들어, 주문서의 시작 부분은"a" → "b"

이번 포스팅에서는 프로그래머스 도넛과 막대 그래프 문제를 해결했던 과정을 공유함.문제의 핵심은 그래프의 연결 관계를 분석하여, 새로 생성된 노드: 들어오는 연결(comeInCnt)이 0이고 나가는 연결이 2개 이상인 노드 막대 그래프 (Pole): 자신으로 되돌아오

문제에서는 주어진 도시와 도시들을 잇는 도로(간선) 정보를 바탕으로 모든 도시를 연결하면서, 두 개의 분리된 마을로 분할하는 최소 비용 계획을 수립해야 합니다.즉, 최소 신장 트리(MST)를 구성한 뒤, MST에서 가장 비용이 큰 간선을 제거하여 두 개의 분리된 마을로

최단거리 구하기 + 음수 사이클 판별 문제https://www.acmicpc.net/problem/11657N개의 도시와 M개의 버스(간선)가 주어짐1번 도시에서 출발해 나머지 모든 도시까지 최단거리 구하기조건음수 사이클 존재 시 -1 출력도달 불가능한 도시는

모든 리프노드를 찾아서 리프에서 다른 리프노드까지의 모든 가능한 길이를 탐색=> 메모리초과최악의 경우 리프노드 10000-1 개 즉, 10000^3 이 가능 -> 맞지 않음트리의 지름을 이루는 노드 u,v가 존재한다면임의의 점 r에서 가장 먼 노드를 찾는다면 그중 하나

문제 요약🏙️ N개의 높이가 서로 다른 타워가 왼쪽→오른쪽 순서로 일직선 위에 서 있고,🔫 각 타워에서 왼쪽 방향으로 레이저 신호를 발사한다.🎯 이 신호는 가장 먼저 만나는 왼쪽 방향의 타워 하나만 수신 가능.출력: 각 타워가 발사한 신호를 수신하는 타워 번호(없

스마트폰에서는 백그라운드에 활성화된 앱들이 메모리에 남아 있어,앱을 재실행할 때 빠르게 복원할 수 있지만 메모리가 한정적입니다.새 앱을 실행하려면 추가로 필요한 메모리를 확보하기 위해 일부 앱을 비활성화해야 합니다.활성화된 앱 개수 N (최대 100) 확보해야 할 메

네 개의 정수 배열 A, B, C, D가 있을 때A\[a] + B\[b] + C\[c] + D\[d] == 0 을 만족하는 (a, b, c, d) 쌍의 개수를 구하는 문제배열 길이 N ≤ 4000각 배열의 값은 정수 (절댓값 ≤ 2²⁸)A + B의 합을 모두 해시맵에

문제 링크과외맨이 고대 마야 사원에 있는 과외 노트를 찾기 위해 도미노 타일로 만들어진 다리를 건넌다.타일은 (왼쪽 숫자, 오른쪽 숫자)로 구성된 도미노 조각.인접한 타일로 이동하려면 공유하는 면의 숫자가 같아야 하며, 이동은 상하좌우로만 가능.목표는 첫 번째 타일에서