BaekJoon

사용 알고리즘 : DP + 다익스트라처음엔 그냥 단순 다익스트라 알고리즘으로 해결하려 하였으나 만약 다른 루트에서 이미 지난 적이 있다고 하더라도, 즉 최소 이동 횟수가 아닌 루트로 이동하더라도 그 위치로 이동 하는 것이 최소 비용일 수 있는 경우를 고려하기 위해 DP

처음엔 투 포인터로 접근 했으나 투 포인터만으로는 4번에서 요구하는 최댓값을 구하기 어려웠고, 마땅한 알고리즘이 떠오르지 않아 일단 슬라이딩 윈도우를 통한 완전탐색으로 코드를 작성해보았지만 당연하게도 시간 초과였다.그러던 도중 결국 3번, 4번 각각의 요구에 해당하는

사용 알고리즘 : 그리디 알고리즘가방과 최대 무게라는 말에 반사적으로 DP문제인가 싶었지만 가방에 최대 한 개의 보석만 넣을 수 있다는 말을 보고 다시 생각했다 ㅋㅋㅋ결국 입력된 보석 정보를 무게 기준으로 오름차순으로 정렬, 각 가방도 최대 무게 기준으로 오름차순 정렬

사용 알고리즘 : DP + DFS목표 지점부터 시작하여 상하좌우에 해당하면서, 높이가 더 높은 위치로 이동가능한 루트의 갯수를 누적해서 합해주는 방식으로 구현하였다.

사용 알고리즘 : DP매우 매우 전형적인 가방채우기 DP 문제이다.아이디어를 떠올리는 것과 구현 자체는 쉬우나 실수형의 자료를 정수형으로 캐스팅 하는 과정에서 발생하는 rounding error를 생각하지 못해서 헤맬 가능성이 많은 문제다.보통 정수형 캐스팅을 하기 전

풀이 방법 : DFS무식하게 풀고 맞긴 했는데, 풀고 나서 분류를 보니 너비 우선 탐색이라고 나와있긴 하더라 깊이 우선 탐색으로 풀면 중복 탐색 막는 과정이 번거로워져서 이렇게 분류된건가 싶다.그냥 재귀함수에서 이중 for문 돌리면서 넘겨받은 문자열의 각 문자들을 sw

풀이 방법 : 그리디먼저 입력된 데이터에 대해 회의 시작 시간을 기준으로 오름차순으로 정렬해준다.가장 먼저 시작하는 회의(0번 인덱스)의 자료를 우선순위 큐에 넣어준다.이때 우선순위 큐의 정렬 기준은 종료시간이 가장 빠른 녀석이 pop되도록 해준다.순서대로(회의시간이

매개 변수 탐색으로 접근할 때 중요한 것은 정답을 매개 변수화할 수 있는지, 매개변수에 따라 참인지 거짓인지를 따질 수 있는지를 잘 따져보자이분 탐색은 어떤 기준으로 변수의 범위를 좁혀나갈 것인지만 잘 생각하면 쉬워지는 것 같다. 물론 그게 어렵지만...

풀이 방법 : DFS간단하게 색약이 아닌 경우, 색약인 경우로 두 번 깊이 우선 탐색을 돌려주면 된다.입력값이 작으니 2번 돌려도 시간이 충분하다.구분할 수 있는 색을 만나면 더 이상 탐색을 진행하지 않도록 했고 하나의 탐색이 끝나면 구역의 수를 하나 늘려주는 식으로

풀이 방법 : 이분 탐색이 문제에서 배정된 예산들 중 최댓값인 정수를 출력하라는 것은 가능한 예산 상한선의 최댓값을 출력하라는 것과 같다.그럼 예산 상한선의 최댓값을 찾아내면 되는데, 이처럼 특정 범위 내에서 최댓값을 찾아내는 문제는 이분탐색을 고려해볼만 하다.

풀이 방법 1\. set을 이용한 풀이2\. stack을 이용한 풀이처음엔 그냥 생각나는 대로 풀었다. 입력된 높이가 이전에 입력되지 않은 높이라면 건물로 인정이 될 수 있다. 하지만 입력된 적이 있는 높이라고 하더라도 그 사이에 자기보다 낮은 높이가 입력된 적이 있다

풀이 방법 : BFS + 우선 순위 큐가중치를 고려하면서 탐색해주어야한다. 이동 후의 위치들과 걸린 시간을 묶어 우선 순위 큐에 넣어주고 지금까지 걸린 시간이 적은 케이스부터 우선적으로 탐색해주도록 한다.이렇게 하면 가장 먼저 K에 도달하는 경우가 최소 시간이 걸리는

풀이 방법 : 다익스트라각 마을에서 X까지 걸리는 최단 시간을 탐색하는 데 입력된 그래프 정보대로만 탐색한다면 최대 1000번의 탐색이 필요할 수 있다. 이를 방지하기 위해 입력된 그래프 정보를 반대로 저장하여 역방향 그래프를 하나 만들어내고 그를 통해 X에서 각 마을

풀이 방법 : 그리디먼저 주어진 문자열이 팰린드롬으로 만들 수 있는지 따진다.주어진 문자열에 들어있는 각 알파벳들의 수를 카운팅 했을 때 홀수인 알파벳이 1개보다 더 많이 있다면 그 문자열은 팰린드롬으로 만들 수 없다.이를 따지기 위해서 map을 이용해서 카운팅을 해줬

풀이 방법 : 우선 순위 큐비슷한 문제가 참 많은 문제 현재 있는 파일 중에서 가장 작은 두 개를 골라 합치는 것을 반복하면 가장 최소 비용으로 파일을 합칠 수 있다. 그러므로 우선순위 큐를 통해 최솟값 두개를 뽑아내서 합을 구하고 비용에 누적 시킨 뒤 합친 파일을 다

풀이 방법 : 브루트 포스문제에서 연산자의 우선순위는 괄호가 없다면 모두 동일하다고 가정했기 때문에 단순하게 괄호의 유무에 따른 경우들만 따져주면 된다.처음 인덱스부터 시작해서 괄호 씌운 경우, 괄호 안씌운 경우로 나뉘어서 계산해준다.씌우지 않은 경우는 그대로 인덱스만

풀이 방법 : 단순 구현문제가 길어서 헷갈리는 것만 빼면 어려울게 없는 문제, 착실히 요구사항을 따라가자.양분은 어린나무부터 먹는다. 정렬을 해도 좋은 선택이겠지만 어차피 나중에 번식으로 인하여 추가되는 나무는 무조건 이전 나무보다 어린 나무일 것이므로 vector를

풀이 방법 : DFS여행 플랜의 첫번째 지점부터 연결된 지점들을 따라서 DFS를 했을 때 플랜에 속해있는 지점들의 check 플래그가 전부 true가 되어있으면 YES를, 하나라도 false가 존재하면 NO를 출력해주는 방식으로 구현했다.유니온 파인드를 이용하면 더 빠

풀이 방법 : BFS3차원 배열이라는 것만 빼면 어느 BFS와 다를게 없는 문제현재 위치에서 동서남북상하 6방향으로 이동할 수 있는지 체크하면서 목적지에 도달했을 경우 그 시간을 체크하면 된다.

풀이 방법 : DPDP로 풀어야겠다는 건 빨리 캐치했지만 DP 테이블을 r오락실 번호의 3차원 배열로만 생각해서 아무리 풀어도 못풀겠더라 그래서 검색을 해보니 4차원 배열을 사용해야 하는 문제라고 한다...그 말을 보고 생각해보니 단순히 오락실 번호뿐만 아니라 지금까지

풀이 방법 : DFS + DP그래프들의 내용을 탐색하면서 싸이클이 발생하는지의 유무를 따져줘야 하기 때문에 DFS를 선택했다. 백트래킹 하듯 해당 좌표에서 탐색 시작할 때 check 플래그를 true로 해주고 탐색이 끝나면 false로 해준다. 이렇게 해주면 중간에 c

풀이 방법 : 백 트래킹해당 알파벳을 지났는지 체크해서 step수를 늘려가다가 이미 지났던 알파벳을 만나면 최댓값을 갱신 시켜주면 된다.시작지점인 좌상단을 포함하라고 했으니 시작 Step을 1로 넣어준다.

풀이 방법 : DP유명한 시리즈의 문제 DP테이블에 각 자리까지의 최대 길이를 갱신해주면 된다. 이전 시리즈의 문제와 다른 점은 그때까지의 경로를 함께 저장해주어야 한다는 점이다.이중 포문을 돌려주면서 이전의 숫자보다 현재 숫자가 더 큰 경우에 길이를 비교하고 이전까지

풀이 방법 : DP팰린드롬이 되는 경우들을 따져보면1\. 자기 자신(길이 1)2\. 길이가 2 이면서 앞 뒤가 같은 경우3\. 길이가 3 이상 (j - i >= 2)일 때 Numsi == Numsj 이면서 i + 1 부터 j - 1까지의 수열이 팰린드롬인 경우그래서 처

풀이 방법 : 정렬, 스위핑물 웅덩이의 시작점을 기준으로 오름차순으로 정렬해준 후 최소 지점부터 널빤지를 덮어나간다고 생각하자.널빤지가 끝나는 지점의 위치를 기억해두고 만약 다음 물 웅덩이의 시작점이 이전 널빤지가 끝나는 지점보다 더 작은 경우, 해당 위치부터 덮어가기

풀이 방법 : DP연속 결석일이 0일이 될 수 있는 경우는 이전날까지 연속 결석일이 며칠이 됐든 그 다음날 출석이든, 지각을 하는 경우다.다행히 연속 결석일만 잘 처리하여 점화식을 짜면 다른 케이스들은 그렇게 어렵진 않다.

풀이 방법 : 정렬, 스위핑선분이 겹치느냐 안겹치느냐에 따라 따로 처리해주면 된다.이를 처리해주기 위해서 선분의 시작점을 기준으로 오름차순 정렬 해주고, i-1번째 선분의 끝점이 i번째 선분의 시작점보다 크거나 같은 경우 선분이 겹친 것이고, 그 반대라면 겹치지 않은

풀이 방법 : 스택처음에는 단순무식하게 풀었다. 가장 가까운 녀석부터 검사해가면서 왼쪽의 탑의 전파가 닿은 탑들을 대상으로 검사해주는 방식으로 검사했다.이렇게 해도 풀리긴 했으나 어차피 루프를 돌릴것이고 더 가까운 녀석들 부터 검사를 할거라면 stack을 사용하는 것이

풀이 방법 : 구현그냥 문제가 요구하는 대로 따라가면 된다. 여기서 헷갈리지 말아야할 것은 입력을 기준으로 어느쪽이 북쪽인지다.또한 이미 청소를 완료한 좌표라고 하더라도 "이동"은 가능하다는 것을 까먹지 말자.

풀이 방법 : 그리디문제에 나온 규칙에 따라 이미 변환된 문자열을 다시 십진수로 변환하는 문제다. 변환할 때 나올 수 있는 숫자의 최댓값과 최솟값을 차례대로 출력해주면 된다.입력으로 주어지는 문자열의 길이의 최댓값이 3000이므로 숫자 또한 문자열로 처리해주자.최댓값

풀이 방법 : 브루트 포스우리가 배치한 트램펄린의 범위 안에 들어오는 별똥별의 갯수를 세줘서 그 최댓값을 구하면 된다.처음에는 각 별똥별의 좌표가 트램펄린의 가장자리에 오는 경우만 생각해도 될 거라 생각했는데 예외가 너무 많았다.입력되는 별똥별 갯수의 최댓값이 100개

풀이 방법 : 슬라이딩 윈도우문제에서 문자열이 원형으로 이루어져 있다고 했기 때문에 a를 연속으로 만드는 방법은 a를 가운데로 몰아넣거나 b를 가운데로 몰아넣는 경우 두 가지가 있을 수 있다.a를 가운데로 몰아넣는 경우에는 a의 갯수를 세서 그 크기만큼의 슬라이딩 윈도

풀이 방법 : 다익스트라문제를 보고 처음엔 뭔 소린가 싶었다. 밑에 있는 힌트 정보를 보고 난 뒤에야 문제를 이해했다.결국에는 그래프 탐색을 진행해가면서 사람을 가장 적게 만나면서 범인에게 도달하는 경우를 찾는 문제였다.그래서 구조체에 좌표정보와 파동이 거쳐간 사람의

풀이 방법 : 재귀 탐색가능한 최대 크기의 정사각형부터 체크하여 한 가지 색깔로 이뤄진 정사각형인 경우 해당 색깔의 수를 늘려주고 정사각형이 아닌 경우, 영역을 1/4로 나눠 각 사각형을 반복적으로 체크해준다.이를 위해 색깔 체크 함수를 재귀 호출 해주었다.

풀이 방법 : 문자열 탐색(?)이런 풀이를 뭐라 해야하는 지를 모르겠다. 일단 조건에 맞는 부분 문자열은 무조건 I로 시작해야한다. 0번 인덱스부터 문자열을 탐색해나가면서 I를 만날 경우 while문 안에 들어가서 계속 반복 돌려주면서 그 다음 문자가 O 그 다음문자가

풀이 방법 : 그리디처음에 제한사항도 안보고 그냥 DP겠거니 하고 대충 풀었다가 메모리 초과가 떴었다. K의 최댓값이 1억이기 때문에 DP 배열을 1억개나 할당해버리면 메모리 제한을 넘겨버리기 때문이었다.그래서 어떻게 풀어야하나 하다가두번째 조건에서 첫번째 입력은 무조

풀이 방법 : 누적 합각 행의 각 인덱스까지의 누적 합을 미리 구해놓고 입력이 주어지면 해당 인덱스에서 이전 인덱스의 누적 합을 빼주면 해당 구간 합이 구해진다. 이를 열 별로 반복하면 된다.

풀이 방법 : DFS입력으로 주어지는 트리의 노드 간의 연결정보를 다 저장해 준 후 시작점을 1로 두고 DFS를 돌려주면서 부모 정보들을 갱신해나가면 된다.

업로드중..주어진 K개의 랜선을 적당한 크기로 나눠 N개 이상의 새로운 랜선들을 만들어내야한다.Left = 1 , Right = K개 랜선중 최대 길이Half = (Left + Right) / 2 라 치면Half로 나눈 값들의 총 합이 N 이상이다\-> 정답 갱신 후

풀이 방법 : 투 포인터데이터가 오름차순으로 정렬된 상태로 입력되므로 양 끝을 처음 기준으로 삼아 탐색한다.만약 양 끝의 용액의 합이 양수일 경우 0에 더 가까워지기 위해서는 더 작아져야 하므로 큰 쪽의 수를 줄여준다. 즉, 오른쪽 포인터를 왼쪽으로 옮겨준다. 마찬가지

풀이 방법 : DPi-1번째에서 이동 가능한 곳의 값을 i번째의 값에 더해주면 된다.예를 들면 i번째 줄의 0번 인덱스에는 i-1번째 줄의 0,1 번 인덱스에서 접근 가능하므로 둘 중에 더 큰 값을 더해주는 식으로 값을 갱신해나가면 최댓값이 구해진다.같은 방법으로 더

풀이 방법 : 큐, 구현문제에서 뱀이 입력으로 주어진대로 움직였을 때 자기 자신과 부딪히거나 보드 밖으로 나갈 때가 몇 초인지 구하는 문제이다.이동 도중 사과를 만나면 자신의 몸의 길이를 1 늘리고 꼬리는 움직이지 않는다. 꼬리 부분이 자라난다고 생각하면 될 것이다.반

풀이 방법 : 브루트포스 , 비둘기 집 원리일단 입력으로 주어진 모든 경우들을 다 비교해서 해야 한다는 것은 알겠는데 입력값의 N의 최댓값이 100000이므로 O(n^3)의 방법으로 비교해버리면 무조건 시간 초과가 날 것이다.여기서 비둘기집 원리를 사용해야 하는데 MB

풀이 방법 : DP점수의 합이 최대가 되도록 스티커를 떼어내야 하는 문제하나의 스티커를 뜯게 되면 뜯은 스티커와 변을 하나라도 공유하는 스티커는 뜯을 수 없다. 왼쪽에서부터 차례대로 스티커를 뜯어간다고 생각하고 각 인덱스의 스티커를 뜯을 수 있는 경우 중 최댓값을 구해

풀이 방법 : 그리디랭킹이 높은 사람이 무조건 이기고 입력값은 랭킹은 1 ~ N까지 주어진다고 했기 때문에 결국에는 무조건 1위가 우승을 한다.그렇다면 제일 낮은 순위의 사람을 가능한 최소한의 차로 경기를 진행하도록 하면 자연스럽게 랭킹차의 합이 최소화될 것이다.그렇기

풀이 방법 : 브루트 포스 , 깊이우선 탐색각 높이로 물이 잠겼을때 생길 수 있는 안전 영역의 수를 모두 카운트 해주면 된다. 그래서 set 컨테이너에 각 지역의 높이 정보들을 넣어놓고 중복없이 해당 높이에 대해서 모든 경우를 탐색해주었다.

풀이 방법 : 수학각 두 개의 터렛의 좌표와 해당 좌표에서 마린까지의 거리가 나와있으니 두 개의 원을 그릴 수 있다.그 두 개의 관계에 따라 원이 만나는 지점의 갯수를 생각해주면 마린이 있을 수 있는 위치의 갯수를 알 수 있다.아예 안만나는 경우 = 0개외접 혹은 내접

풀이 방법 : 브루트 포스두 빌딩 사이의 직선의 방정식을 세워 해당 식에 두 빌딩 사이의 빌딩들의 좌표들을 각각 대입했을 때 사이에 있는 빌딩중 하나라도 해당 직선보다 높은 녀석이 있을 경우 그 빌딩은 볼 수 없는 빌딩이다.y = ax + ca = (y1 - y2) /

풀이 방법 : 이분 탐색Low값을 1, High 값을 주전자 용량 중에 가장 큰 용량으로 두고 루프를 돌려가며 Low와 High의 중간값으로 각 주전자의 용량을 나눈 수들을 누적해 더해간다.누적된 합 즉, 그 중간값대로 막걸리를 나눠줬을 경우, 최대로 나눠줄 수 있는

풀이 방법 : DP문제에서 준 조건을 해석해보면 각각의 경우가 가능한 경우들은1번 식당 : 전날(i - 1일)에 굶었거나 3번 혹은 4번 식당에 간 경우2번 식당 : 전날에 굶었거나 4번 식당에 갔던 경우3번 식당 : 전날에 굶었거나 1번 식당에 갔던 경우4번 식당

풀이 방법 : BFS두 로봇이 출발점에서 각 방까지 가는데에 이동해야하는 최소 거리를 BFS를 통해 계산해서 구해준 다음 통로를 통해 연결되어 있는 방들을 대상으로 각 방에 도달하는 최소 거리를 더한 값들의 최솟값을 갱신시켜가면 된다.

풀이 방법 : 그리디0의 절반만큼 0을 제거하고, 1의 절반만큼 1을 제거해서 사전순으로 가장 빠른 문자열을 구하는 문제다.당연하게도 사전순으로 따지면 0이 1보다 앞에 온다. 그러므로 되도록이면 0이 앞에 있고 1이 뒤에 있는 문자열을 구하는게 맞을 것이다.반복문을

풀이 방법 : 스택오른쪽에 있는 건물만 볼 수 있으므로 오른쪽 끝에서부터 건물 번호를 스택에 넣어두고 시작하자반복문을 오른쪽에서부터 돌려가면서 검사할 때 만약 스택에서 숫자를 꺼냈을 때 현재의 건물보다 낮은 높이의 건물일 경우 스택에서 pop해준다.높거나 같은 높이의

풀이 방법 : DFSN이 작아서 사실 어떤 방식으로 풀어도 되는 문제다. 만약 N이 컸다고 한다라면 DP로 해결이 가능할 것 같다.그냥 간단하게 아래, 오른쪽으로만 이동하면서 연산자에 따라 현재 숫자를 연산해가면서 끝에 도달했을 때 최대, 최솟값을 갱신 해주면 된다.

풀이 방법 : 다익스트라(?)사실 다익스트라 말고 MST처럼 푸는게 더 빠를듯 근데 자신없어서 그냥 다익스트라로 풀긴 했다...각 지점까지 도달하는 루트에서의 길의 너비의 최솟값들을 갱신해나가면서 탐색을 한다. 만약 해당 지점까지의 너비의 최솟값보다 더 작은 루트일경우

풀이 방법 : 수학(?), 브루트포스수학으로 풀었다고 하기도 민망하다 태그를 보니까 투 포인터로도 가능하다는데 범위 보니까 싹 다 검사해도 시간초과에 안걸릴 것 같아 그냥 무식하게G = Cur^2 - Prev^2Cur^2 = G + Prev^2를 만족시키는 자연수들을

풀이 방법 : 그리디주어진 숫자들의 합으로 만들 수 없는 최소인 양의 정수를 출력하는 문제다.먼저 입력으로 주어진 추들을 오름차순으로 정렬 하고 가벼운 추부터 시작해서 비교해가기 시작한다.현재 무게는 1부터 시작해간다. 만약 현재 무게보다 비교하는 추가 더 무거울 경우

풀이 방법 : DP왼쪽 자릿수의 숫자가 오른쪽 자릿수보다 작거나 같은 숫자의 갯수를 구하는 문제다.N이 1인 경우 0 ~ 9까지 10개다.N이 2일때 가장 앞자리가 0인 경우 일의 자리가 0 ~ 9 까지인 경우가 가능하다. 가장 앞자리가 1인 경우 일의자리가 1~ 9까

풀이 방법 : 브루트 포스A를 주어진 조건대로의 연산으로 B를 만들 수 있는지 하는 문제이다.만약 A에서 주어진 연산 두 가지를 계속 적용시켜가면서 연산을 하면 따지게 되는 경우의 수가 너무 많아져서 시간 혹은 메모리 초과가 날 것이다.반대로 B에서 주어진 연산을 거꾸

풀이 방법 : 그리디M번 자를 수 있을 때 길이 10인 케이크 개수의 최댓값을 구하는문제다. 길이가 10으로 나누어떨어지는 케이크들을 우선적으로 잘라서 개수를 구하고 그 뒤에 다른 케이크들을 잘라야한다. 길이가 26이라면 2번 잘라야만 길이가 10인 케이크가 두 개 나

풀이 방법 : 에라토스테네스의 체1부터 N까지 숫자를 색칠하되, 서로소인 다른 자연수는 다른 색으로 칠해야하는 문제결국 (1 < i) 라 할때 i의 배수는 i와 같은 색으로 칠할 수 있다는 얘기다.1은 무조건 다른 모든 숫자와 다른 색이어야하므로 2부터 시작해서

풀이 방법 : DFS습관적으로 DFS로 풀긴 했지만 아무래도 최단경로를 구해야하는 문제다보니 BFS로 푸는게 더 빠를 것 같다.그냥 출발 코드에서 시작해서 길이가 해밍 거리가 1인 거리를 찾아가면서 탐색해가면 된다.

풀이 방법 : DP입력으로 주어지는 대로 단방향 그래프를 하나 만들고 1에서부터 출발해서 거리 계산해주며 최단거리를 갱신해주면 된다.예시 입력을 보니 지름길의 도착지점이 입력으로 주어지는 D보다 큰 경우가 있길래 이 경우는 건너 뛰도록 해주었다.

풀이 방법 : 투 포인터입력으로 주어지는 수열을 오름차순으로 정렬한 뒤 0번 인덱스부터 시작해서 차이값을 토대로 왼쪽, 오른쪽 포인터들의 인덱스를 증가시켜나간다. 같은 수를 고르는 것이 허용되는 문제이므로 Left, Right 둘 다 0에서부터 시작한다.오름차순으로 정

풀이 방법 : 정렬A의 요소가 B의 요소보다 큰 쌍의 수를 출력해주면 되는 문제다.주어지는 A와 B를 둘 다 오름차순으로 정렬 해주고 비교한다 치면, 만약 Ai가 Bj보다 크다고 한다면 당연하게도 Ai+1 또한 Bj 보다는 크다는 얘기이므로 쌍의 갯수를 누적해가면서 구

풀이 방법 : 백트래킹선택한 구슬을 체크하고 그 양 옆에 있는 구슬의 곱을 더해가며 남아있는 구슬의 갯수가 2개가 남았을 때, 즉, 양 끝의 구슬만 남아있을 때까지 반복해서 구한 값들의 최댓값을 갱신해나가면 되는 문제이다.

풀이 방법 : 그리디0으로 채워져있는 배열 A 에서 입력으로 주어진 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제다.처음에는 최소 횟수라길래 반사적으로 BFS를 생각했고 문제에 주어진 연산으로 A에서 B로 바꾸는 모든 경우를 생각하면 경우의 수가 너무 많아져 시간

풀이 방법 : 그리디처음엔 감이 안와서 완전 탐색에서 경우의 수를 줄이는 방향으로 생각해봤다.완전탐색을 한다 치면 L부터 시작해서 R까지 증가시켜가면서 각각 8의 갯수를 세주면 될 것이다.여기서 L과 R의 자릿수가 다른 경우를 생각해보았다. 만약 R이 자릿수가 L보다

풀이 방법 : 스택결국 커서의 위치를 잘 파악하는게 가장 중요한 문제 커서를 중심으로 왼쪽부분, 오른쪽 부분으로 나눠서 문제에서 요구하는 연산들을 수행하는게 편할 것이다. 중간 삽입 삭제가 빈번할 것이기 때문에 링크드 리스트를 이용해서 푸는 것도 가능할 것이다.1\.

풀이 방법 : DFS입력받은 정보를 단방향 그래프에 저장해준뒤 각 인덱스로부터 출발하여 깊이우선 탐색을 진행한다.깊이우선 탐색을 통해 구슬들의 관계를 알 수 있다.1\. i번째 구슬에서 출발하여 도달할 수 있는 번호의 구슬들은 i번보다 가볍다는 뜻이다.2\. 다른 번호

풀이 방법 : 정렬입력으로 주어진 두 성적이 다른 지원자와 비교했을 때 두 성적이 모두 다른 사람보다 낮은 케이스가 있다면 그 사람은 선발될 수 없다.입력으로 주어진 등수 둘 중 하나를 기준으로 정렬해둔다면, 나머지 다른 등수만 비교해주면 N번 반복만으로 선발할 수 있

풀이 방법 : 최소 신장 트리어찌 보자면 전형적인 MST 문제, 입력으로 주어진 경로들 중 남초 대학끼리 잇는 경로와 여초 대학끼리 잇는 경로들을 제외한 경로들을 가지고, 유니온-파인드 알고리즘을 이용하여 최소신장트리를 구성해주면 된다.최소신장트리를 구성할 수 있는지

풀이 방법 : DP입력 값들중 최댓값을 저장 값으로 삼고 가중치를 더해 출력 값을 구하다보면 결국에는 입력값중 최댓값은 바로 직전 열에 있는 입력값들 중에서만 나온다는 것을 알 수 있다. 바로 직전 열들의 입력값들은 한칸 위, 같은 행, 한칸 아래에 있는 입력값들만 가

풀이 방법 : 그리디화살을 쏘고 풍선을 맞췄다면 화살의 높이가 1씩 낮아진다.만약에 높이 4인 풍선을 맞추려고 한다면, 이전에 5번 풍선을 터뜨린 화살이 있다고 한다면 해당 화살이 자동적으로 높이 4인 풍선을 맞출 것이기 때문에 화살을 다시 쏠 필요가 없다. 그렇기 때

풀이 방법 : 구현? 시뮬레이션?좌표 정보들이 주어지면, 시작 위치에서부터 각 방향으로 출발하는 경우 4가지를 다 시뮬레이션을 돌려보면 된다. 문제에서 주어진 대로 방향만 변경해주는 것만 신경쓰면 딱히 어려울게 없는 문제였다.무한히 전파될 수 잇다면 "Voyager"를

풀이 방법 : 누적 합각 행의 각 좌표까지의 누적 합을 구해놓고 반복문을 돌리면서 각 시작 지점 위치에서 1 x 1 부터 시작해서 가능한 최대 크기의 부분 행렬들의 요소들의 합들을 구해주었다.

풀이 방법 : 우선순위 큐처음에는 특정 날짜까지 얻을 수 있는 점수의 최댓값들을 갱신해나가는 DP 방식으로 풀어볼까 생각했으나, 그렇게 하려면 특정 날짜에 어떤 과제를 수행하였는지도 기록, 비교 해야하기에 복잡할 것 같았다.그래서 생각해낸게 어떤 날짜에 어떤 과제를 수

풀이 방법 : 유니온 파인드문제에서 요구하는 친구 네트워크는 친구 관계만으로 이동할 수 있는 사이라 말했다. 만약 A-B와 B-C가 친구 관계로 주어진다면, A와 C가 B를 통해서 이어져있으므로 하나의 친구 네트워크에 소속되어있다고 할 수 있다. 입력이 주어질 때마다

풀이 방법 : DP순서대로 케익 배달을 해야하는 문제로, 문제에서 고객의 위치에서 상하좌우로 인접한 곳까지만 가더라도 배달이 가능하다고 주어졌기 때문에 "고객 위치, 상, 하, 좌, 우" 5가지의 좌표를 고려해야한다.무조건 주문이 들어온대로 순서대로 배달한다고 했으므로

풀이 방법 : LIS, 이분 탐색전깃줄이 어떨 때 교차가 되는지 살펴보면 왼쪽 1에서 출발한 전깃줄이 오른쪽 3에 연결되어있고, 2에서 출발한 전깃줄이 오른쪽 2에 연결된다면 그 전깃줄은 교차될 것이다. 이를 계속 생각해보면왼쪽 숫자가 낮은 녀석의 도착지점이 왼쪽 숫자

풀이 방법 : 백트래킹각 위치에 장애물을 설치해서 설치한 장애물이 3개에 도달하면 선생의 위치에서 상하좌우 방향으로 학생의 위치에 도달가능한지 여부를 검사하면 된다.입력 최댓값이 6밖에 안되므로 무식하게 다 설치해보는 식으로 해도 충분히 통과가 된다.

풀이 방법 : 누적 합, 투 포인터두 지점을 선택해서 해당 지점들 간의 거리의 최댓값을 구하는 문제 시계방향, 반 시계 방향의 거리 둘 중에 작은 값이 거리이다.시계방향의 거리는 누적 합을 이용해 빠르게 구해줄 수 있고 반 시계방향의 거리는 모든 거리의 총 합에서 시계

풀이 방법 : 플로이드 - 워셜문제 설명을 잘 읽어보면 입력으로 주어지는 값들이 모든 쌍의 도시에 대해 최소 이동 시간들이라는 것을 알 수 있고 이 결과값들은 즉 플로이드 - 워셜 알고리즘에 의해 구해진 값과 동일한 값들이라는 것을 알 수 있다.플로이드 - 워셜 알고리

풀이 방법 : 위상 정렬 + DP건물 중에 특정 건물들이 이미 건설되어 있어야만 건설 시작이 가능하기 때문에 선행 관계에 따라 순서를 파악해야 한다. 따라서 위상정렬을 사용해야 한다.선행 건물이 있는 건물의 건설 시작을 할 수 있는 가장 최소 시간은 선행 건물들의 건설

풀이 방법 : DPVIP를 제외한 이들은 양 옆의 자리에 앉을 수 있다.왼쪽자리에 앉는 경우를 0, 제자리에 앉는 경우 1, 오른쪽 자리에 앉는 경우 2로 둔다면DPi = DPi-1 + DPi-1 //VIP라면 이 경우만 구해준다.DPi = DPi - 1 + DPi -

풀이 방법 : 이분 탐색숫자가 커서 다 검사하면 당연히 시간 초과가 뜬다.이분탐색을 통해 숫자를 하나 골라서 그 숫자보다 작은 숫자가 몇 개 있는지 찾아내면 K번째 숫자가 될 수 있는지 알 수 있을 것이다.이를 위해 한 줄씩 현재 숫자보다 작거나 같은 숫자가 몇 개인지

풀이 방법 : 다익스트라처음엔 유니온 파인드로 접근 했으나 유니온 파인드로 하면 2번 조건을 고려하지 못한다는 것을 발견하게 되었다.그래서 결국에는 슈퍼컴퓨터 즉 1번 컴퓨터에서 각 컴퓨터까지의 최단 거리를 고려하면서 구해야하므로 출발 지점에서 다른 모든 지점까지의 최

풀이 방법 : 누적 합 + 해시i - j번째까지의 부분 합이 K인 경우의 수를 구하는 문제다.1 ~ N까지 숫자들의 누적 합을 구해주는 과정에서 i번째 누적합을 구했다 치면만약 Sumi - Sumj == K 를 만족하는 Sumj 누적합이 나온 적이 있다면 부분 합이 K

풀이 방법 : 분리 집합연결을 끊거나 연결하거나, 두 가지 연산으로 트리 형태의 그래프를 만들어야 한다.입력으로 이미 연결되어 있는 뉴런이 주어진다고 했다.만약 입력으로 들어온 뉴런들을 연결하면 사이클이 발생하는 경우 이것은 연결되면 안된다.즉, 연결을 끊는 연산이 필

풀이 방법 : 슬라이딩 윈도우W 문자열에 들어있는 문자가 S에 순서에 상관없이 들어 있으면 그 단어가 될 수 있다.cAda가 들어있는지 확인하려면 dAac, Acad, cadA 등 문자의 순서와 상관없이 갯수만 일치하면 된다는 것이다. 슬라이딩 윈도우를 통해 대문자와