BOJ 문제풀이

✅ B → BA 이므로 이전 B의 개수 = 이후 A, B의 개수✅ A -> B 이므로 이전 A의 개수 = 이후 B의 개수B는 이전 A의 개수 + B의 개수이고,A는 이전 B의 개수

✔️ 각각의 가로, 세로 길이를 구해서 누적해가며 구했다✔️ 이전의 두 개 타일 둘레 길이를 더하면 다음 타일의 둘레 길이

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를

n이 1 or 2면 k의 값에 상관없이 답은 1이 된다그 외에는 양쪽에 1을 붙이고 dp로 이전의 값들을 더해나가면서 구하면 된다

BFS를 사용해서 탐색했다. 가능한 모든 방의 불을 다 킬 수 있어야 하기 때문. 탐색을 하면서 큐에 담아야 하는 값들은 다음과 같다방에 불은 켜졌지만 ⭕️ 아직 방문은 하지 않은 곳 ❌방에 불은 켜지지 않았지만 ❌ 방문은 한 곳 ⭕️여기서 불이 켜졌다는 이 방의 불을

✅ 격자의 가운데 칸부터 토네이도의 이동이 시작✅ 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다✅ 모래가 격자의 밖으로 이동할 수도 있다. ✅ 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양가운데부터 회오리치듯 돌아서 (1,1)까지 나오게 된

뭐 이런 문제가 다 있냐...✔️ 타자의 순서를 정해서✔️ 정해진 규칙을 지켜서 N번의 이닝까지 경기 진행해서✔️ 얻을 수 있는 최대 점수를 구하면 된다4번째 타자는 무조건 1번 선수여야 한다사실 9명 타자의 순서를 다 정하면 대략 36만정도인데 1명은 이미 정해져있기

돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하

대놓고 큐를 사용하라고 알려주는 구현 문제먼저 올라온 트럭이 먼저 내려가야 하기 때문에 FIFO의 방식을 구현할 수 있는 자료구조 큐를 사용트럭이 다리에 올라오면 다리 위의 트럭 무게 변수값 sumW 에 더해주고, 트럭이 다리에서 내려가면 빼주게 된다. 이 과정은 파이

> 스택 자료구조를 이용한 풀이 - 괄호 열린 괄호(`(`, `[`) 라면 무조건 스택에 넣고, 닫힌 괄호(`)`, `]`)라면 스택에 짝이 맞는 열린 괄호가 있는지 확인하는 방식 - 숫자 모든 괄호들의 짝이 맞다고 가정 - 열린 괄호 + 닫힌 괄호 : 바로 숫자

최단거리 구하기 = bfs 풀이무식하게 모든 이동 루트들을 큐에 같이 저장했다. 메모리가 터지든 저장하다 시간이 터지든 둘 중 하나일거라고 생각했는데 시간이 터졌다근데 애초에 시간이 안 터져도 위의 풀이는 틀릴 수 밖에 없었다.이 블로그를 참조해서 풀어도 계속 시간초과

섬을 구분하기 위해 각각의 섬을 찾아서 번호를 붙인다각 섬에서 bfs로 탐색하여 다른 섬을 찾으면 그 거리가 최단거리배열의 처음부터 끝까지 돌면서 섬을 발견하면 bfs로 탐색해서 연결된 모든 섬을 찾아 같은 번호를 붙여준다. 1번 섬을 찾고 나면 2번 섬을 찾는 방식.

반드시 현재 출발하는 숫자로부터 사이클이 완벽하게 완성되는 경우에만 탐색을 인정하는 방식이전에 다른 숫자를 통해 사이클이 발견됐어도 그냥 넘어가기 때문에 중복으로 탐색하게 된다말하자면 1 -> 3 <-> 3 으로 1에서 시작해도 3이라는 사이클을 발견할 수 있는데

모든 행과 열에 대해 탐색이 진행된다높이가 2이상으로 변화하게 되면 탐색을 중단한다경사로는 낮은 칸에 놓아야 하므로 탐색을 진행하다 1칸 높은 칸을 만나게 되면 뒤로 후진해서 경사로를 놓을 수 있는지 확인(back 함수), 1칸 낮은 칸을 만나게 되면 앞으로 나아가면서

첨엔 단순히 알파벳 순서가 빠른거부터 차례대로 출력하면 되는 거라고 생각했는데 문자열이 사전 순으로 앞에 오도록 출력해야 되는 거였다.앞에서부터 순서가 가장 빠른 알파벳을 찾는다알파벳을 찾았으면 출력하고, 그 알파벳 다음 순서에 있는 단어들 중에서 가장 빠른 알파벳을

오랜만에 풀어본 BFS 문제였는데 이 문제는 진짜 실수를 겁나 많이 했다...우선 로직 자체는, 불이 먼저 확산한다지훈이가 이동한다지훈이가 이동할 수 있는 칸에 범위를 벗어나는 칸이 있다면 시간 출력 후 종료지훈이가 더 이상 이동할 수 있는 칸이 없다면 탈출 불가 IM

정렬되어 있는 리스트에서 찾고자 하는 값을 탐색할 때 범위를 절반씩 좁혀가며 찾는 방식일반 탐색(Brute-Force)은 O(N)인 반면에 이분 탐색은 O(logN) (단, 리스트의 길이가 짧은 경우는 일반 탐색이 더 빠를 수 있음)start, end 의 값을 정해놓고

백준의 기타 레슨과 유사바킹독 님 블로그를 참고하면 이 문제는 파라메트릭 서치 = 매개 변수 탐색 문제로, 조건을 만족하는 최소/최대를 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법을 통해 풀 수 있다최대/최소를 구하는 방식을 이분탐색을 통해

문제 풀이 잘못된 풀이 (0, 1) 부터 시작해서 (N-2, N-1)의 칸 까지 d1, d2를 각각 뻗어나갈 수 있게 하는 재귀 방식으로 짜려고 했지만 이렇게 하는 경우 이미 방문했던 칸에서 이미 계산했던 구역을 여러번 또 계산하게 되는 불필요한 중복 계산이 계속

같은 깊이의 큐에 있는 경우는 방문했던 곳을 한 번 더 재방문할 수 있게 해준다.visitx은 여기까지 오는 경로가 몇 가지였느냐(경우의 수)를 나타내며 최종적으로 여기에 방문하는 모든 경우의 수를 다 더한 값을 나타내야 하므로(총합) 추가적으로 계속 더해줘야 한다.

이동 방식에 따라 가중치가 다르기 때문에 다익스트라 최단경로 알고리즘을 통해 풀이했다. 우선순위 큐(힙 자료구조 사용)를 사용했기 때문에 가장 짧게 걸리는 시간을 먼저 꺼내서 탐색을 진행하게 된다. 방문처리는 현재 탐색을 진행하려는 위치(x)까지의 시간(visited\

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드

원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.문제는 어렵지 않았는데 출력 조건을 제대로 안 봐서 세 번 틀렸다원래 갈 수 있는 부분에서 도달할 수 없는 위치는 -1도달할 수 없는 위치는 탐색

N번 마을 → X번 마을 → N번 마을 로 올 수 있는 최단 경로를 찾으면 된다. M개의 경로를 통해 각 마을에서 다른 마을들로 갈 수 있는 최단 경로를 모두 구한 다음에 (1) N → X (2) X → N 이 두 가지 경로를 더한 값의 최대값을 구하면 된다. 범위가

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으

진짜 이 문제 뭘까어제부터 날 고생시키는 불...이야...솔직히 문제 자체는 별로 어렵지 않았다불! 이랑 똑같다그래서 코드를 똑같이 냇다따란!불!이랑 전혀 다른 게 없는데 자꾸 12%에서 터졌다질문 게시판을 다 뒤져봐도 내가 놓친 조건이나 고려사항이 전혀 없는데다가 심

테케 다 맞았는데 0%에서 틀렸습니다!가 나오는 문제2차원 배열로 쌈싸먹는 완벽한 구현문제다배열 돌려 배열 내려놔 배열 다시 돌려....블록 그룹 찾기일반 블록 최소 1개검은 블록 포함 x무지개 블록의 개수는 상관 x블록의 조건최소 2개 이상일반 블록의 색은 모두 동일

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.중간에 합을 구하다가 M을 넘은 것 같으면 어차피 더 계산해볼 필요가 없기 때문에 break 해줘야 하는데 무조건적으로 다 더해서 시간초과합이 M을

문제 조건 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다.

단순하게 모든 칸들에 대해서 사다리를 놓아보는 완전탐색 방식으로 생각했는데 예상치 못한 중복 탐색이 발생해서 시간초과가 터졌다시간 줄여보겠다고 원래 사다리가 놓여있는 곳과 원래 놓여있지 않은 곳 두 가지에 대해서 따로 분기 처리를 해줬는데 이것 때문에 오히려 중복 탐색

딱 봐도 뭔가 반복되는 느낌이다그렇게 안 보이지만 그림의 사각형은 전부다 정사각형이다. 한 변의 길이와 시작되는 위치만 안다면 재귀든 반복문이든 사용해서 찍어주기만 하면 될 것 같다문제는 안에서부터 밖으로 나가느냐, 밖에서부터 안으로 들어오느냐인데. 입력되는 숫자에 따

너무 뻔한 구현문제라 어렵지 않았다. 문제가 제시하는 순서대로만 풀면 마법처럼 풀림\~\~~다만 파이어볼이 2개 이상인 경우 라는 조건은 쉽게 낚일 수 있는 듯

DP로 푸는 방법도 있지만 그 경우는 리스트 전체를 훑는 반복문을 두 번 돌리는 O(N^2)의 복잡도를 가지기 때문에 이 문제의 조건에서 주어진 백만개의 리스트같은 경우는 시간복잡도가 터진다원래 이 문제는 1.DP 2.이분탐색 두 가지 방법이 있는데, 여기서는 이분탐색

프로그래머스의 퍼즐 조각 채우기같은 문젠 줄 알았는데 그것보다는 쉬운 것 같았다. 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있

참고 블로그

각 cctv의 방향에 따라 감시 지역을 설정하고, 감시 되지 않는 사각지대의 최소값을 구하는 문제백준 연구소 시리즈랑 좀 비슷하다고 느꼈다. cctv의 번호와 위치를 구한다각 cctv를 돌면서 하나씩 방향에 따라 감시지역을 설정한다. 처음엔 북쪽 방향, 그 다음엔 남쪽

신장 트리란 (1) 모든 정점을 연결하는 (2)사이클을 이루지 않는 트리이다. 하나의 연결된 그래프에 신장 트리는 반드시 한 개 이상 존재할 수 있다. 가중치를 가지는 무방향 간선(edge)그래프가 존재할 때 최소의 간선 비용을 가지는 신장 트리를 말한다. 구현할 때

친구 관계는 대표적인 그래프 탐색 문제 중 하나다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이라는 아주 유명한 알고리즘 기법들이 있다. 어떤 문제들은 두 가지 중 어떤 방식을 택해도 풀리겠지만 어떤 문제는 둘 중 하나의 방법을 택하는 것이 훨씬 효율적일 때가

이 문제에서 가중치는 거리이며, 특정 위치에서 다른 모든 위치로 이동할 수 있는 거리를 모두 구하는대신 m을 넘어가면 더 이상 구하지 않는다. m이하에 있는 위치들의 아이템을 다 더해서 나오는 최대값을 구하는 문제. 다익스트라로 풀이했다.

일단 이진 트리 형태는 아니다. 차수가 3을 넘어갈 수 있다. 기본적으로 특정 루트 노드에서 자식 노드들로 dfs 탐색을 하게 되면 각 자식노드 ~ 리프노드까지의 지름의 길이를 구할 수 있다. 그렇게 구해진 여러 자식 노드들의 반환값들 중에 최대값 2개를 구해서 더하면

트리 형태의 그래프이며 특정 노드에서 다른 노드까지의 거리만 구하면 되므로 bfs를 사용해 풀었다.

문제 좀 까다로운 구현 문제였다. 처음엔 2차원 배열을 단순하게 90도로 회전하는 건줄 알고 zip을 사용하면 될 줄 알았는데 바깥에서부터 안쪽으로 각 단계별로 각각 따로 회전하는 문제였다 ㅠㅠ 어떻게 해야 될 지 감이 오긴 하는데 정말 그렇게 풀어도 되나를 모르겠어

항상 (0, 0)에서 시작해서 (M-1, N-1)로 이동하게 된다. 이동할 때 도중에 뛰어넘거나 할 수 없기 때문에 반드시 모든 길은 연결되어 있다. A에서 A와 인접한 곳으로 갈 수 있는 경우의 수는 일단 A까지 가는데 걸리는 경우의 수에 추가적으로 더해지는 것이다.

여우와 늑대가 각각의 그루터기에 최단 시간으로 도착하고 도착한 시간들 중에서 여우가 늑대보다 빨리 도착할 수 있는 그루터기의 개수를 구하는 문제이다. 그루터기를 하나의 정점으로 생각하고 여우와 늑대가 출발하는 지점이 1이라면 1에서부터 다른 정점까지의 최단거리를 구하는

도시를 둘로 분리하고 분리된 마을들끼리는 최소한의 경로로 연결되어 있어야 한다. 길의 유지비가 최소가 되도록 해야 한다고 한다. 그렇다면 둘로 나누기 전에 모든 마을을 최소한의 길로 연결하고 가장 큰 유지비를 가지는 길을 끊으면 되지 않을까? 그럼 둘로 나뉘면서 최소한

모든 칸은 넴모를 놓거나 놓지 않는 2가지 경우가 존재할 수 있다. 2x2 형태의 넴모가 이뤄지지 않도록 위쪽 왼쪽부터 오른쪽 아래쪽까지 차례대로 탐색한다. 도중에 2x2를 이루게 된다면 백트래킹으로 탐색을 중단한다.

틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.이게 왜 백트래킹 분류에...??? 아무튼 게임이 종료된 상태냐 진행중이냐를 묻는 것이다. 종료된 상태라고 하면 둘 중 하나가 이겼거나, 더 둘 곳이 없거나 둘 중 하나일것이다. X가 먼저 놓고 O가 다음에

배양액을 뿌릴 수 있는 곳에 모든 배양액을 뿌린다배양액은 각각 1칸씩 상하좌우로 퍼질 수 있다서로 다른 색의 배양액이 동시에 도착하는 같은 꽃이 핀다꽃이 핀 칸은 더 이상 퍼지지 않는다호수에는 배양액이 퍼질 수 없다배양액을 뿌릴 수 있는 칸 K(<=10)칸 중에서

1원으로 10원을 만드는 방법에 대해 생각해보자. 처음엔 1원이 있을 것이다. 1원으로 1원을 만드는 방법은 한 가지다. 그렇다면 1원으로 2원을 만드는 방법은? 1원에다가 1원을 더하는 방법 한 가지다. 그렇다면 1원으로 3원을 만드는 방법은 몇 가지일

로또 당첨 되고 싶다

1차원 배열이 2차원이 됐다가 다시 1차원이 되는 과정을 반복하며 배열을 돌리는 시뮬레이션 문제. 정답률이 높은 걸 보면 문제만 잘 읽으면 틀릴 일 없을 거 같았다. 물고기 수가 가장 적은 칸들에 1씩 추가한다불가능할 때까지 어항을 쌓는다물고기의 수를 조절한다한 줄로

S와 Y를 조합해야 하는 문제. 25개 중에서 7개를 골라야 하고 그 중 4개 이상은 반드시 S 여야 한다. S가 4, 5, 6, 7인 경우를 모두 비교해서 가능한 조합을 찾아낸 후 이 조합들이 서로 연결되어있는가를 확인하면 된다. 확인의 과정은 DFS로 탐색했다.

스도쿠의 규칙에 맞게 각 빈칸에 숫자가 들어가는지 들어갈 수 있는 모든 숫자 조합을 다 넣어본다. 도중에 하나라도 규칙에 맞지 않는다면 백트래킹으로 가지를 쳐낸다.

2n 개의 스티커에 대해 구할 수 있는 최대 점수를 구하는 방법을 찾아야 한다. 최대 길이가 10만이기 때문에 브루트포스나 완전 탐색은 어려울 것 같다. 만약 길이가 1인 경우라고 생각하면 계산할 것도 없이 값 2개 중 큰 값을 고르면 된다. 만약 길이가 2라면, 서로

고려해야 될 게 너무 많았다.무기/방어구는 수치에 상관없이 얻을 때마다 교체된다방어구는 4개 이상 착용할 수 없다.이미 동일한 방어구를 착용하고 있는 경우에도 착용할 수 없다.착용할 수 없는 경우에도 아이템 상자를 열었다면 무조건 빈 칸이 된다.주인공이 사망하지 않은

가장 왼쪽 계란부터 순차적으로 시작한다손에 들고 있는 계란으로 깨지지 않은 다른 계란 중 하나를 친다. 손에 들고 있는 계란이 깨졌거나 or 더 이상 깰 계란이 없으면 넘어간다.방금까지 손에 들고 있던 계란 바로 오른쪽에 있는 계란으로 과정을 반복한다.여기서 핵심은 깨

로그인에 시도된 비밀번호들로부터 최대한 안전거리가 먼 비밀번호를 찾는 문제다. 특정 위치에서 최대한 먼 거리를 찾는 것은 일종의 그래프 탐색이라 할 수 있다. 그래프 탐색에 비유하자면 특정 출발 위치에서 상하좌우로 한 칸씩 탐색 범위를 넓혀가면서 가장 멀

깊이가 10만까지 들어갈 수 있기 때문에 파이썬 최대 재귀 탐색 범위(999)를 넘는다. 최대 재귀 범위를 늘려줘야 한다. 스택 재귀로 오래걸리는 것 같아서 스택+반복문으로 바꿨는데 시간은 별 차이가 안 났다.

시뮬레이션 과정은 다음과 같다. 오른쪽으로 한 칸씩 이동한다.땅과 가장 가까운 상어를 잡는다.상어가 이동한다상어는 가야하는 방향으로 이동하다가 격자판에 부딪히게 되면 방향을 반대로 변경하게 된다. 상어의 속도는 1000까지 존재할 수 있는데 격자판 행, 열의 최대 크기

문제에서 알려준 2048 게임 룰은 아래와 같다.이동하는 방향으로 같은 숫자가 연속으로 2개 있다면 합쳐진다.(단, 빈칸은 고려햐지 않는다.)그림에선 왼쪽으로 이동한 방향으로 여러개가 있다면 이동하는 방향 쪽에 위치한 2개를 먼저 합친다.그림에선 위쪽으로 이동이미 한

풀이 가치의 합의 최대를 구하기 위해서 모든 조합을 다 구해보는 경우 무게가 최대 10만이라 시간초과가 날 가능성이 있다. 좀 더 효율적인 방식이 필요하다. 완전 탐색은 안 되지만 어쨌든 물건을 가방에 한 번씩 다 넣어보긴 해야 한다. 스택이나 큐 같은 곳에 저장하

봉우리의 조건은 다음과 같다.가로와 세로가 각각 1이하 거리에 있는 같은 높이의 값인접한 모든 값들이 다 현재 봉우리의 높이보다 낮은 높이인 경우그림에서 하늘색은 인접한 높이를 가진 인접한 격자들을 묶은 것이다. 위의 경우는 주변에 높이 3이 있기 때문에 봉우리가 될

일단 이동해야 하니까 그래프처럼 연결했다. 규칙성이 없어서 노가다로 연결해야 했다. 20번까지는 반복문 돌리고 나머진 진짜 다 씀. 0열에는 다음 이동해야 할 위치를, 1열에는 현재 칸에서 얻을 수 있는 점수를 기록함이제 예외사항 몇 가지를 정리했다. 위치는 위의 그래

플레이어들이 순서대로 s만큼 확장해나간다. 확장이기 때문에 너비 우선 탐색을 사용했다. 플레이어들이 탐색을 시작할 수 있는 위치를 저장해뒀다가 각 턴마다 그 위치들에서 너비 우선 탐색을 통해 확장해나갔다. s만큼 확장하고 마지막에 저장된 위치들은 다음 턴에 탐색할 수

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오. 최소 스패닝 트리 문제이다. 각 정점들 간의 거리는 min(|xA-xB|, |yA

자두나무가 2개 있을 때 최대 W까지 둘 사이를 오고가면서 얼마나 많은 자두를 얻을 수 있는지를 구해야 한다. 문제의 예제를 보고 직관적으로 구해보면 처음에는 1번 자두나무 위치에 그대로 서 있는다. 비록 2번 자두나무에서 떨어지긴 하지만 그 뒤의 2,3번 째 자두

준석이는 최소한의 비용으로 친구를 사귀고 싶어한다. 친구의 친구는 친구라는 것은 결국 1, 2가 친구고 1, 3이 친구라면 2, 3 역시 친구가 된다는 소리다. 결국 친구 관계를 하나의 집합으로 묶을 수 있다. 분리집합 개념을 사용할 수 있을 것 같다. 보통 분리집합에

1, 2, 3 세 가지 숫자를 사용해서 더할 수 있는 방법의 개수에 대해 구하는 문제이다. n의 최대 값은 백만으로 모든 경우의 수를 dfs로 구한다는 건 불가능했다. 이미 구해진 값으로부터 누적해서 구해나가는 다이나믹 프로그래밍 방법으로 접근했다. 우선 1을 구하는

모든 별들을 최소 연결해야 하는데 최소 비용이여야 함 -> 최소 스패닝 트리좌표들 간의 거리가 곧 비용이기 때문에 모든 좌표에 대해서 다른 좌표들과의 거리 값을 전부 구해서 거리에 대해 오름차순으로 정렬하고 크루스칼 알고리즘으로 풀이주어지는 좌표들의 개수는 최대 100

현재 탑의 위치보다 높은 위치의 탑 위치를 찾는 문제이다. 왼쪽에서 오른쪽으로 하나씩 확인해나가면 된다. 전체 탑의 개수가 50만이기 때문에 각 탑에 대해서 매번 왼쪽을 일일이 탐색하면 시간초과남.결국 현재 탑을 기준으로 왼쪽에 있는 탑들에 대한 정보를 어딘가에 저장해

상근이가 항상 먼저 시작하고, 상근이나 창영이는 어떤 패를 두든 자신이 이길 수 있는 패를 선택하게 된다. 우선 돌은 1,3,4개를 한 번에 가져갈 수 있으므로 주어지는 돌의 개수가 1,3,4 중 하나라면 무조건 먼저 시작하는 상근이가 이기게 된다. 하지만 돌의 개

유사 테트리스인데 이제 행과 열 둘 다로 움직인다. 그림에서와 같이 빨간칸에 블럭이 생기면 아래에 있는 초록칸과 오른쪽에 있는 파란칸으로 블럭이 이동하게 된다.

집에 있는 모든 온풍기에서 바람이 한 번 나옴온도가 조절됨온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소초콜릿을 하나 먹는다.조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.테스트

로프들을 사용해서 들어올릴 수 있는 최대 중량을 구하는 문제이다. 모든 로프를 사용하지 않아도 되고 로프를 사용해서 들어올릴 때는 각 로프에 중량(w)을 들어올리는 로프의 개수(k)로 나눈 만큼 무게가 가해지게 된다. 중량이 높아질수록 각 로프에 가해지는 무게도 높아지

1열에서 C열까지 이동해야 한다. 가장 이상적이면서 파이프라인을 최대한 많이 설치할 수 있는 경우는 위의 그림과 같이 같은 행에 위치한 C열로 이동하는 것일 것이다. 하지만 중간에 건물들이 위치해있기 때문에 그림처럼 이상적으로 일렬로 나열되는 것은 어렵다. 대신 최적의

예제에서 이동할 수 있는 최대 경로의 길이는 4이고 가능한 경로는 위의 3가지이다. 단순하게 모든 칸을 다 순회하면서 최대 경로를 찾는 방법도 가능하겠지만 최대 칸 수가 2만이 넘기 때문에 모든 칸에 대해 브루트포스로 찾는 것은 불가능하다.

그대로 출력해야 하기 때문에 n x n 크기의 배열을 먼저 생성한다. 해당 모양이 계속 반복되고 있다. 전체 배열을 그리고, n//3 사이즈로 줄여나가면서 해당 모양을 그려주면 된다. 이 모양도 사실 3x3 배열에서 한 단계 더 들어가서 1x1 사이즈일 때의 모양들이

`o` 에서 시작하여 가능한 모든 `*` 위치에 방문할 수 있는 전체 이동 거리의 최소 값을 찾는 문제이다. 만약 모든 `*` 에 도달할 수 없는 상황이라면 `-1` 을 반환한다.

백조는 자신이 위치한 공간을 포함해 서로 인접해 있는 물 위라면 어디든지 자유롭게 움직일 수 있다. 즉, 두 마리의 백조가 각자 속해 있는 두 개의 물 공간이 서로 만나게 될 때 두 마리의 백조도 만날 수 있다. 서로 인접한 물 공간을 하나의 집합으로 묶기두 마리의 백

외부 공기와 2면 이상 맞닿은 치즈들은 사라지게 된다. 모든 치즈가 사라지는데 얼마의 시간이 소요되는지 구하는 문제이다. 최소 시간을 구하며 그래프 탐색이기 때문에 너비 우선 탐색 알고리즘을 사용했다. 이때 외부 공기라는 개념이 뭔지 어떻게 구해야하는지 아이디어를 떠올

모든 부하들은 한 명의 직속 상사를 갖게 된다. 트리 형태로 나타낼 수 있다.2번이 2의 정도를 갖는 칭찬을 받게 되면 그 아래에 있는 3, 4, 5가 모두 칭찬의 수치에 +2를 하게 된다는 것이다. 매번 dfs를 돌려서 리프 노드까지 탐색해서 더해주면 되겠지만 트리의

배열의 최대 크기가 백만이기 때문에 모든 경우의 수를 dfs로 탐색할 수는 없다. 대신 특정 칸에 도달하는 경우의 수는 항상 변함이 없기 때문에 이 경우의 수들을 누적해서 최종 값을 구할 수 있다. 우선 1행 1열을 보면 1행 2열과 2행 1열에 갈 수 있다. 1행 1

1 ~ K 까지 차례대로 수행한다.이동할 때 위에 쌓여있는 블럭들은 함께 이동한다.빨간색일 때는 뒤집어야 한다. 이동할 수 없는 곳이거나 파란색 칸인 경우에는 방향을 바꿔서 다시 움직인다.어느 한 칸이라도 4개 이상의 블럭이 쌓이면 종료되어야 한다함께 이동하게 되는 모

투 포인터로 풀이했다. 2개의 포인터가 있다고 가정하고, p1 ~ p2까지의 값을 모두 합한 값을 sum 에 저장하게 되는데 p1과 p2를 적당히 조절해서 목표값을 맞출 수 있는 경우의 수가 몇개나 되는지 찾는 문제이다. 시작은 p1과 p2의 위치가 동일하다. 모든 수

🔗 서로 연결된 관계를 친구관계라고 정의한다. 친구 관계는 양방향이며 사이클이 되는 경우는 존재하지 않으므로 트리이다. 다만 양방향이기 때문에 아래와 같이 모든 노드가 루트로 선정될 수 있다. 모든 노드는 2가지 상태를 가질 수 있다. > 1. 자기 자신이 얼리

0을 포함하는 N보다 작은 모든 양의 정수를 두 번째 수로 설정하고 나올 수 있는 모든 배열을 구한 후 최대 길이를 갖는 값을 answer 로 출력한다.

중위 순회인데 이제 모든 노드를 탐색하면 도중에 중단해야 한다는 조건이 있다.이때 주의해야 할 점은 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서대로 방문처리를 해야 한다는 점이다. 부모 노드에 들어가자마자 방문 처리를 하게 되면 왼쪽 자식 노드를 방문한

최단거리를 구할 수 있으며 도중에 지름길이 존재한다. 항상 +1 칸을 할 수 있고, 지름길이 있으면 지름길로 이동한다. 각 위치에 대해 해당 위치에 도달할 수 있는 최대 거리는 해당 위치의 값이 된다. 만약 5km 위치에 있다면 지름길 없이 도달하는데는 5km 이상이

길이가 10만이기 때문에 투포인터로 풀이했다. i는 왼쪽 인덱스, j는 오른쪽 인덱스로 두고 값을 더할 때는 j에 있는 값을 더하고 j++를, 값을 뺄 때는 i에 있는 값을 빼고 i++를 하게 된다.우선 시작할 때는 구간 내의 합인 s 가 기준값 S 보다 작으면 j에

숫자 하나를 기준으로 삼고, 나머지 숫자들 가운데 기준으로 삼은 숫자와 더했을 때 가장 0에 가까울 수 있는 숫자가 무엇인지 찾는 방법을 생각했다. 주어지는 숫자는 10만개이고 오름차순 정렬로 주어진다. 10만개의 숫자에 대해 한번씩 기준 숫자

이 문제의 핵심은 결국 해당 빌딩의 위치보다 더 높은 높이를 가지는 빌딩이 오른쪽에서 몇번째 위치에 존재하느냐이다. 완전 탐색 방식으로 오른쪽에 있는 빌딩의 개수를 셀 수도 있겠지만 전체 빌딩의 개수가 8만개이기 때문에 시간 복잡도가 O(n^2) 면 계산이 불가능하다.

시뮬레이션 과정을 크게 3가지로 분류할 수 있다원판 회전 (rotate)원판에 남아 있는 수 2-1. 남아 있으면 : 서로 인접하면서 같은 수 모두 02-2. x : 평균 구하고 평균보다 큰 수 -1, 작은 수 +1원판을 회전 한 후, 원판에 남아 있는 수를 확인한다.

닫힌 구간들에 대해서는 건너뛰면서 A, B 만큼 이동했을 때 최소 이동 횟수인 값을 저장해나가는 dp로 풀이했다. 닫힌 구간들이 100개 정도 주어지고 해당할 수 있는 범위는 각 구간별로 최대 10만이므로 10만 x 100 을 일일이 표시하면 시간초과가 날 것 같았다.

수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새

플레이어의 수는 최대 10만이기 때문에 모든 플레이어와 매칭하게 되면 10만 x 10만으로 시간초과가 발생할 수 있다. 모든 플레이어에 대해 자신의 배수 점수를 가진 플레이어의 점수를 -1하고 본인의 점수는 +1하면 된다. 점수에 중복은 없으므로 10만개의 플레이어에

가능한 모든 숫자를 구하고, 영수가 질문한 숫자들과 비교해 N 개의 질문을 모두 통과하는 숫자만이 정답이 될 가능성이 있는 숫자들이다. 3자리의 숫자는 1~9의 숫자들로 이뤄져있으며 중복되는 숫자는 존재할 수 없으므로 987 = 504개이다. permutation 함

A B 가 주어지면 A가 B의 앞에 선다는 뜻이 된다. 어떤 순서로 줄을 서게 되는지 구하는 문제로 답은 여러 가지가 존재할 수 있다. 처음에는 dp나 누적합 정도로 풀 수 있겠다 생각하고 A 가 앞에 있으니 -1을 하고 B 가 뒤에 있으니 +1을 하는 방식으로 어느

1 에서 N 으로 갈 때 u, v 두 개의 정점을 반드시 지나야 한다고 하는데 경로 그려보면 가능한 경우는 아래 두 가지 뿐이다. 결국 구해야 하는 최단 경로는 아래와 같다.v 에서 1, u, N으로 가는 경로들과 u에서 1, v, N으로 가는 최단 경로들을 구하면 된

처음 백준이가 서 있는 위치를 idx 라고 하자. 여기서 t^3 만큼 이동해야 한다. 이때 한 줄로 서 있고 가장 끝까지 이동하면 다시 처음으로 되돌아오는 구조이기 때문에 t^3을 전체 서 있는 사람의 수로 나눈 나머지가 실제 중복 없이 이동해야 하는 거리이다. 현재

과목들은 위의 그림과 같은 관계를 가지고 있다. 해당 그림에서 선수 과목은 파란선으로 표시된다. 선수 과목이 없는 경우 1학기에 바로 들을 수 있고 해당하는 과목들은 1, 4, 6이 된다. 1학기에 들은 과목을 제외하면 남은 과목은 위와 같다. 5를 듣기 위해서는 2를

주유소 최대 개수를 생각하면 완전 탐색은 불가능하고, 그래서 처음엔 뒤에서 앞으로 오면서 이전의 값을 저장해두는 dp 방식을 생각했지만 너무 복잡해졌다. 다시 앞에서 뒤로 가는 걸 생각하니 그냥 이전의 주유소 리터 값과 현재의 주유소 리터값을 비교해서 이전 값이 더 작

1 -> 2, 3 -> 4 와 5 -> 4 2가지 경로가 존재할 수 있다. 이때 매 노드마다 걸리는 시간들을 갱신해야 한다. 2, 3의 경우 1이라는 같은 출발지를 갖고 있기 때문에 30과 40의 시간이 최소로 걸리게 된다. 이제 4는 2, 3, 5 중 하나에서 도달할

이 문제는 최대한 많이 배달해야 하므로 빨리 배달할 수 있는 것들부터 빨리 배달할 수록 많이 배달할 수 있다.(1) 보내는 곳에서 받는 곳까지의 거리가 가장 짧은 순 (2) 택배의 개수의 크기가 큰 순서대로 정렬해야 된다고 생각했다. 근데 애초에 (2)는 고려할 필요가

모든 가능성을 고려하면서 최소 횟수를 구하는 문제이므로 그래프 탐색의 너비 우선 탐색 방식과 구슬의 이동 경로를 시뮬레이션하는 두 가지 방식을 합해서 풀이했다. 우선 빨간 구슬과 파란 구슬은 사방으로 움직일 수 있고, 벽을 마주하거나 다른 구슬을 만나기 전까지는 계속

위상 정렬 알고리즘 문제인데 먼저 풀어야 하는 문제가 없는 문제들 중에서 가장 쉬운 문제(숫자가 낮은 문제)부터 풀어야 하기 때문에 조건에 해당하는 문제들을 담을 때 큐를 우선순위 큐를 사용했다. 매번 정렬하는 대신 매번 풀어야 하는 문제가 가장 작은 문제부터 나올 수

비싼 쥬얼리부터 가방에 담아야 한다. 근데 이때 최대한 효율적으로 가방에 담아야 한다. 비싼 순서대로 정렬한 다음에 쥬얼리의 무게와 가장 차이가 나지 않는 가방에 담으려고 했는데 그렇게 되면 예제2에서 (2, 99)의 보석이 2 크기의 가방에 담기게 되고, (1, 65

수열을 정렬했을 때 두 수 사이의 간격이 M 이상이라면 구할 수 있는 차이 값을 업데이트 한다. 이때 왼쪽에 있는 수 A 라고 했을 때 이제 B 뒤에 있는 수들은 차이 값이 현재 구한 B - A 라는 차이 값 이상이 되기 때문에 더 이상 구하는 의미가 없다. 이때는 이

1202\. 보석도둑 과 유사한 문제.며칠 내에 과제를 해결해야 하는지 기한이 주어지지 않으므로 주어지는 과제들 가운데 최대 마감일을 기한으로 정하면 된다. 어차피 그 이상의 기한을 줘 봤자 수행할 수 있는 과제가 없기 때문에. 문제 예제에서는 6일이 최대이기 때문에

1182\. 부분 수열의 합 문제와 유사한데 범위가 다르다. 1182번은 N = 20이라서 부분 집합을 전부 구해도 시간 초과가 발생하지 않지만(2^20 = 대략 백만) 1208번은 N = 40 이라서 시간 내에 구할 수 없다. 그래서 아래와 같이 반으로 나눠서 푸는

원형 형태의 DP 문제이다. N의 수를 늘려가면서 n번째 칸을 선택하거나, 선택하지 않는 경우의 수로 나눠서 생각하면 된다. N=4, K=2 라고 가정할 때, 아래와 같이 생각해볼 수 있다.먼저 N=4 번째 칸을 선택하지 않은 경우이다. 이 경우는 사실상 4칸 중 1칸

현우의 통장 잔액은 고려할 필요가 없다.정확히 M번 맞추기 위해 의미없는 입금과 출금을 반복할 수 있으므로 인출 금액이 K일 때 반드시 인출해야 하는 횟수가 M이하면 된다. K의 초기값이 될 수 있는 값 중에 최소값은 최대 N일과 하루에 쓸 수 있는 최대 금액(10,0

휴게소가 없는 구간의 값을 탐색하는 것이 목적이다. 해당 구간은 1보다 크고, 고속도로의 최대 길이보다는 반드시 작다. 문제에서 주어지는 L은 1000이 최대값이기 때문에 결국 휴게소가 없는 구간의 값은 1 ~ 1000 내에 존재한다고 할 수 있다.1~1000 내의 임

질문의 개수는 최대 백만이고 수열의 크기가 2000이기 때문에 모든 질문에 대해서 매번 팰린드롬인지 여부를 확인하면 시간 초과가 발생할 수 있다. 그래서 규칙을 찾아서 S~E까지 팰린드롬인지를 한 번에 확인할 수 있도록 미리 메모이제이션을 통해 저장해둬야 풀 수 있는

승객을 태운 다음에 목적지까지 이동하는데 항상 모든 경로가 최단거리로 이루어져야 한다. 그래프 탐색 중에서 최단 거리를 가장 빠르게 구할 수 있는 너비 우선 탐색 방식을 이용한다. 너비 우선 탐색은 인접한 정점 순서대로 방문하게 되는데 이때 같은 최단 거리에 여러 승객

아래 2가지만 고려하면 쉽게 풀리는 이분탐색인데 둘 다 못해서 틀렸다. 승률을 구할 때 소수점을 버리기 위해 곱해야 하는 100의 위치\-1이 나오는 경우승률을 구하기 위해서는 X와 Y 자료형을 double 로 변경해서 구해야 하는데 이때 소수점 2자리까지만 구하고 나

배열의 크기는 1000 x 1000으로 각 벽에 대해서 매번 인접한 이동할 수 있는 칸을 찾게 되면 시간 초과가 발생할 수 있다. 각 벽에 대해서 인접할 수 있는 칸들은 결국 벽이 아닌 칸(0)들이기 때문에 이어져있는 벽이 아닌 칸들에 대해서 서로 인접해있는 칸들의 개

트리 형태지만 양방향이기 때문에 루트 노드는 어느 노드가 되어도 상관 없는 구조이다. 문제만 읽으면 마을 하나를 선택하고 그 다음 마을을 건너뛰는 식으로만 하면 될 것 같지만 실제로 예제를 보면 아래와 같은 경우도 가능하다. 2 - 6 은 서로 인접해있지만 둘 다 우수

최장 증가 부분 수열 문제이다. 나열된 전봇대의 숫자들 중에 가장 긴 증가하는 연속된 수열을 찾으면 된다. 1부터 N번까지 탐색하면서 매번 현재의 값보다 큰 값 중 가장 최소인 값을 찾아 그 값을 대체하는 방식을 택하게 된다. 위와 같은 수열이 있을 때 노란 수열은 길

출발지에서 목적지로 갈 수 있는 경로는 여러 개가 있을 수 있고, 그 여러 개의 경로 가운데 각 경로가 가지는 골목의 최대 요금값 중 최소를 찾는 문제이다. 우선 목적지까지 도달할 수 있는지 여부를 확인해야 하기 때문에 백트래킹을 사용해 도달할 수 있는 경로들을 판별하

멘토링 관계를 자료구조로 표현하면 트리 구조가 된다. 멘토는 부모 노드, 멘티는 자식 노드다. 만약 부모 노드가 하나의 자식 노드와 멘토링 관계를 맺게 되면 나머지 자식 노드들과는 멘토링 관계를 맺을 수 없다. 결국 멘토링 관계라는 건 모든 노드들에 대해서 자식 노드와

발전소는 최대 16개이고 모든 발전소는 켜져 있거나/꺼져 있는 , 두 가지 상태를 가지게 된다. 켜진 상태를 1이라고 하고 꺼져 있는 상태를 0이라고 하자. 켜진 발전소로만 꺼져 있는 발전소를 작동시킬 수 있으므로 우선 작동시킬 꺼진 발전소를 찾은 후 해당 발전소를 어

수열의 최대 크기는 9999이기 때문에 매번 숫자가 추가될 때마다 정렬을 하고 중앙값을 찾는 방식은 비효율적이다. 어떤 수열을 정렬해서 중앙값을 찾을 때의 구조는 위와 같다. 길이는 항상 홀수이기 때문에 중앙값을 기준으로 더 작은 값과 중앙값을 포함한 더 큰 값들로 나

왼쪽과 오른쪽 발을 (왼쪽 발, 오른쪽 발)처럼 하나의 좌표로 나타냈을 때 매번 발을 옮길 때마다 가능한 모든 좌표에 대해서 계산해야 한다. 매번 최선의 선택을 한다고 해서 최종적으로 최소가 된다는 것을 보장할 수는 없기 때문이다. 그래서 해당 문제는 그리디가 아니라

n길이의 암호코드가 있다면 해당 암호코드가 가질 수 있는 해석의 수는 이전의 암호코드들이 가지는 해석의 수를 포함하게 된다. 그림으로 나타내면 다음과 같다. 길이3의 암호코드 123은 (12, 3)과 (1, 23)으로 나눌 수 있다. 해석 가능한 암호는 1~26사이의

좌측 상단인 좌표 (0, 0)에서 시작하여 모든 보드를 탐색하며 최대 몇 칸 지날 수 있는지 확인하는 문제이다. 전체 보드의 크기가 최대 400이기 때문에 완전 탐색으로 진행하여도 시간 초과는 발생하지 않을 수 있다. 특정 시점에서 가능한 모든 방향에 대해 확인해야 한

전체 배열의 크기가 1000x1000으로 백만이기 때문에 브루트포스 방식으로 모든 경우의 수를 탐색하는 건 불가능하고 한 번의 탐색으로 최대값을 구할 수 있어야 하므로 다이나믹 프로그래밍을 사용했다. 우선 상승의 경우 위와 오른쪽으로만 갈 수 있다고 하였고 시작점은 반

전체 방 N의 최대값은 백만이고 빅-종빈빌런이 행동을 수행하는 횟수는 최대 M이기 때문에 M번의 행동을 할 때마다 깨부수는 벽들의 정보에 대해서 일일이 확인하는 방식은 시간초과가 발생할 수 있을 것 같다. 빅-종빈빌런이 방을 부술 때는 연속해서 있는 벽들을 허문다는 규

N은 최대 1000이므로 모든 경우에 대해서 브루트 포스 방식으로 구하는 것은 1초 내에 연산이 불가능하다. 대신 규칙을 찾아보기로 했다. 간단하게 N=3에 대해 가능한 모든 경우의 수를 구하면 아래와 같다. 순서에 따라 정렬할 수 있는 가지수는 Nx(N-1)/2 =

선물 가격들은 D이상이 차이나면 안 된다. 최대 값과 최소값의 가격 차이가 가장 클 것이기 때문에 이 값이 D이상이 되면 둘 중 하나를 빼야 한다. 이때 N이 10만이기 때문에 가능한 모든 경우의 수를 조합해서 구하는 것은 2초 내에 연산이 불가능하다. 대신 선물의 가

최소 거울의 개수를 찾는 문제라서 최소라는 말만 보고 BFS인가 싶었지만 최단 거리로 도착하는 경우가 반드시 최소 거울의 개수를 보장하지는 않는다. 거울의 개수를 최소로 가진다는 것은 결국 회전하는 횟수가 최소라는 뜻이지 방문해야 할 위치의 수가 최소인 것은 아니기 때

바라보는 방향은 딱 2번 회전할 수 있고, 처음 바라보고 있는 방향은 오른쪽으로 고정이다. 즉 오른쪽 -> 왼쪽 -> 다시 오른쪽, 이렇게 3가지 경우만 존재하게 된다. 주어지는 예제들은 세 가지 경우를 구분하지 않고 계산해도 제대로 된 정답이 나올 수 있지만 실제로는