PS

백준 1041번: 주사위 아이디어 주사위 전개도 모양이 다음과 같을 때 마주보는 면은 AF, BE, CD이다. A~F를 0~5로 대응시킨 후 마주보는 면이 없는 조합을 만든다. 마주보는 면이 동시에 보이는 일은 없기 때문. 만든 조합으로 합이 가장 작은 경우를

백준 1092번: 배 크레인의 무게 제한보다 무거운 박스는 옮길 수 없다. 한번에 최대한 많은 박스를 옮기려면, 가장 성능이 좋은 크레인이 가장 무거운 박스를 옮겨야 한다.즉, 각 단계에서 가장 최선의 선택을 하는 그리디 알고리즘 문제이다.같은 코드임에도 불구하고 P

백준 9095번: 1, 2, 3 더하기모든 경우의 수를 탐색해야 한다. 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 세가지 경우 다 다른 경우이다. 0부터 더해나가며 확인하는것이 아닌, N부터 빼나가는 방법을 사용했다. 정수 N을 1, 2, 3의 합으로 나

백준 1149번: RGB거리i번째 집을 R, G, B로 칠하는 경우, i-1번째 집까지 최소의 비용으로 칠하는 방법은 정해져있다. 이를 배열에 기록하고 다음 계산때 활용해야 한다.입력이 다음과 같다고 하자.이때 1번째 집을 R로 칠하려면, 0번째 집이 G와 B로 칠해진

백준 1260번: DFS와 BFSDFS는 재귀함수로, BFS는 파이썬 collections의 deque로 구현했다. 인터넷 검색 한번도 안하고 구현해서 기분이 상당히 좋다.

백준 1697번: 숨바꼭질BFS(너비 우선 탐색)으로 현재 위치에서 -1, +1 \*2 되는 경우를 탐색한다. 배열에 있는 숫자를 1씩 더해서 해당 위치까지 가는데 걸린 시간을 기록한다.

백준 1992번: 쿼드트리이미지를 4등분한다. 이미지 사이즈가 1인경우 출력한다. 4등분한 이미지가 각각 0 혹은 1로만 이루어져있으면서 네 이미지 모두 같은 경우 출력한다. 그 외의 경우 여는괄호를 출력하고 함수를 재귀호출하고, 닫는괄호를 출력한다. 4등분한 이미지가

백준 2630번: 색종이 만들기종이를 4조각내고 자른 조각이 전부 같은 색으로 이루어져 있으면 count, 다르면 같아질 때까지 혹은 1칸이 될 때까지 자른다. 사실 어제 쓴 코드가 아까워서 재탕했다.

백준 11047번: 동전 0가장 비싼 동전부터 사용하면 동전을 최소한으로 사용할 수 있다. 사실 이게 가능한 이유는 각 동전의 금액이 서로 배수 관계이기 때문이다. 예를 들어, 1원, 7원, 18원짜리 동전으로 21원을 만드는 경우, 가장 비싼 동전인 18원짜리 동전을

백준 11399번: ATM각 사람마다 돈을 인출하는데 걸리는 시간은 정해져 있다. 기다리는 시간을 최소로 해야 각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 된다. 기다리는 시간을 최소로 하려면 돈을 인출하는데 걸리는 시간이 짧은 사람부터 돈을 인출해야 한다.

백준 2606번: 바이러스그냥 그래프 탐색하면서 몇개나 연결됐는지 세면 된다.한국정보올림피아드시․도지역본선 > 지역본선 2004 > 초등부 3번 문제라고 한다. 난 초등학생이다.

백준 2293번: 동전 1동전 a, b, c 를 가지고 K원을 만든다고 하자. 동전 a만 사용해서 1원부터 K원까지 만드는 경우를 배열에 기록한다(가능하면 1, 불가능하면 0으로 채워질 것). 이후 동전 a와 b 둘 다 사용해서 1원부터 K원까지 만드는 경우를 배열에

백준 1912번: 연속합배열의 첫 번째 원소부터 합을 기록한다. 그 합이 음수가 되는 순간 그 다음 원소는 음수에다가 더하지 않고 다시 처음부터 합을 기록한다. 계속 더해 나가는 것보다 시작점을 바꾸는 것이 이득이기 때문이다. 이렇게 기록된 합중에 가장 큰 값이 정답이

백준 11053번: 가장 긴 증가하는 부분 수열 아이디어 arr[i]가 가질 수 있는 최대의 길이를 d[i]에 기록해 나간다. 첫 번째 인덱스부터 i-1번째 인덱스까지 탐색하며 가장 길이가 길면서 arr[i]보다 작은 값을 가지는 원소를 찾는다. 코드

백준 12015번: 가장 긴 증가하는 부분 수열 2앞에서 풀어본 백준 11053번: 가장 긴 증가하는 부분 수열에서는 원소 하나의 길이를 결정할 때마다 앞에 있는 모든 값을 탐색해야만 했다. 따라서 시간복잡도는 O(N^2)인데 이러한 방법으로는 입력의 크기가 1,000

백준 1018번: 체스판 다시 칠하기\\체스판은 8 X 8 = 64칸이고 N, M의 최댓값은 50이다. 한 칸씩 조건에 맞나 확인해봐도 시간 제한에 걸리지 않을 것이다. 8 X 8로 자른 조각의 가장 첫 번째 칸을 변수에 저장해놓고 각 행, 열마다 조건을 달리하여 확인

백준 10989번: 수 정렬하기 3입력의 개수가 천만개다. 그냥 sort()하려고 하면 메모리 초과가 난다. 하지만 숫자의 최댓값이 10000이다. 이것을 잘 이용해보자.10001개짜리 배열을 만들고, 0으로 꽉 채운다. a라는 숫자가 입력됐을 때, a번째 인덱스에 위

백준 18870번: 좌표 압축좌표중 가장 작은 숫자부터 순서대로 압축된 좌표를 할당한다. 가장 작은 값을 가지는 좌표는 0으로, 그 다음은 1...이렇게 하려면 우선 입력받은 좌표를 정렬하고, 중복을 제거하고, 좌표를 압축해야 한다.좌표 정렬 - sort()를 사용하면

백준 11279번: 최대 힙파이썬 heapq 모듈은 이진 트리 기반의 최소 힙 자료구조를 제공한다. 가장 작은 값이 항상 트리의 루트에 위치한다. 최대 힙 자료구조는 제공하지 않기 때문에 잡기술을 사용해서 최대 힙으로 만들어야 한다. 어떤 잡기술이냐면.. push할 때

백준 1764번: 듣보잡list에 집어넣고 하나하나 비교하면 O(N^2)로 시간 안에 해결할 수 없다.hash set는 탐색에 걸리는 시간이 O(1)이기 때문에 시간 안에 해결할 수 있다.파이썬에서는 set 자료구조를 제공한다. 파이썬 set의 교집합 method(in

백준 11724번: 연결 요소의 개수이미 방문한 노드를 dfs, bfs 함수의 인자로 집어넣으면 False를 반환하고, 방문하지 않은 노드를 함수의 인자로 집어넣으면 True를 반환하게 하였다. 이중 True를 반환하는 경우의 수를 모두 더하면 연결 요소의 개수이다.

백준 11726번: 2xn 타일링n번째까지 타일로 채우는 방법의 수는 n-2번째까지 타일로 채우는 방법의 수 + n-1번째까지 타일로 채우는 방법의 수이다. 그림을 통해 알아보자.n-1번까지 채워진 상태에 2x1 타일 한개를 붙이는 경우와 n-2번까지 채워진 상태에 1

백준 2579번: 계단 오르기계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있다. 이 문제의 까다로운 조건인 "계단 세 개를 연속해서 밟을 수 없다, 마지막 계단은 무조건 밟아야 한다" 를 만족시키려면 어떻게 해야 할까?dp테이블에 해당하는 계단을 밟는 경우 그 이

[백준 7576번: 토마토](https://www.acmicpc.net/problem/7576) ## 아이디어 전형적인 BFS 문제다. 맨 처음 시작할 때 익은 토마토가 위치한 지점들을 deque에 넣고, 상하좌우 한 칸씩 탐색하며 익지 않은 토마토가 있는 경우 익히

백준 1012번: 유기농 배추그래프의 연결 요소 개수를 세면 된다. 배추가 위치한 좌표를 dfs 함수에 넣었을 때 True를 반환하면 처음 방문한 배추이고 False를 반환하면 이전에 방문한 적이 있는 배추이다. True를 반환하는 횟수가 정답이다. BFS로도 풀 수

백준 1074번: Z시간제한 단 0.5초, N이 15일 때 배열 사이즈 약 10억개. 그냥 탐색해서는 풀 수 없다. 입력받은 r, c를 기준으로, 함수에 어떤 arguments를 넣을지 결정한다. row, col이 현재 탐색중인 위치이다. 전체 배열을 4등분하여 r,

백준 15649번: N과 M(1)백준 15650번: N과 M(2)백준 15651번: N과 M(3)백준 15652번: N과 M(4)백준 15654번: N과 M(5)백준 15655번: N과 M(6)백준 15656번: N과 M(7)백준 15657번: N과 M(8)백준 156

백준 9663번: N-Queen백트래킹 문제다. "서로 공격할 수 없도록" 퀸을 배치해야 한다. 어떤 경우에 서로 공격할 수 있을까?같은 행, 같은 열에 위치할 때.대각선 방향에 위치할 때.1번 조건은 걸러내기 매우 쉽다. 그냥 같은 행, 같은 열 슥~ 하고 탐색해서

빼기 기호가 처음으로 나온 다음부터는 그 다음 기호가 더하기든 빼기든 상관 없이 모든 수를 빼주면 된다. - 이후 다시 -가 나오기 전까지 나오는 +에 괄호를 쳐 주면 모두 뺄 수 있기 때문이다. 처음 입력받은 문자열에 공백 문자를 더해주는 이유는 다음 문자가 숫자가

백준 2178번: 미로 탐색기본적인 bfs 문제다. 한 칸 이동할 때마다 값을 1씩 증가시켜서 총 몇 칸 이동했는지 센다. 어떻게 하면 입력받는 코드를 한 줄로 만들 수 있을까 고민하다이런 길쭉한 코드가 나왔다. input받은 문자열을 list로 만들고, map으로 하

백준 10026번: 적록색약bfs. 근처에 같은 색이 존재하면 큐에 넣고 탐색. 적색 녹색을 구분하지 않게 하기 위해 R을 전부 G로 변경하고 다시 탐색했다.맨날 너무 쉬운것만 골라푸는듯.

백준 1107번: 리모컨채널 0번부터 100만번까지 스르륵 돌면서 내가 숫자 눌러서 갈 수 있는 채널중에 가야하는 채널에 가장 가까운 채널을 찾는다. 그리고 100부터 +-버튼 눌러서 가는거랑 비교해서 출력.EOFError는 고장난 버튼이 한개도 없는데 입력을 받으려고

백준 16953번: A → B A에서 B로 올리는게 아니라 B에서 A로 내려간다. B의 마지막 숫자가 1이면 무조건 지운다. B가 2로 나누어 떨어지면 무조건 나눈다. 둘 다 안되면 불가능! 연산 한 번 할때마다 카운트 증가. 3달전에 이상하게 풀었다.

백준 11725번: 트리의 부모 찾기DFS로 루트 노드인 1번부터 탐색한다. 입력시 부모-자식 순서가 아니라는것에 주의하자. 처음에 바보처럼 풀었다노드 하나당 함수를 한 번씩 실행시켜서 계속 시간초과가 났다. 노드 하나의 부모 노드를 찾는 문제가 아니라 모든 노드의 부

백준 1629번: 곱셈a를 b번 곱하는 대신 b/2번 곱한걸 제곱하면 연산 횟수를 줄일 수 있다. b가 1이 될 때까지 반복한다. 곱셈 연산을 21억번 하면 0.5초 안에 끝낼 수 없지만 이 방법을 사용하면 O(logN)의 시간복잡도를 가지기 때문에 0.5초 안에 끝낼

백준 1753번: 최단경로다익스트라 알고리즘 문제다. 시작 노드를 선택하고 그 노드부터 연결된 노드를 탐색하며 최단 거리를 저장해 둔 리스트를 업데이트한다. 연결된 노드중에 비용이 가장 적은 노드를 다음으로 우선으로 탐색한다(그리디 알고리즘 느낌). 비용이 가장 적은

다익스트라 알고리즘을 여러번 사용하면 답을 찾을 수 있다.1->v1->v2->N / 1->v2->v1->N 두 가지 경우중 더 적은 비용으로 N까지 도달하는 경우가 정답이다. 다익스트라 안보고 짤 수 있을때까지 연습해야겠다.

백준 2206번: 벽 부수고 이동하기맨 처음 생각했던 방법은 모든 벽 (1)을 길(0)으로 하나씩 바꿔보고 BFS를 하는 방식이었는데 벽의 최대 개수가 NM개이기 때문에 시간복잡도가 O(N^2M^2)가 되어 풀 수 없었다.모든 벽을 부숴보면서 풀 수 없기 때문에 길을

백준 9935번: 문자열 폭발문자열 길이 최대 1,000,000이다. 그냥 string.find(어쩌구) 하면 당연히 시간초과가 난다. 여러번 find하고 그 과정에서 문자열을 계속 탐색하기 때문. 문자열에서 문자를 하나씩 뽑아 리스트에 넣는다. 그러다 뒷부분이 폭발

정수 삼각형 백준 1932번: 정수 삼각형 아이디어 같은 크기의 배열을 만들어서 합을 기록한다. 이 때 본인과 더해질 수 있는 숫자는 왼쪽 위, 오른쪽 위 두 가지 경우 뿐이므로 둘 중 합이 더 커지는 경우를 기록한다. 맨 왼쪽, 맨 오른쪽은 선택의 여지가 없으므로

구간 합 구하기 5

귀여운 플로이드

백준 1011번: Fly me to the Alpha Centauri수학 문제다. 1 121 12321 1234321 각각 1, 4, 9, 16… 모두 제곱수다. 제곱수를 기준으로 대칭이 된다. 대학교 1학년때 풀다 어려워서 도망간 문제다. 이걸 왜 못풀었지?

백준 12851번: 숨바꼭질 2백준 1697번: 숨바꼭질 문제를 살짝 응용한 문제다. 가장 빠른 시간 내에 찾는 경우의 수를 구해야 한다. 큐에 집어넣는 조건을 바꿔줬다.원래는 다음 위치에 저장된 값이 0일 때(방문한 적 없을 때) 큐에 집에넣었는데 이 문제에서는 다음

백준 17928번: 오큰수수열의 크기가 1,000,000이다. O(NlogN)의 시간복잡도를 가진 알고리즘을 설계하면 풀 수 있을 것 같다. 그런데 이 문제는 O(N)의 시간복잡도로 풀 수 있다. 그림입력받은 수열을 역순으로 집어넣은 스택 A, 빈 스택 B를 만든다.

백준 13549번: 숨바꼭질 3순간이동을 하는 경우 걸리는 시간이 0이다. 이 경우를 우선적으로 처리해주기 위해 가장 먼저 push한다. 또, 비용이 적은 경우를 우선적으로 처리해주기 위해 우선순위 큐를 이용한다. 그냥 deque로 풀어도 될듯? 이게 bfs문제에서 한

백준 13913번: 숨바꼭질배열에 비용과 함께 직전에 어디를 지나서 왔는지 함께 기록한다. 최단거리를 구하고, 마지막부터 역추적한다. 숨바꼭질 장인이 되었다.

백준 12865번: 평범한 배낭dp테이블에 각 무게에서 담을 수 있는 무게중에 가치가 최대인 경우를 저장한다.(인덱스가 무게임)이렇게 저장하면 막 "물건 이거 넣어봤다가.. 다른거 다시 넣어봤다가.." 이런 슬픈 완전탐색을 할 필요 없이 가방에 넣을 수 있는 최대한의

백준 9465번: 스티커간단한 dp 문제다. 스티커가 두 줄이기 때문에 dp테이블도 두 줄로 만들었다. 테이블에는 "해당 위치에 있는 스티커를 선택했을 때 만들 수 있는 최대한의 점수"를 기록했다. 아 클래스4 언제다풀지

백준 2407번: 조합고등학교 확률과 통계 시간에 배운 파스칼의 삼각형을 기억하는가?? 난 당연히 까먹어서 검색해봤다. 모의고사 볼 때 확통 틀린날은 반성하는 날이었다.

백준 1167번: 트리의 지름트리에서 아무 노드나 하나 잡고(루트 노드) dfs로 가장 멀리 있는 노드를 찾는다. 그리고 찾은 노드에서 가장 멀리 떨어져 있는 노드까지의 거리가 트리의 지름이다. 왜 이렇게 되는걸까? 맨 처음에는 루트에서 멀리 있는 노드 두 개 찾아서

백준 3482번: Labyrinth미궁에서 밧줄을 가장 길게 연결하는 방법을 구해야 한다. 즉 "가장 멀리 떨어진 두 노드"의 길이를 구하면 된다. 어떻게 구하면 좋을까?문제에 "The labyrinth is designed in such a way that there

백준 1422번: 숫자의 신a와 b 두 숫자중에 어떤 숫자가 앞에 와야 하는지 생각해보자. 우선 무조건 앞자리가 큰 숫자가 맨 앞에 와야 한다. 문제는 앞부분이 똑같은 두개의 숫자(232와 23, 212와 21)를 비교하는 경우이다. 긴 숫자를 a, 짧은 숫자를 b라고

백준 1918번: 후위 표기식각 연산자별로 우선순위 정의 (괄호->곱하기 나누기->더하기 빼기)피연산자는 바로 출력한다.여는 괄호를 만나면 스택에 push한다.닫는 괄호를 만나면 짝을 이루는 여는 괄호를 만날 때까지 스택에 쌓여있는 연산자를 pop해서 출력한다.스택의

백준 9251번: LCSDP 테이블에 해당 문자열로 만들 수 있는 Longest Common Subsequence의 길이를 저장한다. 그림2차원 배열의 인덱스와 두 문자열의 인덱스를 매칭시킨다. 예를 들어 주어진 문자열이 ACAYKP, CAPCAK라 하자. 이 때 dp

백준 2493번: 탑스택 2개를 만들고 1번 스택에 모두 push한다. 1번 스택의 top과 2번 스택의 top을 비교한다. 스택 2번의 top이 더 크거나 스택 2번이 비어있을 경우 1번 스택에서 pop해서 2번 스택에 push한다. 1번 스택의 top이 더 큰 경우

백준 3015번: 오아시스 재결합이 문제의 핵심은 "같은 키를 가진 사람들을 어떻게 처리할 것인가?" 이다. 스택에 push할 때 같은 키를 가진 사람이 몇명 연속돼있는지 함께 기록한다.1\. 스택의 top과 현재 입력값을 비교한다.2\. 현재 입력값과 같은 경우 스택

백준 4179번: 불!간단한 bfs문제다. 불이 번지는 미로랑 지훈이가 움직이는 미로를 따로 만든다. 불을 먼저 다 번지게 만들고, 지훈이가 그 불보다 빠르게 갈 수 있는 곳을 찾아서 큐에 집어넣는다. 불이 하나도 없는 경우를 조심하자. 지도에 있는 숫자가 다 0이 되

백준 5014번: 스타트링크간단한 bfs 문제다. 건물 범위를 벗어나지 않도록(1층부터 f층까지) 조심하고 한 번도 층에 도달한 적이 없거나, 더 짧은 시간 안에 도달할 수 있는 경우 큐에 집어넣는다. 범위 조심. 쉬운 문제 푸니까 힐링된다.

백준 9466번: 텀 프로젝트그냥 dfs하면 안되고 ”학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한

백준 16920번: 확장 게임정해진 횟수만큼만 bfs를 해야 한다. 플레이어 1번부터 9번까지 각각 Queue를 만들어주고 따로따로 bfs를 하면 된다. 뭔가 우선순위 큐로 잘 만들면 되지 않을까?? 하다가 포기하고 그냥 큐 여러개 썼다.

백준 11967번: 불켜기원래라면 방문하지 못했을 곳이 나중에 불을 켜서 방문할 수 있게 되는 경우가 있다. 이 경우를 위해 지금은 못가지만 나중에 불이 켜지기만 하면 갈 수 있는 곳을 추가로 기록한다. 그리고 불을 켰을 때 귀여운 소 베시를 거기로 순간이동(?) 시켜

백준 1525번: 퍼즐좀 어려운 BFS문제다. 우선 퍼즐을 표현할 때 문자열으로 표현했다. 2차원 배열로 표현하면 map의 key로 사용할 수 없기 때문이다.(근데 이거 포인터로 하면 될것같기도?… 잘 모르겠다.) 또 일반적으로는 visited 배열로 방문했음을 표시하

숨바꼭질 5 백준 17071번: 숨바꼭질 5 아이디어

백준 2294번: 동전 2Dp테이블에 해당 금액을 만드는데 필요한 동전의 최소 개수를 기록한다. 1번 동전부터 N번 동전까지의 금액을 각각 S(1) ~ S(N)이라 하면, N번째 동전까지 사용해서 K원을 만드는데 필요한 동전의 최소 개수는 N-1번째 동전까지 사용해서

백준 1182번: 부분수열의 합N개의 숫자 각각 포함시키거나 포함시키지 않는 경우를 모두 탐색한다. 2^N인데 N이 작아서 풀 수 있다.벡터를 전달할 때 &(참조자)로 전달하면 시간이 1/22로 줄어든다. 대박! 그냥 전달하면 벡터를 복사하는데 시간이 들기 때문이다.

백준 1759번: 암호 만들기입력받은 모든 알파벳을 포함하거나 포함하지 않는 경우 전부를 탐색하는데 이 때 모음 최소 1개, 자음 최소 2개가 되어야 하기 때문에 모음의 포함 여부, 자음의 개수를 기록하며 탐색한다. 함수 인자가 5개!

백준 1987번: 알파벳상하좌우 알파벳중에 고른 적 없는 알파벳이 있으면 고르고, 함수가 끝나면 방문 배열에서 방문한 적 없다고 표시해준다. 맨 처음 알파벳은 항상 방문처리 되어있음에 유의. 따라서 count도 1부터 시작한다.

백준 2580번: 스도쿠숫자를 입력받으면서 스도쿠 판에 기록하고 각 행, 열, 3\*3 정사각형에 해당 숫자가 포함되는지 확인하는 배열에도 기록한다. 0을 입력받으면 그 좌표에는 숫자를 채워줘야 하니 따로 기록해둔다.기록해둔 좌표에 숫자 1부터 9까지 하나하나 조건에

백준 2096번: 내려가기dp테이블에 현재 위치의 숫자 + 이전에 고를 수 있던 숫자들중 가장 큰(작은) 값을 저장한다. 메모리 제한이 4MB다. dp테이블을 재활용했고 입력받는 숫자는 short로 받았다. 아슬아슬하게 통과함.

색종이 붙이기 백준 17136번: 색종이 붙이기 아이디어 색종이를 사이즈별로 붙이다가 더이상 붙일 수 없을 때 이전의 상태로 돌아가면 된다. 이 때 주의할 점이 몇가지 있다. > 1. 색종이를 붙였을 때 10x10 사이즈 종이 바깥으로 벗어나는지 확인. 같은 사이

백준 2263번: 트리의 순회postorder의 맨 뒤에 나오는 숫자가 루트 노드이다. 이 숫자를 inorder에서 찾는다. inorder에서 찾은 루트 노드를 기준으로 왼쪽, 오른쪽에 나오는 숫자들이 각각 왼쪽 서브트리, 오른쪽 서브트리를 이룬다. 여기서 각각 서브트

백준 1799번: 비숍비숍을 하나 놓으면 그 비숍을 기준으로 기울기가 1, -1인 대각선 방향 모두 비숍을 놓을 수 없다. 기울기가 1인 대각선 방향 좌표의 합(row + col)이 모두 일정하고, 기울기가 -1인 대각선 방향 좌표의 차(row-col)도 모두 일정하다

백준 1562번: 계단 수0부터 9까지 모든 숫자를 다 사용해야 한다. 지금까지 어떤 숫자를 사용했는지 2진수로 표현해보자.000000001은 숫자 0을 사용한 것이고 000000101은 숫자 2와 0을 사용한 것이다. 111111111은 0부터 9까지 모든 숫자를 다

백준 12094번: 2048 (Hard)구현 부분과 가지치기 부분으로 나뉜다. 상하좌우로 미는 함수를 모두 구현하면 귀찮다. 한쪽 방향으로 미는 함수만 하나 구현해놓고, 배열을 90도씩 돌려가면서 밀면 모든 방향으로 다 밀 수 있다. 왼쪽으로 미는 기준으로 설명하겠다.

백준 2001번: 보석 줍기현재 가지고 있는 보석의 상태를 비트로 표현한다. 섬에 방문할 때 이전에 같은 보석 상태로 방문한 적이 없으면 방문한다. 1번 섬으로 돌아왔을 때 현재 가지고 있는 보석 개수를 가지고 최댓값을 갱신한다. 1번 섬에 마지막으로 도착해서 보석을

백준 1194번: 달이 차오른다, 가자.현재 열쇠 보유 현황을 비트로 표현한다. 미로에서 이전에 방문했던 위치라도 현재 가지고 있는 열쇠 현황이 그때 당시와 다르면 다시 방문해도 된다. 비트마스킹 고수의 길..

백준 14442번: 벽 부수고 이동하기 2벽을 몇 개 부수고 이동했는지 상태를 기록한다. BFS 문제들 풀다보니 상태 기록이 핵심이 되는 문제가 많다. 내가 벽을 몇 개 부쉈는지, 현재 열쇠를 몇 개 가지고 있는지 등등 탐색에 영향이 가는 상태를 잘 구분해서 기록해야

백준 16933번: 벽 부수고 이동하기 3벽 부수고 이동하기 2 문제를 조금만 응용하면 풀 수 있다. 우선 벽에 가로막혔을 경우 낮이면 벽을 뚫고 지나가고, 밤이면 기다린다. 이 때 지금이 낮인지 밤인지, 그리고 몇 번 기다렸는지를 함께 기록해서 BFS한다. 마지막 답

백준 9328번: 열쇠우선 거리를 재는 문제가 아니기 때문에 열쇠 보유 상황에 따라 다른 배열을 사용할 필요는 없다. visited 배열에 현재 열쇠 상태를 기록한다. 이전과 다른 열쇠 보유 상황이면(열쇠 하나라도 새로 주웠으면) 다시 탐색한다.열쇠 보유 상황은 a부터

백준 2098번: 외판원 순회모든 도시를 한 번씩 방문해야 한다. 무조건 첫 번째 도시부터 방문하자. 어차피 모든 도시를 방문해야 하기 때문에 시작하는 도시가 어디인지는 답에 영향을 주지 않는다.visited에 도시 방문 여부를 표시한다. i번째 마을 방문 여부는 vi

백준 1600번: 말이 되고픈 원숭이벽 부수고 이동하기랑 똑같다. 점프한 횟수에 따라 다른 배열에 기록해주고 큐에 집어넣을때도 점프한 횟수를 함께 기록한다. 골드 1 달성 ㄷㄷ

백준 1102번: 발전소외판원 순환 문제보다 살짝 단순하다. 현재 상태에서 적어도 P개의 발전소가 돌아가기까지 필요한 최소 비용을 메모이제이션 하면 된다. 얘도 그렇고 외판원 순회도 그렇고 탑다운 dp로 풀면 좀 더 직관적으로 풀 수 있다. 많이 짜서 탑다운 모양을 익

백준 3056번: 007몇번 지미가 미션을 먼저 수행하는지는 신경쓸 필요가 없다. 각 미션의 할당 여부를 비트필드로 나타낸다. 지미 번호를 1씩 키우면서 넘겨준다. 모든 미션을 클리어했을 때 확률 변동이 없어야 하기 때문에 1을 반환한다.생각해보니까 PS하면서 처음으로

백준 2320번: 끝말잇기마지막 문자가 X이고, 지금까지 사용한 단어 목록을 Y라 하자. 이 상태에서 낼 수 있는 가장 높은 점수를 cacheX에 메모이제이션 ㄱㄱ풀다보니 탑다운 재귀가 다 비슷한거같기도 하고?.. 종만북 피셜 더 직관적이라는게 팩트인듯. 아 빨리 플레

백준 16991번: 외판원 순회 3외판원 순회 1이랑 똑같고 cost 대신 거리를 구하면 된다. 소수점 출력 주의.기본 6자리 출력이라 그냥 만 쳐도 소수점 6자리까지 나온다.

백준 1029번: 그림 교환현재 그림을 가지고 있는 예술가를 X, 그 예술가가 그림을 구매한 가격을 Y, 지금까지 그림을 소유해봤던 예술가의 목록을 Z라 하고 cacheXZ에 메모이제이션 ㄱㄱ그림을 여러번 사도 되는 줄 알았는데 아니었다. 문제를 꼼꼼히 읽도록 하자.

백준 1480번: 보석 모으기현재 가방 번호, 현재 가방에 담긴 보석 무게, 지금까지 담은 보석 목록 메모이제이션 ㄱㄱ이미 담은 보석이거나, 보석 무게가 가방 무게보다 큰 경우는 탐색하지 않는다. 보석 무게가 가방 무게보단 덜 나가지만 지금 가방에 다른 보석이 들어있어

음메

백준 1176번: 섞기cache마지막으로 세운 학생에 메모이제이션 ㄱㄱ

백준 1715번: 카드 정렬하기항상 제일 작은 카드덩이 두개를 합친다. 최소 힙에서 원소 두개씩 꺼내서 합친다음에 다시 힙에 푸쉬해준다. 이걸 힙에 원소가 딱 하나만 남을때까지 반복하면 된다. 반복하면서 카드 두개 합칠때마다 몇 번 비교했는지 센다. C++에서 우선순위

백준 2014번: 소수의 곱맨 처음 소수를 입력받을 때 최소 힙에 다 푸쉬한다. 그리고 하나씩 꺼내면서 입력받은 모든 소수와 한 번씩 곱하고, 그 값을 다시 푸쉬한다. 중복이 있을 수 있으므로 원소를 꺼낼 때 똑같은 원소를 다 꺼내고 N은 1만 감소시킨다. 첫 번째로

백준 2696번: 중앙값 구하기최대 힙, 최소 힙 하나씩 준비한다.1\. 최대 힙에 원소 하나를 push한다. 2\. 그 다음 원소부터는 최대 힙의 top에 위치한 원소보다 큰 경우는 최소 힙에 push하고, 아니면 최대 힙에 push한다.3\. 두개의 원소가 삽입된

백준 14464번: 소가 길을 건너간 이유 4닭이 도와줄 수 있는 소랑 매칭시켜주면 된다. 그런데 닭이 도와줄 수 있는 소가 2마리 이상이면 어떤 소를 도와줘야 할까? 닭이 도와줄 수 있는 시각을 T라 하고 소 A가 길을 건너는 시간이 Sa, Ea, 소 B가 길을 건너

백준 1717번: 집합의 표현유니온 파인드 (분리 집합)이라고 부르는 자료구조가 있다.각 원소는 모두 트리의 루트이고, 이를 합치는 연산(union)과 루트를 확인하는 연산(find) 두가지가 존재한다. 원래는 parent에 자기 부모를 저장해서 주루루룩 타고 올라

백준 16562번: 친구비친구끼리 Union해주는데 이 때 친구비가 제일 저렴한 애가 루트가 되도록 합친다.맨 처음에는 cost루트 인덱스에 각 집합의 최소 친구비가 들어가도록 짰는데 잘 안됐다. 왜안됐지? 솔직히 아직도 잘 모르겠다. 이렇게 했는데 어딘가 빼먹는게 있

백준 4195번: 친구 네트워크유니온 파인드 자료구조에 잡기술을 하나 추가한다. 원래 parentn == n 이면 루트 노드임을 확인하고 n을 리턴했는데 대신에 parentn이 음수인 경우 루트 노드임을 확인하고 n을 리턴해준다. 기본적으로 모두 -1을 가지고 있고

백준 17404번: RGB거리 2Cache이전에 칠한 색 에 메모이제이션 ㄱㄱ시작위치 끝날때랑 비교 ㄱㄱ

백준 11049번: 행렬 곱셈 순서cache시작 위치에 최소 연산 횟수를 메모이제이션 한다.최소 연산 횟수는 그림처럼 분할정복 느낌으로 구한다.엄청 쉬워보여서 풀기 시작했는데 결국 식을 잘못 세워서 맞왜틀?? 하고 한참 헤매다 찾아봤다..조그만 예제 만들고 식을 세우면

백준 7579번: 앱맨 처음 계획한 풀이는 배열의 인덱스를 지금까지 확보한 메모리로 하고, 그 값은 메모리를 확보하는데 필요한 최소한의 비용으로 해서 풀려고 했는데 메모리가 천만이라 실패했다.발상의 전환으로, 배열의 인덱스를 지금까지 사용한 비용으로 하고, 그 값은 해

백준 17387번: 선분 교차 2벡터의 외적 아는사람?반시계방향(CCW)으로 외적하면 양수, 시계방향으로 외적하면 음수, 일직선이면 0이걸로 선분의 교차 여부를 알 수 있다. 어떻게??p1(x1, y1) p2(x2, y2) / p3(x3, y3) p4(x4, y4) 이

백준 2162번: 선분 그룹선분이 교차하면 Union.유니온 파인드 자료구조에서 proot에는 원소의 개수(음수로) 저장.백준 4195번: 친구 네트워크백준 17387번: 선분 교차 2여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다.

백준 2342번: Dance Dance Revolution현재 발 상태와 진행도를 인덱스로 비용 메모이제이션 ㄱㄱ쉽다.

백준 10942번: 팰린드롬?cachestart에 메모이제이션 ㄱㄱstart와 end에 위치한 문자가 같고, 그 두개를 뺀 문자열이 팰린드롬이면 start ~ end도 팰린드롬이다. Base case는 문자가 하나이거나 두개인 경우.집컴에 올려놓은 code-server

팰린드롬 분할 백준 1509번: 팰린드롬 분할 아이디어 방금 전에 푼 문제 재활용했다. 최소 분할 개수를 구할때도 DP로 구했다. 코드 여담 > 분할 개수 구하는 과정도 subproblem 만들어서 dp로 풀어야했는데 별 생각없이 완전탐색하다 시간초과남.

백준 14003번: 가장 긴 증가하는 부분 수열 5O(NlogN) LIS를 구현하는 방법은 이전에 알아봤다. 길이 i를 만드는 수열의 최소 마지막 숫자를 vi에 저장한다. 그럼 이제 그 수열을 어떻게 출력하는게 좋을까?그냥 v에 저장된거 순서대로 출력하면 당연히 틀린다

백준 14868번: 문명상하좌우 한 칸씩 문명이 전파되는건 bfs로 어렵지 않게 구현할 수 있다. 숫자 1씩 늘리면서 몇년 지난건지도 알 수 있다. 그리고 방금 전파된 장소에서 상하좌우에 다른 문명이 있는 경우, union한다. 연도 순서대로 큐에 들어가기 때문에 1년

백준 9938번: 방 청소서랍끼리 union 연산을 수행한다. 이 때 루트에는 연결된 서랍들중에 빈자리가 몇개인지 음수로 표시한다.이렇게 하면 술병을 입력받을 때마다 이 술을 보관할 수 있는지, 아니면 마셔야 하는지 알 수 있다.보관할 수 있다면 (입력받은 서랍 두개의

백준 17398번: 통신망 분할완성 상태에서 하나씩 끊어보면서 찾으면 10만 \* 10만이라 풀 수 없다.맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다.비용이 int 범위를 넘어갈 수 있기 때문에 long l

백준 10775번: 공항기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번

백준 2042번: 구간 합 구하기세그먼트 트리 연습 문제다. 루트에는 전부 합한 값이, 그 자식은 구간을 반씩 잘라서 그 구간에 해당하는 값을 가지고 있다. 왼쪽 자식은 부모 인덱스 2, 오른쪽 자식은 부모 인덱스 2 + 1이다. (루트는 1부터)어떤 구간의 합이라

백준 11505번: 구간 곱 구하기구간 합 구하기랑 비슷한데 좀 생각할게 많다. 구간 곱을 구하는 함수는 범위를 벗어났을 때 1을 반환한다. Update가 살짝 느낌이 다르다. 루트부터 호출하여 리프 노드까지 내려가서 원하는 값으로 바꾸고, 하나씩 올라갈 때마다 자기

백준 2357번: 최솟값과 최댓값각 구간의 최솟값과 최댓값이 저장된 트리를 둘 다 만든다. 이런걸 멋있게 RMQ라고 부른다. Range Min / Max Query..

백준 12837번: 가계부 (Hard)단순한 구간 합 구하기 문제다. 1번 쿼리가 값을 변경하는 것이 아니라 그냥 더하는거다. 문제를 잘 읽자.

백준 6549번: 히스토그램에서 가장 큰 직사각형분할정복 문제다. 전체 구간을 start ~ end라 하자. 이중에서 높이가 최소인 막대기의 인덱스를 i라 하면 높이가 arri인 직사각형의 최대 넓이는 (end-start+1)\*arri가 된다. 그리고 인덱스 i를 기

버블 소트 백준 1517번: 버블 소트 아이디어 문제 이름은 버블 소트지만 버블 소트 하면서 몇번 swap했나 세면 당연히 틀린다. N이 최대 500,000이므로 O(NlogN)에 풀어야 한다. 세그트리에 정렬 여부를 기록한다. 쿼리를 날리면 해당 구간에 정렬되

백준 3006번: 터보소트이전 버블소트 문제에서 쿼리 날리는 순서를 바꾸기만 하면 풀 수 있다. 0 ~ i이랑 N-1-i ~ N-1 번갈아서 날려주면 1, N, 2, N-1 순서로 정렬 가능.터보소트 (느림)

백준 1280번: 나무 심기해당 구간에 존재하는 나무의 개수와 인덱스 0부터 각 나무까지 거리의 합을 세그먼트 트리에 기록한다. 이렇게 하면 새로운 나무를 심을 때 바로 cost를 구할 수 있다.리프 노드에는 {인덱스 번호 \* 나무 개수, 나무 개수}가 기록되어 있다

백준 3653번: 영화 수집쿼리가 최대 10만개 주어진다. 배열을 0~99,999, 100,000~199,999 두 구간으로 나누고, DVD를 가장 위로 올릴 때 10만부터 시작해서 하나씩 순서대로 올리면서 합을 구하면 풀 수 있다. DVD 번호가 주어졌을 때 배열의

백준 9345번: 디지털 비디오 디스크(DVDs)각 구간에서의 최댓값과 최솟값을 기록한다. L번 선반부터 R번 선반까지 쿼리를 날렸을 때 최솟값이 L, 최댓값이 R이면 DVD가 모두 있는 것이다.진짜 활용이 무궁무진하다. 최대, 최소, 합 등등 상황에 맞게 잘 짜야하는

백준 2243번: 사탕상자각 구간에서의 사탕 개수 합을 저장한다. rank번째로 맛있는 사탕을 사탕을 구할때는 세그먼트 트리에서 binary search를 하면 된다!루트부터 시작해서, left node에 저장된 합이 rank보다 크거나 같은 경우는 왼쪽으로, rank

백준 7578번: 공장A열 입력을 받을 때 기계의 식별번호를 인덱스로 하는 배열에 해당 기계가 A열에서 몇번 인덱스에 위치하는지 기록한다. B열 입력을 받을 때, A열 몇번 인덱스에 위치하는지 구하고, 그 위치부터 오른쪽으로 맨 끝까지 구간에서 줄이 연결된 개수를 구하

백준 2517번: 달리기자기보다 실력 높은사람 몇명 있는지 구하면 된다. 그런데 실력의 최댓값이 10억이다. 사이즈 10억짜리 배열을 만들면 터지니까 좌표 압축을 해야한다. N은 최대 50만이니까 충분히 가능하다. 좌표 압축은 map으로 했다. 실력순으로 정렬 후 제일

백준 1572번: 중앙값사탕상자 문제랑 비슷하다. 구간에서 순위를 구하는 문제는 나올 수 있는 전체 숫자 사이즈만큼 범위로 잡아서 트리를 만들고, 숫자가 나올 때마다 개수를 늘려주고, 해당 구간에서 개수의 합을 반환하는 쿼리를 짜면 된다. 최근 숫자 K개중에 중앙값을

백준 2104번: 부분배열 고르기히스토그램 문제랑 푸는 방법이 정확히 일치한다. 높이 가장 작은거 골라서 걔 기준으로 왼쪽, 오른쪽 분할정복. 최솟값의 인덱스를 저장해야 한다는 사실..!

발머의 피크 이론(Ballmer's Peak Theory)은 프로그래머의 혈중 알콜 농도가 0.129% 와 0.138% 사이일 때 초인적인 코딩 실력을 발휘한다는 이론이다.

백준 10999번: 구간 합 구하기 2구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다. 해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면

백준 12844번: XORXOR 연산은 결합법칙과 교환법칙이 성립한다. 따라서 구간합 세그먼트 트리처럼 구성할 수 있다. lazynode\*2 ^= lazynode 해야하는데 +=을 써버렸다. 상위 노드만 연속으로 방문해서 자식 노드에 업데이트 해야하는 내용이 쌓일 수

스위치 백준 1395번: 스위치 아이디어 tree에는 켜져있는 스위치의 개수를 기록한다. lazy에는 반전을 몇번이나 해야 하는지 기록해둔다. 두 번 반전하면 똑같아지므로 lazy[node]가 홀수인 경우만 반전을 해주면 된다. 반전이 일어나는 경우 현재 구간 사이

백준 13637번: 수열과 쿼리 1합병 정렬 중간 결과를 트리에 저장한다. 각 구간은 항상 정렬된 상태이다. query(l, r, k)를 날리면 각 구간마다 upper_bound로 k보다 큰 숫자가 몇 개 있는지 구하고, 합친다. 이런걸 merge sort tree라고

백준 7469번: K번째 수query(l, r, num)을 날리면 해당 구간에 num보다 작은 숫자가 몇개 있는지 알려준다. 이제 이걸로 이분탐색을 하면서 답을 구하면 된다. 3, 6, 9, 12에서 3번째 수가 무엇인지 구하기 위해 쿼리를 날렸다 하자. num이 7,

백준 13925번: 수열과 쿼리구간에 더하기, 곱하기 교체 세가지 쿼리를 모두 수행해야 한다. ax + b꼴로 lazy를 만들고, 곱셈 쿼리가 들어오면 a*=v, b*=v, 덧셈 쿼리가 들어오면 b+=v, 교체 쿼리가 들어오면 a*=0, b*=,0, b+=v 를 해주면

백준 5419번: 북서풍자기보다 x좌표가 크면서 y좌표가 작은 점이 몇개인지 세면 된다. x좌표 오름차순으로 정렬해서 순서대로 자기보다 y좌표가 작은 애가 몇개나 있는지 보면 하나도 빼놓지 않고 찾을 수 있다. y좌표가 작은 애가 몇개인지 찾기 위해 좌표압축을 하고,

백준 17131번: 여우가 정보섬에 올라온 이유스위핑을 두 번 해주면 된다. 왼쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 세고, 오른쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 센 후에 곱해주면 된다. 셀때 y좌표는 무조건 작은걸 먼저 세야 한다 큰걸 먼저

백준 2533번: 사회망 서비스부모가 얼리어답터라면 내가 얼리어답터가 되는 경우와 되지 않는 경우 두 가지를 모두 고려한다. 부모가 얼리어답터가 아니라면 내가 얼리어답터가 되는 경우만 고려하면 된다. 루트 노드부터 내려가면서 모든 케이스를 시도해보고, 그중 최솟값을 메

백준 2248번: 이진수 찾기dp자릿수에 경우의 수를 기록.nCr 계산해서 dp테이블 채운다고 생각하면 편하다.이 때 I번째 수를 구하는 방법은 다음과 같다.N = 5, L = 3, I = 19일 때 00000~11100중에 19번째 수를 찾으면 된다.맨 앞자리부터 채

백준 2213번: 트리의 독립집합루트부터 내려가면서 해당 노드를 선택할지 말지 결정한다. 만약 부모 노드가 선택된 상태라면 현재 노드를 선택하지 않는 경우만 고려하면 되고, 부모 노드가 선택되지 않은 상태라면 현재 노드를 선택하는 경우, 선택하지 않는 경우 두 가지 모

f500,000(x)를 구하기 위해 50만번 함수를 실행하면 시간초과를 받을 것이다. f1(x), f2(x), f4(x), f8(x), f16(x).. 이렇게 미리 저장해놓으면 빠르게 구할 수 있다.

백준 15422번: Bumped!도로는 무방향, 비행기 티켓은 방향 간선임에 주의.똑같은 그래프 두 개(g1, g2) 만들고, 각각 주어진 도로 입력대로 연결해준다. 그리고 비행기 티켓 입력대로 g1의 u번 도시와 g2의 v번 도시를 연결해준다. 이 때 cost는 0이

인간 대포 백준 10473번: 인간 대포 아이디어 시작 위치를 0번 노드, 모든 대포를 1~N, 목적지를 N+1번 노드로 한다. 각각의 노드끼리 이동하는데 걸리는 시간을 모두 (N+1)*(N+1)배열에 기록한다. 30m보다 거리가 짧은 경우 그냥 걸어가는게 이득이

백준 2211번: 네트워크 복구문제를 보면 최소 스패닝 트리 문제인가? 싶지만 1번 노드에서 출발할 때 최소 거리를 구하는 문제다. 필요한 간선만 빼고 다 잘라내면, 결국 트리가 된다. 각 노드별로, 자신의 부모 노드가 무엇인지만 기록한다면 어떤 간선을 살려야 하는지

거의 최단 경로 백준 5719번: 거의 최단 경로 아이디어 최단 경로에 포함되는 모든 간선을 지나면 안된다. 최단 경로가 여러개인 경우 전부 지나면 안된다. 따라서 최단경로의 길이를 구하고, 다음 최단 경로의 길이가 바뀔 때까지 경로를 지우는 방법을 사용하려고 했

백준 1162번: 도로포장어려운 다익스트라. 단순하게 방문 여부로 우선순위 큐에서 거르지 말고, 거리를 비교한다. 거리를 기록할 때 몇 번 도로를 포장했는지 상태를 정의한다. 약간 dp느낌?연산자 오버로딩 잘못해놓고 한참 고민함 ㅠㅠtypedef struct \_Dat

백준 10217번: KCM Travel도로포장 문제랑 비슷하다. cost 상태를 정의하고 소요 시간을 기록한다. 튜플 쓰기 넘 불편하다. 왜 5초나 걸렸을까? DP로 풀면 더 빨라질지도?

백준 11657번: 타임머신음의 간선이 존재하기 때문에 다익스트라 알고리즘으로는 최단거리를 찾을 수 없다. 따라서 O(VE)로 모든 경우의 수를 탐색하는 벨만 포드 알고리즘이 적합. i가 1씩 커질때마다 싸이클을 한번씩 돈다고 하면, 500바퀴 돌렸을 때 INT_MIN

백준 1738번: 골목길음의 간선을 포함한 최단거리 찾기. 이 때 단순히 사이클이 존재한다고 -1을 출력하는 것이 아니라, 1부터 N까지 가는 길에 사이클이 존재하여 N에 도착했을 때 금품을 무한히 가질 수 있는 경우에만 -1을 출력해야 한다. 예를 들어, N=5이고,

백준 1219번: 오민식의 고민기본 아이디어는 골목길 문제와 비슷하다.간선을 탈 때 빼주고, 노드에 도착했을 때 더해준다. 이 문제도 도착점까지 가는 경로에 사이클이 있는 경우에만 Gee를 출력해야 한다. 골목길 문제는 1부터 N까지 순서대로 V-1번 루프를 돌고 마지

백준 1613번: 역사플로이드 한 번 돌리고 a->b만 INF면 b가 먼저 일어난거고, b->a만 INF면 a가 먼저 일어난거고, 둘 다 INF면 그래프가 연결되어 있지 않아서 전후 관계를 알 수 없다. 한국사 세계사 시간 특) 꿀잠시간

백준 2610번: 회의준비BFS로 각 컴포넌트별로 나누고, 플로이드 한번 돌리고, 각 컴포넌트에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록 대표를 고르면 된다. 오름차순 출력인데 그냥 출력해서 틀림. 문제를 잘 읽자.

백준 1602번: 도망자 원숭이현재 최단 거리와 그 경로에 있는 최대 지연 시간을 함께 기록한다. 최단 거리 갱신시 최대 지연 시간까지 합쳐서 계산한다. 이 때 지연시간이 짧은 노드부터 순차적으로 방문해본다. 정렬 후 DP를 하는 느낌으로?어려웡,, 푼사람들 보니까 그

백준 18185번: 라면 사기 (Small)백준 18186번: 라면 사기 (Large)1개를 사면 3원, 2개를 사면 5원, 3개를 사면 7원이다. 라면 1개를 사는 대신 2개를 사는 경우, 개당 가격이 3원에서 2.5원으로 0.5원 줄어든다. 라면 2개를 사는 대신

백준 1647번: 도시 분할 계획트리가 만들어지면 간선이 총 N-1개이다. MST를 만들다 간선의 개수가 N-2가 되었을 때 멈춘다면 도시가 최소의 비용으로 분할된다. 즐거운 MST

백준 4343번: Arctic NetworkSatellite Channel을 제외하고 MST를 만들면 된다. 마지막으로 뽑은 간선의 비용을 출력한다. 문제 해석이 제일 어렵다.

백준 2887번: 행성 터널x, y, z 좌표값 순서로 각각 한번씩 정렬해서 cost 계산하고 간선 리스트에 넣은 다음 비용순으로 정렬하면 된다. 맨날 연산자 < 오버로딩했는데 이번엔 비교함수로 해봤다.

백준 1944번: 복제 로봇모든 K에 번호를 부여한다. (for union-find)S와 모든 K에 대하여 여러번 BFS를 돌려 각각 K까지의 최단거리를 찾고, 간선 리스트에 추가한다. 이 때 1번에서 부여한 정점 번호를 사용한다. 간선 리스트를 정렬하고 MST를 구하

백준 9373번: 복도 뚫기양쪽 벽과 모든 센서를 정점으로 한다. 각각의 정점의 거리를 간선으로 하여 간선 리스트를 만들고 정렬 후 순서대로 연결한다. 양쪽 벽이 연결된 순간의 거리가 지나갈 수 있는 최대 거리다. n이 0일 때 w/2를 출력해야 한다.

백준 2623번: 음악프로그램위상 정렬을 하는 방법은 크게 두 가지가 존재한다. DFS하고 거꾸로 출력하기진입 차수가 0인 노드를 계속 큐에 집어넣으면서 찾기나는 1번 방법을 사용했다. 또 현재 DFS를 진행중인 노드를 만나는 경우 (아직 함수 실행이 끝나지 않은 노드

백준 1516번: 게임 개발위상정렬 후 순서대로 방문하면서 각 건물을 짓는데 필요한 시간을 기록한다. 이전 건물까지 짓는데 소요된 시간 + 현재 건물을 짓는데 필요한 시간 vs 현재 건물까지 짓는데 소요된 시간을 비교하여 더 큰 값으로 교체한다.스택에 넣고 다시 뽑아서

백준 1766번: 문제집DFS로 풀어보려 했으나 실패.. 최소 힙을 사용하도록 하자.진입 차수를 관리하며 0이 되면 pq에 넣고 돌리면 됨.아 그냥 좀 풀지 ㅋㅋ

백준 1005번: ACM Craft게임 개발 문제랑 똑같다. w에 대해서만 출력하면 된다.맨날 전역 배열만 쓰다보니 초기화하는걸 까먹음.

백준 2637번: 장난감 조립맨 처음에 진입차수가 없는 노드가 기본 부품이다. 기본 부품부터 시작해서 total cost를 기록한다. 큐에 넣고 돌리다 진입 차수가 0이 되는 경우, 자기 자신을 만드는데 필요한 모든 부품을 고려한 것이므로 큐에 집어넣는다. total

백준 3665번: 최종 순위1등->2등, 1등->3등, 1등->4등.. 2등->3등, 2등->4등.. 이런식으로 만들어놓고, 상대적인 등수가 바뀐 쌍의 경우 a->b를 b->a로 바꿔주면 된다!“상대적인 순위”가 변경되기 때문에 그래프를 모델링할 때 상대적인 순위로 모

백준 2848번: 알고스팟어단어 입력 순서대로 두개씩 비교한다. 맨 앞 알파벳부터 비교한다. 같으면 다음 알파벳으로 넘어가고 다르면 string1i->string2i 간선을 만들어준 후 다음 단어로 넘어간다. 그래프가 만들어지면 위상정렬 후 출력한다. 이 때 입력된 모

백준 1948번: 임계경로시작 노드부터 위상 정렬을 하면서 각 노드에 진입하는데 가장 오래 걸리는 시간을 기록한다. 이후 종료 노드에서 역방향 간선을 타면서 간선의 비용이 현재 노드 최대 진입 비용 - 다음 노드 최대 진입 비용 인 경우가 얼마나 되는지 센다. 소공 시

백준 1199번: 오일러 회로모든 간선을 딱 한 번씩만 사용해서 원점으로 돌아올 수 있으면 오일러 회로다. 오일러 회로는 모든 노드에 연결된 간선의 개수가 짝수여야만 한다. 오일러 회로를 구하기 위해 Hierholzer's Algorithm을 알아보자. a에서 시작해

백준 4013번: ATM같은 SCC에 속하는 ATM 전체를 털어서 돈을 챙기고 다음 ATM으로 이동할 수 있다. SCC를 구하고 이를 위상정렬해서 최대 금액을 구할 수 있다. 시작 지점이 정해져있기 때문에 시작 지점에서 도달 가능한 컴포넌트인지 확인해야 한다. 알아야

백준 6543번: 그래프의 싱크outdegree가 0인 scc에 속하는 모든 노드를 구하고, 오름차순으로 정렬 후 출력하면 된다. 그것이.. 싱크니까..!

백준 3977번: 축구 전술indegree가 0인 SCC가 단 한 개 존재하고, 그 SCC에 속하는 노드 번호를 출력하면 된다. indegree가 0인 SCC가 여러개인 경우 모든 SCC로 도달할 수 없기 때문에 Confused를 출력하면 된다. SCC 고수의 길..

백준 2152번: 여행 계획 세우기ATM 문제랑 비슷하다, 같은 SCC에 속하는 여행지는 모두 방문하고, 다음 SCC로 이동한다. 시작 지점에서 도달 가능한지 확인하고, 도달 가능하면 금액을 갱신한다. 당연한 얘기지만 위상정렬 할 때 그냥 시작 지점을 넣으면 안된다.

백준 11097번: 도시 계획입력된 그래프에서 SCC를 찾아서 묶고, 거기서 사이클 하나 만들어서 출력하고, 각 SCC에 속하는 노드 하나씩 뽑아서 u->v 출력하면 된다.중복 간선을 제거할 때 위상정렬을 사용하려고 했는데 안됐다...i->k, k->j가 존재하면 i-

백준 23797번: 개구리K로 끝난 개구리, P로 끝난 개구리가 몇마리인지 기록한다. K로 끝난 개구리가 있는데 P가 입력되면, k--, p++를 하고(합쳐지니까), K로 끝난 개구리 없이 그냥 P가 입력되면 p++만 한다.그중 가장 최대였던 k 혹은 p의 값이 정답이

컨닝 백준 1014번: 컨닝 아이디어 r-1행에 사람이 앉아있는 상태를 state라 하자. 이 때 cacher에 앉을 수 있는 최댓값을 메모이제이션 한다. 코드 여담 > 윗줄 사람이 어떻게 앉아있는지에만 영향을 받기 때문에 r값을 0부터 키우면서 아래로 내려가

백준 15824번: 너 봄에는 캡사이신이 맛있단다크기순으로 정렬하면 vi가 가장 매운 경우는 2^i, 가장 안매운 경우는 2^(n-1-i)이다. 식 전개해서 정리해보면 됨.주석처리해둔건 부끄러운 O(N^2) 코드다..

백준 16637번: 괄호 추가하기그냥 구현하면 됨.괄호 사이에 연산자 하나밖에 못들어가니까 주의.재귀로 잘 짜서 모든 경우의 수 미리 만들어놓고, 문자열 읽으면서 앞에서부터 계산하면 된다.문자열 공포증

백준 2981번: 검문N1 % M = kN2 % M = kN3 % M = kN4 % M = k...N2 % M - N1 % M = 0(N2 - N1) % M = 0따라서 각 숫자의 차를 구하고, 그 차의 최대공약수를 구한 후, 구한 최대공약수의 약수를 전부 출력하면 된

백준 2168번: 타일 위의 대각선대각선은 가로, 세로 모든 타일에 각 한 번씩 대응되고, 가로, 세로 길이의 최대공약수만큼 겹친다. 가로, 세로 길이가 서로소일 때 가로+세로-1이니까 gcd 단위로 쪼개고 이렇게 계산해도 됨. 근데 똑같음. 수학이 싫어

백준 2487번: 섞기 순열사이클 크기 모두 찾고 그 크기간의 최소공배수를 구하면 정답. 최소공배수를 구하기 위해 곱하는 과정에서 int 범위를 초과할 수 있다.

백준 16563번: 어려운 소인수분해에라토스테네스 체 잡기술arri에 i의 가장 작은 소인수를 저장한다. 주어진 숫자 k를 저거 계속 타고가면서 나누면 소인수분해임. 아니면 루트500만까지 소수 구해놓고 그 숫자로 주어진 숫자 k 계속 나누다가 다쓰면 남은 숫자 출력.

백준 24524번: 아름다운 문자열만들어야 하는 문자가 현재 몇 개 나왔는지 기록한다. 이 때 자기보다 한 칸 앞서서 나와야 하는 문자의 개수가 자기 자신보다 많은 경우에만 증가시킨다. 예를 들어 abcd를 찾는다 하면 현재 a를 2개, b를 1개, c를 1개 찾은 상

백준 24526번: 전화 돌리기그래프에서 사이클을 찾는다. 그 사이클에 포함된 노드와 사이클로 들어가는 노드를 제외한 노드가 몇 개 있는지 세주면 된다. 그래프를 거꾸로 뒤집는다. 그래도 사이클은 유지된다. 그리고 indegree를 기록하며 위상정렬을 한다. 사이클에

백준 24527번: 이상한 나라의 갈톤보드맨 처음 생각한 아이디어는 그냥 레이지 세그로 푸는거였다. 구간 업데이트를 로그 시간에 처리하고, 쿼리에 대답할 때는 누적합으로 상수 시간에 대답했다. 누적합 응용으로 imos법이라는게 있다. a부터 b까지 3을 더한다 하면,

백준 11689번: GCD(n, k) = 1https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC\_%ED%94%BC\_%ED%95%A8%EC%88%98이걸 구현하면 된다. n이 최대 10^12이므로 루트n까지

경찰차 백준 2618번: 경찰차 아이디어 1번 경찰차, 2번 경찰차가 현재 맡은 사건 번호로 메모이제이션. 이 때 처음에는 (1, 1), (N, N)에서 시작하니 그 부분만 따로 계산해주면 된다. tracking은 메모이제이션한 값 비교를 통해 몇번 경찰차가 사건

백준 1086번: 박성원주어진 순자를 하나씩 골라 뒤로 붙이면서 점점 큰 숫자를 만든다. 이 때 숫자가 커질 수 있으므로 나머지만 취한다. 어차피 나누어 떨어지는지 확인만 하면 됨. a뒤에 b를 붙이면 (a×10^b.length)+b이고 나머지를 계속 계산해야 하므로

백준 5670번: 휴대폰 자판자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다.모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다.다들 C-style 문자열(const char\*)로 trie를 구현하고, 그걸

백준 16934번: 게임 닉네임단어를 루트에 삽입하면서 하나씩 출력한다. 그러다가 다음 알파벳이 자식 노드로 존재하지 않으면, print를 false로 변경하고 재귀호출한다. print가 true인 경우에만 알파벳을 출력한다.같은 닉네임으로 가입한 유저를 숫자로 구분하

백준 19585번: 전설색상은 trie에 insert, 닉네임은 unordered_set에 insert.그리고 쿼리 앞부분부터 트라이에서 찾는다. 트라이에 알파벳이 존재하지 않으면 return false, 트라이에 해당 색상이 존재하고, 뒷쪽 substring이 uno

백준 5446번: 용량 부족지워야 하는 파일, 지우면 안 되는 파일 둘 다 트라이에 insert. 이 때 지워야 하는 파일은 노드 마지막에 종료 표시, 지우면 안 되는 파일은 모든 노드에 지울 수 없다고 표시. 노드 하나가 removable 하면 그 모든 자식들도 re

백준 3080번: 아름다운 이름노드 자식 개수만큼 permutation 구하면서 올라가면 된다. 로직 짜는건 쉬운데 그냥 Trie child26 해도 MLE, map<char, Trie> child해도 MLE.. 그나마 메모리 제일 적게 사용하는 vector 만들

백준 5467번: Type PrinterTrie를 구성하고 재귀적으로 깊이가 얕은 글자부터 출력한다.마지막에 최대한 긴 단어를 치고 지우지 않고 끝내야 한다.

백준 16903번: 수열과 쿼리 200이랑 1만 있는 트라이를 만든다. 입력받는 정수의 맨 앞쪽 비트 (2^29)부터 쭉 훑으면서 둘 다 있으면 XOR값을 최대로 할 수 있도록 선택, 둘 중 하나만 있으면 그거 선택. 다 더하면 정답!삭제 연산은 cnt를 감소시킨다.

백준 10464번: XORvi = a1^a2^a3^...ai라 하자. 이 때 i%4 == 3인 경우 vi 가 0이 된다!또 al^al+1^...ar-1^ar = vl-1^vr이다. 이를 이용하면 쉽게 문제를 풀 수 있다.누적합 느낌?

백준 2830번: 행성 X3입력받은 모든 정수중 a번 비트에 1이 몇개 있는지 기록한다. 최대 100만이니까 0번 비트 ~ 19번 비트까지 기록하면 됨. 이제 각 비트별로 1의 개수 × 0의 개수 하면 합을 구할 수 있다!수학 넘 어렵다.

백준 13710번: XOR 합 3앞에 올린 두가지 문제를 응용하면 된다. vl-1^vr = al^al+1^..ar-1^ar이라는 사실과비트별로 쪼개서 n번째 비트에 1이 몇 개 있는지 구하고 1의 개수 × 0의 개수 하면 값을 알 수 있다. XOR 고수의 길.. x^x

백준 13504번: XOR 합입력받은 수열의 누적 XOR을 계산해놓는다. 이 값을 전부 트라이에 삽입하고, 각각의 값과 XOR했을 때 최댓값이 부분수열 XOR의 최댓값이다. trie를 이런식으로 만드는게 훨씬 간편한듯. 노드 번호를 전역 변수로 관리한다. 새로운 노드를

백준 4354번: 문자열 제곱실패함수에서 fs.length-1은 가장 긴 접두사이면서 접미사의 길이이다. 우리가 구하는 n은 s.length/(s.length-fs.length-1)이다. 이 때 ABCAB같은 반례가 있기 때문에 나누어 떨어지는 경우에만 n으로 채택하도

백준 11585번: 속타는 저녁 메뉴문자열을 두 개 이어 붙인 다음 거기서 찾으면 한바퀴 돌리면서 찾는거랑 똑같음. 이 때 처음부터 끝까지 찾으면 하나 더 찾을수도 있으므로 한칸 건너 뛴다. ex) ABCABC에서 ABC 찾기오늘 저녁 짬이 뭐더라..

백준 24525번: SKK 문자열문자열에 포함된 K의 개수가 S의 개수의 2배여야 한다. S는 2, K는 -1, 그 외 글자는 0으로 해서 배열을 만들고, prefix sum을 구한다. 각 prefix sum의 값을 가지는 최소 인덱스를 기록하면 가장 긴 부분 문자열의

백준 3033번: 가장 긴 문자열문자열 해싱. ABCED - > 2^4A + 2^3B + 2^2C + 2^1D + 2^0\*E부분 문자열마다 계속 해쉬값을 구하지 않고, 이전에 구한 값을 재활용해서 구할 수 있다. 개어렵다.. 해쉬값을 인덱스로 가지는 부분 문자열의 시

백준 6206번: Milk Patternschar이 아니라 int를 쓰고, 해싱 충돌했을 경우 완전히 일치하는 개수를 세서 k-1개 이상인 경우 답을 갱신한다.라빈카프 넘 어렵다

아름다운 만영로 백준 17228번: 아름다운 만영로 아이디어 dfs로 탐색하면서 현재 해쉬값을 가지고 간다. 맨 처음에 계산한 P랑 일치하면 정답 개수 증가. 지금까지 거쳐간 알파벳들을 벡터에 push, 롤링해쉬 계산. 함수 호출 끝나면 pop. 코드 여담 >

백준 19608번: Searching for Strings모든 permutation에 대해 해시를 계산할 순 없고 그냥 알파벳 개수만 세서 a~z 개수가 같고, 해시값이 us에 없으면 집어넣는다. 이게 P4?..

백준 2287번: 모노디지털 표현숫자 i개 사용해서 만든 수 +\*-/ 숫자 j개 사용해서 만든 수 = cachei+j뺄셈, 나눗셈은 순서에 영향을 받기 때문에 뒤집어서도 해준다.이렇게 하면 괄호 생각 안하고 풀어도 됨. 아니 진짜 개어렵다.. 프로그래머스 스킬체크 레

화이팅!

백준 25402번: 트리와 쿼리S에 속한 노드끼리 union하면서 몇개인지 함께 기록한다. n(n-1)/2 계산하면 정답.NPC 선발 문제였는데 기한이 지나버렸다..왜 틀렸는지 며칠 내내 봤는데 25만개짜리 배열에 memset을 100만번 해버렸다.. 난 바보야..각

백준 25406번: 식사 계획 세우기이전에 먹지 않은 음식 중에서 가장 인덱스가 앞에 있는 음식을 먹는다. 이 때 한 종류의 음식이 과반수를 넘어가면 그 음식 먼저 먹는다. 과반수를 넘는지 확인하기 위해 set 하나, 이전에 먹지 않은 음식 중 가장 인덱스가 앞에 있는