알고리즘

문제를 읽어보면 핵심은 다음과 같다.절단기의 높이 H로 나무들을 쭉 잘랐을때 위쪽의 남은 부분을 우리가 가져가는 것이고, 이 가져가야 하는 최소 길이는 M이다. 이때, M이상 길이를 가져가지만 가장 M과 가깝도록 만들어주는 절단기의 높이 H를 구하는 것이다. H의 높이

이 문제의 핵심은 다음과 같다. R과 D로 구성된 문자열이 주어지는데 이게 함수다. 그리고 정수배열이 주어졌을때, 이 정수배열에 함수를 따라 적절한 연산을 해주면 된다. 출력으로는 그 연산 결과를 출력해주면 된다.R은 뒤집는거고, D는 현재 남은 배열에서 가장 앞 요소

문제 자체는 이해하기 쉽다. 우리가 알고 있는 우선순위 큐의 삽입 연산은 동일하고, 삭제 연산만 양쪽 방향으로 모두 가능하게 하고 싶다는 것이다.큐를 양방향으로 두 개를 생성,각 원소가 존재해야 하는 갯수를 추적하는 해시맵 생성.삽입은 항상 두 큐 모두 같이 해주고,

D, S, L, R 이라는 네가지 연산이 존재함.초깃값 A를 B로 바꾸기위한 최소한의 연산(횟수가 아니라 일련의 스트링)을 찾는 것임. 만약 가능한 방법이 여러개면 그 중 하나를 출력.A를 B로 바꾸기 위해 dp를 적용할 수 있는지 생각해봤음, 하지만 문제를 보면 알겠

총 100개의 칸이 있으며, 각 칸마다 고유의 숫자가 순서대로 있다. 1부터 시작해서 100까지 도달해야하는데, 이때 주사위를 굴리는 최소 횟수를 구하는 것임.현재 칸에서 주사위를 굴려 1~6칸까지 이동가능하다. 이때, 이동한 칸이 사다리 혹은 뱀과 연결되어있다면 따라

mbti가 최대 10만명에 대해 주어진다. mbti의 종류는 16개다.ISTJ와 ISFJ 사이의 심리적 거리는 T와 F가 다르므로 1이다. 이때, 이 10만명 중 세 사람의 거리가 가장 작은 값을 구하라.시간 제한이 2초에 10만명 밖에 안돼서 브루트 포스로 먼저 생각

지민이가 파티 M개에 참여할거다. 가서 거짓말을 하고싶다. 파티M개를 통틀어서 참여하는 사람의 수는 N명이다.근데 이 N명 중 그 거짓말에 대한 진실을 처음부터 아는 사람들이 존재한다. 각 사람마다 M개의 파티중 여러개의 파티에 참여가능하다.진실을 아는 사람들이 있는

N개의 집이 선분 위에 순서대로 존재한다. 이 집들을 각각 빨,초,파 중 하나로 칠할건데, 이웃한 집끼리는 같은 색일 수 없다. 즉, 연속된 두 개 이상의 색상이 나올 수 없다는 말이다. 그리고 각 집마다 자신을 빨,초,파로 칠했을때의 비용이 주어진다. 이때, 모든 집

N개의 마을에 각각 사람이 한 명씩 살고 있다. 이 마을 중 한개의 마을X에서 사람들이 모이기로했다. 마을들을 잇는 도로는 총 M개이며 단방향이다. X 마을에 사는 사람을 제외하고는 모두 X마을로 갔다가 다시 자기 마을로 돌아가야한다. 이때, 왕복거리가 가장 긴 시간을

1번 노드에서 N번 노드로 이동을 해야함. 그런데, 중간에 무조건 V1->V2로 가는 길을 포함해야함. 또한, 한 번 이동했던 정점이나 간선도 다시 쓸 수 있다. 이때의 최단 거리는? 노드의 갯수 N은 최대 800개, 간선의 갯수 E는 최대 20만개, (단, v1 !=

A, B, C 가 주어진다. A를 B번 곱한 것을 C로 나눈 나머지를 구하라.A, B, C는 21억 이하의 자연수이며, 시간제한은 0.5초다.일다 보자마자 모듈로 연산의 분배법칙이 떠올랐다.하지만, 이걸 B번 반복하는것은 21억번이라서 너무컸고, 묶음단위로 A를 여러개

방향그래프가 주어진다. 시작점이 주어진다. 여기서 모든 다른 그래프로의 최단경로 거리를 찾아서 출력해라.단, 정점 간 여러개의 간선이 존재할 수 있다.다익스트라다. 처음에는 정점 간 여러개 간선이 존재할 수 있다는 것 때문에, ArrayList<Node>\[]로

N개의 노드가 있고, M개의 무방향 간선이 있다. 추가로 W개의 방향성 음수간선(문제에선 이걸 웜홀이라고 함)이 존재한다. 이때, 임의의 한 점에서 출발해서 순회하고 다시 돌아왔더니 오히려 시간이 뒤로 가는 경우가 있는가?거치는 간선의 가중치 합 < 거치는 간선에

숫자 N에 대해서, N층부터 1층까지 존재하며 층을 내려갈때마다 숫자가 한개씩 증가하는 삼각형 구조를 이루고 있다.이때, 꼭대기층부터 1층까지 숫자를 하나씩 선택하며 내려왔을때 합의 최댓값은?단, i층에서 i-1층으로 내려갈때, 자신과 이웃한 두 개의 자식으로만 내려갈

후위표기식 백준 문제를 푸는데, 스택으로 하는건 학교에서 배운게 기억이 나는데 너무 가물가물했다. 이건 너무 유형적인 문제라고 생각해서 20분 고민하고 그냥 답지를 보기로 했다. 나중에 시험에서 어떤게 나올지 모르니, 스택을 언제 어떤 상황에 적용해야하는지에 대한 이유

요즘 알고리즘 공부가 너무 뜸했던 이유...주 5일 한달반 토익 학원을 다니고 있습니다ㅠㅠ 요즘 영어 실력이 늘어서 가끔 미디엄 글 시간날때 읽으면 잘 읽히는건 좋은데,, 절대적으로 시간이 부족해서 미디엄을 잘 못읽고 다른 분야 공부를 아예 못하고 있는게 좀 아쉽다(토

R행 C열 보드가 있음. 여기서 각 칸마다 알파벳이 하나 적혀있음. 현재 위치에서 상하좌우로 이동 가능.한 번 지난 적 있는 알파벳은 다시 지나면 안됨. 보드 내 좌상단에서 시작해서 이동할 수 있는 최대 횟수는?처음에는 최소인줄 알고 bfs로 풀려했으나 문제를 다시보니

트리를 주면, 그 트리에 대한 전위, 중위, 후위 순회를 순차적으로 하고 각 결과를 출력하면 된다.아... 너무 오랜만에 본다. 분명 학교 알고리즘 시간에 배운건 기억이 나는데 아리송해서 그냥 개념 정리할겸 유튜브에 있는 5분짜리 영상을 하나봤다.우선, 기본적인 이진트

N개의 층이 주어진다. 각 층마다 3개의 숫자가 나열되어있다. 각 숫자는 0~9 사이다.이때, 꼭대기 층부터 시작해서 아래층까지 내려올건데, 아래층으로 내려갈때는 현재 위치의 바로 아래 숫자 혹은 그와 이웃한 숫자들로만 이동가능하다. 아래 사진을 참고하자.이런 방식으로

N \* M 행렬에서 0은 이동할 수 있고, 1은 이동할 수 없는 벽이다.최단 경로로 (1,1)에서 (N,M)으로 가는 경로 길이를 구해라. 단, 필요하다면 벽을 딱 한 번 부술 수 있다.시간 2초, 공간 192MBBFS를 오랜만에 풀어서 최단 경로를 구해야 한다는 점

N으로 3\*2^K (0 <= k <= 10)인 수가 들어온다.이때, 다음과 같은 패턴을 만족하도록 출력해라. 아래 예시는 N이 24인 경우다.처음엔 재귀로 하려했으나, 재귀로 하면 중간 중간에 DP로 저장하지 않는한, 반복적인 탐색이 존재해서 비효율적이라고

외부에 두 변이상이 노출된 치즈가 한시간마다 사라진다.총 사라지는 시간은?얼핏보면 쉬우나 고민할것은 치즈들에 둘러쌓인 치즈가없는 공간은 외부로 취급하지 않는다는 것.때문에 외부,외부는 아니지만 치즈가 없는 칸, 치즈가있는 칸을 구별해야한다.난 외부를 2, 외부는 아니지

숫자 스트링과 지울 숫자갯수의 정보가 주어진다. 그러면, 이 숫자 스트링에서 지워야 하는 갯수만큼 지웠을때 가장 큰 수가 나오는 경우를 찾아라.내가 접근한 방법은 다음과 같다. 1\. 지워야 하는 갯수 + 1을 윈도우로 삼는다.2\. 주어진 문자열에서 해당 윈도우 내

일단 정렬시키고, 가벼운 사람부터 난 기준을 삼았다. 가벼운 사람은 가장 무거운 사람부터 시작해서 자기가 함께 탈 수 있는 무거운 사람들과 순차적으로 보트를 태워보낸다.이때, 무게에 대한 정보와 각 무게별 남은 인원의 정보는 별도로 관리했다.이로인해, 정렬 시간 및 탐

5-3+1+2-4 같은 문자열 배열이 주어지면, 이 연산의 최댓값 구하기, 단 연산은 +와 -밖에 없다.처음에 dp로 접근은 했으나, -의 소비 개수를 따라 선형적으로 한 번만 읽고 지나가며 구하려고 했다. 하지만, 구현이 쉽지 않았고 생각보다 중복을 많이 제거 못한다

수직선 위에 각 자동차들이 존재하는 시작점과 끝점이 배열로 주어진다.모든 자동차들이 최소한 한 번씩 지나갈 수 있도록 수직선 위에 단속카메라를 세운다고 생각해보자.이떄, 최소 몇개를 세워야 하는가?우선, A라는 자동차가 끝나면 그 뒤에 아무리 카메라를 설치해도 의미없는

1번 마을에서 K 시간 내에 배달 가능한 마을의 갯수 찾기전형적인 다익스트라 문제. 시간을 줄이기 위해 선형탐색 대신 우선순위큐를 적용했고, 인접행렬 대신 인접리스트를 적용해서 시간 최적화를 시켰다.PriorityQueue같은 제네릭 구조에다가 Comparator 를

문제는 DFS/BFS 유형으로 분류되어 있으나, 문제를 읽다보니 그래프로 표현해서 다익스트라를 적용 후 begin->target까지의 경로가 존재하는지로도 해결할 수 있을 것 같아서 두 가지 방법으로 모두 풀어보았다.풀리긴했으나 역시 속도가 더 느리다. 그래도 이런 다

문제 설명 수평선이 주어진다. 시작 출발 위치는 0이고, 도착지점은 distance로 주어진다. 그리고 이

문제 접근 시간제한이 2초였고 메모리도 512로 매우 널널했다. N의 크기도 최대 20이였기에 칸은 고작해야 400칸이다. 현재 위치에서 매번 BFS를 돌려서, 이동 경로가 가장 가까운 먹을 수 있는 물고기가 있는 곳으로 펭귄을 이동시키면 된다. 하지만, 여기서 처음에

세로선의 갯수 N과 가로점선의 갯수 H가 주어진다.그리고 이미 놓여진 사다리의 갯수 M도 주어진다.이때, 최대 3개의 사다리를 더 배치해서, 모든 i에 따라 i세로선이 사다리게임을 따라 i세로선에 도착할 수 있는 경우에 그 최소로 더 놔야하는 사다리의 갯수를 구해라.

https://www.acmicpc.net/problem/9935LCS 알고리즘과 비슷한 느낌으로 현재까지의 문자가 패턴문자열의 몇번째 인덱스까지 일치했는지를 기억하면 된다고 생각했다(이게 가능한 이유는 패턴 내에 동일 문자가 존재하지 않는다는 조건이 주어져서

https://www.acmicpc.net/problem/15685N도 20이하라고 주어졌고, 판도 100\*100 이라서 어떻게 해도 시간초과가 날 수 없는 구조였다. 그러나, 구현하기가 너무 어려워보이는 문제였다. 주기적으로 간선들을 회전시켜서 새로 배치된

문제 접근 원소들의 합이 n인 중복 집합들 중에서 곱이 최대가 되기 위해서는, 집합 내 숫자들 간의 표준편차가 가장 적어야 한다는 것을 의미한다. > 이게 살짝 헷갈린다면, 미적분에서도 극대값과 극솟값은 항상 값들이 고르게 분포되어있거나, 특수한 상황이라는 것을 잘 떠

https://school.programmers.co.kr/learn/courses/30/lessons/12979이미 배치된 기지국의 좌표들을 순차적으로 접근한다.해당 기지국의 바로 앞쪽에서 아직 설치되지 않은 연속적인 구간들을 대상으로 순회를 돌며, 최적의

https://school.programmers.co.kr/learn/courses/30/lessons/12971스티커를 떼면, 좌우 스티커를 더이상 먹지 못함.이걸 고려하면, 크게 두가지 경우로 나눌 수 있음.1\. 0번을 먹은 경우 -> 1번을 먹지 못함2

우선, 아래 코드는 정확성테스트는 모두 통과했지만, 효율성이 모두 틀렸다. 다만, 시간복잡도가 얼추(여기서 얼추인 이유는 해시테이블을 사용해서임) 계산했을때 N=최대20만인 상황에서, O(NlogN)이므로 실패할 이유가 없어보였다.이 문제의 시간 복잡도가 타이트한 것으

https://school.programmers.co.kr/learn/courses/30/lessons/42861문제를 읽자마자 최소신장트리를 구하라는 것을 이론적으로는 알았다. 그래서 프림과 크루스칼 중 구현이 쉬운걸로 기억하는 크루스칼을 선택했다.그래서 코

이 문제는 그냥 문자열을 어떻게 끊어서 빠른시간안에 문제를 해결할거냐가 관건이였던 것 같다. 시험때 만나면쉬운데 시간 잡아먹을 것 같은 문제였다.숫자는 최대 500개이므로 어차피 N^2으로 답을 구해도 충분하다.그러므로 그냥 잘 끊어읽어서 집합 사이즈별로 구분만 잘하면

https://school.programmers.co.kr/learn/courses/30/lessons/118667두 큐의 크기가 같다는 것과 큐의 특징을 이해하면 사실 이 문제는 투포인터의 부분합이 매칭되는 경우를 찾는 것과 동일한 문제가 된다. 우선, 두

일단 k진수로 바꾸는 과정을 거쳐야 하는데, k진수로 바꾸는건 스택 써서 k씩 나눈 나머지를 계속 추가하고, 스택에서 다시 꺼내서 순서대로 읽으면 된다. 문제에서 원하는건 그냥 0이 나오기 전까지의 연속된숫자들을 십진수로 바라보고 소수판별하라는 것임.이때, 소수 판별시

저번에 풀었던 스티커 모으기(2)와 비슷한 유형의 문제였다.

문제를 보고 어디선가 본 문제 같았고 dp라는 것은 생각보다 쉽게 떠올릴 수 있었다. 처음에는 dpi = dpi-1 + dpi-2 + dpi-3 의 점화식에서 중복된 값들만 제거하면 될거라고 생각했다. 그런데, 생각보다 중복된 값을 제거하는 규칙이 찾아지지 않았다. 여

문제는 매우 심플하게 투 포인터다. 투 포인터로 한칸씩 슬라이드 해가면서, 중복을 제거한 가짓수를 카운트해주면 된다.

https://www.acmicpc.net/problem/13549문제를 읽어보면, 현재 위치에서 좌우로 한칸 이동하는데 1의 시간이 걸리고, \*2의 위치로 순간이동하는데 시간이 소모되지 않는다. 시작점 N이 주어지고, 도착 목적지 K가 주어진다.선분 혹은

이 문제의 핵심은 어떻게 가장 빠르게 두 집합 간 교집합의 갯수와 합집합의 갯수를 구하느냐이다.이 문제에는 조건이 있다. 집합 안의 원소들은 모두 길이가 2인 영어로만 구성된 문자열이라는 것이다.또한, 문자열 간 비교시 대소문자 관계를 신경 쓰지 않는다고 했다.따라서,

n,t,m,p 가 순차적으로 매개변수로 주어진다.각 매개변수의 의미는 다음과 같다.n은 이번 문제의 n진수t는 미리 구할 갯수m은 총 참여 인원수p는 튜브(주인공)의 차례 순서위 정보들을 토대로, 튜브가 외쳐야할 숫자들을 t개 미리 구하면 된다.잘 생각해보면, 그냥 숫

진짜 진짜 문제 해석이 너무 어려운 문제였다.글의 모든 부분을 잘 읽어야 풀 수 있다.올리는 위치와 내리는 위치라는 것은 벨트 위에 올라간 로봇이 벨트 위에 새롭게 올라가거나 아예 내려가게 되는 위치를 말하는 것임. 또한,위의 빨간 줄 '언제든지 로봇이 내리는 위치에

문제 접근 주어진 조건을 만족하는 연속된 문자열에 대한 모든 탐색이 필요하다. 이런 경우는 전형적인 투포인터 문제다. 우리가 구해야하는 것은 임의의 문자를 K개 포함하고 있는 연속된 구간의 최소 길이 임의의 문자를 K개 포함하고 있는 연속된 구간의 최대 길이(단, 이때

처음에는, 이분 그래프 탐색 알고리즘을 몰라서 문제를 읽고 이분 그래프가 되기 위한 조건은 사이클이 없으면 된다고 생각했다. 물론 사이클이 없는 그래프인 트리가 이분 그래프를 만족하는 것은 사실(트리의 레벨끼리 서로 다른 그룹에 넣으면 됨)이나, 트리가 아니여도 이분

티켓들이 주어진다. 각 티켓은 시작 지점과 도착지점에 대한 정보가 있다.우리의 여행 출발 도시는 "ICN" 이다. ICN 부터 시작해서 사전 글자 순서대로 방문해야한다. 한 번 지난 도시를 다시 지날 수 있으며, 모든 티켓을 소모해야한다. 즉, 이 문제는 인접리스트를

처음에 문제를 이해하는데 매우 오랜시간이 걸림. 예시에서 왜 4 2 입력이 18출력인지를 이해못했다.문제를 잘 읽자....난 처음에 나보다 절댓값으로 K이하로 차이나는 수 뒤에만 올 수 있는 줄 알았다.알고보니, 내 앞 수가 나보다 크면 상관없고 작다면 K 차이까지만

문제를 읽어보면, 시작 위치부터 도착지점까지 이동할 수 있는 정해진 경로 중 가장 짧은 거리를 구하는 것이다.\-> 이것만 봐도 일단 bfs라는 것은 알 수 있다.하지만, 이 문제의 진짜 문제는 정해진 경로를 구하는 것이다.정해진 경로란, 이 문제에서 사각형들을 좌표위

문제에서 N을 8 보다 많이 조합하지 말라고 나와있다. 즉, 생각보다 한계가 적은 문제다.N이 1개인 경우 -> NN이 2개인 경우 -> NN, N+N, N-N, NxN, N/NN이 3개인 경우 -> NNN, NN+N, NN-N, N-NN, NNxN, NN/N, N/N

아주 전형적인 쉬운 dp 유형이다.문제에서 원하는 조건대로 경우의 수를 트리 구조로 만들어 나가다 보면, 중복 연산 지점이 발생한다. 보통 쉬운 dp들은 뒤에서부터 dfs를 시작해서 한 칸씩 앞으로 재귀적으로 댕겨나가면서 구해나가는 방식이다. 물론 역으로 해도 되지만

노드들끼리 연결된 하나의 네트워크를 컴포넌트라고 부른다.밀도는 다음과 같이 정의한다. 컴포넌트에 속한 회선 갯수 / 컴포넌트에 속한 노드수이 문제의 그래프는 양방향 간선이다. 즉, 무방향으로 줌.우리가 출력해야 하는 것은 밀도가 가장 큰 네트워크에 속한 노드들에 대한

시작 정점부터 나머지 모든 정점까지의 최단 거리를 구하는 알고리즘.음의 간선 허용하지 않음. 음 순환 못잡음.그리디의 성격 알고리즘임. 즉, 매번 방문한 노드를 기준으로 인접한 노드들을 살펴보며, 현재 방문 노드가 가진 시작정점부터 방문노드까지의 최단경로 + 방문노드에

다익스트라와 목적은 같다. 한 시작 정점에서 다른 모든 노드까지의 최단 경로 거리를 구하는 것.하지만, 다익스트라는 음의 간선이 있으면 정상작동하지 않는다.벨만포드는 음의 간선까지는 허용한다. 하지만, 벨만포드도 음의 순환이 존재하는 그래프에 대해서는 정상 작동 하지

우선, 이 글은 제가 나중에 다시 보기 위해 작성한 것이라서 그렇게 읽기 편하지 않으실 수 있습니다. 나중에 다시 기회가 되면 정리하겠습니다.... 현대 소프티어 코테 중 비트 연산자를 써야 쉽게 풀리는 문제가 나왔다. C언어 말고 자바에서는 처음 써봐서 여기에 정리한

단순히 말해서, 타워를 기준으로 왼쪽에 있는 타워들 중 가장 먼저 해당 타워와 높이가 같거나 더 큰 타워를 찾으면 되는 문제다.N이 50만 이였고, 시간제한은 1.5초였다. 즉, NlogN 문제였고, 나는 PriorityQueue를 사용해서 해결했다.우선, 뒤에 타워부

구간들을 구해서 그 구간 사이에 찰 수 있는 물의 양을 구하고, 이걸 반복해서 모두 더하는 문제다.그렇다면, 구간의 정의를 어떻게 내릴 수 있을까?구간의 시작 지점 높이를 sH라고 잡자.그리고, sH 이상의 높이를 갖는 블록(이 블록의 높이를 eH라고 해보자)이 등장하

결국 이 문제의 핵심은, 해당 유저의 id를 기반으로, 유저의 최종 닉네임이 무엇이었냐?를 구해야 한다.유저의 최대 수는 10만이고, Map 자료구조를 사용했다. 유저가 들어오거나, 닉넴 변경시마다 맵 자료구조에 해당 유저의 최종 닉네임을 기억한다. 이후, 다시 rec

블록들 중 2\*2 사각형이 같은 모양이라면, 다음 턴에 제거하고, 그 위에 있는 블록들을 그대로 아래로 떨어트리는 시뮬레이션 문제임.시뮬레이션 문제 특징 답게 n,m이 최대 30으로 매우 작은 범위로 주어짐.떨어트리는 문제이기 때문에, 문제의 구조를 다른 관점으로 바

다음과 같은 절차를 따라 진행하면 풀리는 단순 구현문제다.각 사람의 주문 별로 세트메뉴 종류들을 조합으로 반환해줄 수 있는 함수를 만든다. 세트메뉴 사이즈 별로 해당 세트메뉴가 몇번 나왔는지 기억할 Map을 만든다.이 함수를 사용해서, 사람들이 주문한 메뉴들에 대해 조

각 노래들이 라디오에서 얼마나 방송됐는지 시간을 정수로 변환한다.네오가 들었던 멜로디를 - 각 노래들을 - 노래의 시작 음과 같은 음을 노래 음에서 찾으면, 그 음부터 시작해서 모듈로 연산을 통해, 네오가 들었던 멜로디가 끝날때까지 같은지 비교한다. 같은걸 찾았다면,

문제에서 나와있는 조건을 따라 그대로 구현하면 된다. 여기서, u는 더이상 쪼갤 수 없는 '균형잡힌 괄호 문자열' 이라고 나와있다. 이 말은 문자열을 앞에서부터 하나하나 읽으면서 최초로 (와 )의 갯수가 같아지는 지점까지를 u로 잡으라는 것과 같다. 이 부분만 빠르게

브루트포스로 모든 경우를 다 고려해보고 최소길이를 구하면 되는 문제다.어차피 문자열의 길이는 1000자이고, 압축단위를 키워갈수록 그만큼 순회하는 횟수도 비례해서 줄어들게 된다. 다만, 이 문제에 가지치기를 적용해서 개선하고 싶었으나, StringBuilder를 쓰고

문제에 대한 이해가 어렵지는 않으나, 구현하기 까다로운 유형이였다. 우선 시간을 순서대로 정렬하고, 버스시간과 비교해야한다. 또 시간을 HH:MM 형식의 스트링으로 변환도 해야하기에 굉장히 구현할게 많은 문제라고 느꼈다.

문제는 간단하다. 그냥 유일성과 최소성을 만족하는 모든 후보키를 구하면 된다. 컬럼의 최대 개수는 8개, 튜플의 최대개수는 20개로 그냥 구현문제다.다만, 여기서 최근에 사용하고 싶었지만 적당한 문제를 못찾아 적용을 못하고 있던 비트마스킹을 사용할 기회를 봤다.속성이

주인공이 1 노드에 있고, 도착지인 N 노드까지 가야하는데, 이 길 위에 소들이 C마리씩 있다. C는 최대 1000이하다. 노드는 N개고 간선은 M개다. 또한 N과 M 모두 최대 5만개다. 그리고 지나는 모든 소들에게 여물을 한개 씩 줘야 한다.이 때 도착지까지 최소

시간 제한은 1초다. 그런데, N은 갯수는 10만개다. 즉, 브루트 포스로는 안된다. 그렇다면 가장 적합한 방법은 NlogN이다. 그러면 우리는 문제의 본질을 이해하고 이 안에서 NlogN으로 해결할 수 있는 알고리즘을 떠올려야 한다. 음수 중 0에 가장 가까운 두 개

처음에는 최종상태만 오목처럼 체크하는건줄 알고 구현했다가 틀렸다. 문제를 다시 읽어보니,최종상태까지 도달할 수 있는지 등 여부를 모두 파악해야 하는 문제였고, 문제에서 놓을 수 있는 X돌은 최대 5개, O돌은 최대 4개로. 결국은 브루트포스로 모든 경우를 파악하면서 가

전형적인 백트래킹 문제로, 학교 알고리즘 시간에 배운게 기억나는 문제였다. 이 문제는 결국 모든 행에 하나씩 배치를 해봐야해서 만약 행개수가 n이라면, n^n을 모두 확인해봐야 한다. 하지만, 문제에서 n은 최대 14이고, 시간 복잡도는 10초라고 했다. 따라서 10억

낼 수 있는 돌은 1,3,4 밖에없다는 것을 생각하고, 항상 턴은 상근이부터 시작한다는 것에 초점을 맞추자.N이 1인 경우 -> 승자: 상근, 케이스: 1N이 2인 경우 -> 승자: 창영, 케이스: 1 1N이 3인 경우 -> 승자: 상근, 케이스: 3N이 4인 경우 -

행렬 A를 B번 거듭제곱한 결과의 각 원소를 1000으로 나눈 나머지를 원소로 갖는 행렬을 출력하는 문제다.우선, 이 문제를 보고 가장 먼저 떠올려야 하는것은 행렬의 곱셈에 결합법칙이 성립하는가를 알아야 한다. 또한, 어떻게 해야 결합법칙을 활용해서 최대한 중복 행렬이

우선, 문제를 읽어보면, 학생은 자신의 키보다 큰 사람이 Ki명 이하힌 그룹에만 들어갈 수 있다. 문제를 해석해보자. 즉, 자기 입장에서 나보다 큰 사람들이 이전에 모두 그룹에 배치되어있는 상황이라면, 나는 그냥 내가 들어갈 수 있는 그룹 중에서 가장 사람이 많이 차있

피보나치 수 6 문제를 풀면서 새로운 개념을 알게 되었다.이 문제는 개념을 알아야 풀 수 있는 것 같다. 그래도 블로그 글을 읽을 때 이해는 되니...그걸로 만족하자.F2 = F1+F0같은 관계가 지속되는 수열들을 말한다.그러므로, Fn+2 = Fn+1 + Fn 이다.

기본적으로 N이 16이하이기 때문에 굳이 dp를 적용하지 않고 브루트포스로 풀어도 된다.하지만, 어차피 연습하는 것이고 공부하는 것이니 더 좋은 방법인 dp로 풀어보려고 했다.실제로 시간 차이가 거의 2.5배 정도 났다.우선, dp로 풀고 싶다면 파이프의 끝이 위치한

사실 그냥 구현 시뮬레이션 문제라서 별다른 접근법은 없다.하지만, 주의해야할 점이 있다. 필자는 여기서 많이 틀렸다..바로, 공기청정기가 바람을 쏜 위치의 시작 지점의 값을 0으로 초기화 해야 한다는 것이다.그리고, 공기청정기가 있는 위치는 항상 -1이라는 것을 기억하

우선, 처음에는 bfs인줄 알았다. 하지만, 10퍼쯤 틀렸다고 나오고 반례를 찾아보았다. bfs는 그냥 거리에 상관없이 이웃한 노드를 먼저 접근하는 알고리즘이다. 따라서, 단순한 bfs로 구하면 안된다....거리 제약 조건이 붙어있는 경우는 단순 bfs말고, 다익스트라

문제를 읽어보고 처음엔 어렵게 느껴졌다. 하지만, N의 크기(문자열 길이)와 시간복잡도(2초)를 보고 N^2에도 풀릴 것이라 생각했고, 이때부터 사고가 좀 유연하게 그냥 브루트 포스로 접근하자고 생각하니 쉽게 풀렸다.결국 a문자열은 쭉 이어져야 한다. 그렇다면 a문자의

표현할 수 있는 자릿수는 최대 6개임. 그래서 표현가능한 수도 최대 100만이라고 조건에 나옴. 10^K이므로.우리는 시작 숫자 X를 알고 있음. 그렇다면 그냥 100만개의 수를 자릿수만큼 다 비교해봐도 최대 600만번 비교임. 1초안에 해결 너무 널널함.이를 위해,

일단 빌딩은 50개 밖에 없다.... 브루트 포스다. 그런데 어떻게 해야 효율적으로 접근할 수 있을까? 기준 i위치 빌딩에 대해, 그 좌측에 있는 빌딩 j와의 기울기를 다음과 같이 정의하자. ( 단, 0<=j<i )double degree = (double)

문제를 잘 생각해보자. 만약 방법의 가짓수를 구하지 말라고 했다면? 그냥 일반적인 BFS로 끝났을 것이다.하지만, 이 문제는 방법의 가짓수를 구해야한다.이게 좀 골치아파질 수 있으나, 잘 생각해보자... a라는 위치에 도달하는 가장 빠른 시간은 정해져있다. 그냥 N부터

사실 일반적인 다익스트라와 다를게 없지만 s->e 로 갈 때 최소 경로를 구해야 한다는 점, 그리고 n1->n2로 이동하는 버스가 여러대일 수 있다는 점이 다르다.사실 우리는 최소 경로를 구하는 것이므로, n1->n2로 가는 경로 중 최소 경로만 고려해서 다익스트라를