백준

https://www.acmicpc.net/problem/11053이 문제는 dp테이블 하나와 수열의 값을 담는 배열을사용해야겠다고 접근했다.수열에 있는 어떤 한 값 seqi 보다 작은 인덱스들을 탐색하면서 seqi보다 작으면 dp테이블 dpi에 dpj+1을

https://www.acmicpc.net/problem/11052이 문제의 경우 합이 N이 되는 모든 경우를 살펴봐야 하기 때문에 일단 O(N^2) 알고리즘의 경우 시간이 얼마나 걸리는지 확인해보았다.(시간 제한 1초)최악의 경우 100만번이므로 O(N^2)

https://www.acmicpc.net/problem/2178이 문제는 최단 경로의 문제이기 때문에최단 경로 문제에 유리한 bfs를 사용해 풀어야 한다.먼저 bfs는 dfs와 달리 큐에 있는 노드들(몇 개 정도)의 탐색 범위의 깊이가 유사하다.따라서 같은

https://www.acmicpc.net/problem/1012 이 문제는 전에 다뤘던 이코테의

https://www.acmicpc.net/problem/7576이 문제는 bfs로 풀어야겠다는 생각이 들었다.이 문제의 포인트는 날짜 계산이었다.코드는 다음과 같다.날짜 계산은먼저, day0에서 익은 것들을 큐에 넣고큐의 사이즈를 담는 변수를 선언했다.bfs

https://acmicpc.net/problem/12865 소위 knapsack이라고 불리는 문제이다. 사실 이 문제 유형은 위 문제를 풀면서 알게 되었다.

https://www.acmicpc.net/problem/16928이 문제에 처음 접근할때에는 bfs보단 dp로도 풀릴 느낌이 들었다.하지만 dp로 풀게되면 경우를 탐색하는 것이 복잡하게 될 수있을 것 같아 bfs로 풀게 되었다.먼저 주사위를 던졌을 때 i+1

내가 접근하려는 방식은 다음과 같았다.(사실 이렇게 생각하는 힘을 키우는 것도 중요하게 생각한다.)

https://www.acmicpc.net/problem/2293이 문제의 풀이는 dp table을 작성할 때 데이터를 조금 색다르게 저장하는방식이어서 글을 쓴다.보통 dp 문제를 풀때 하나에 dp table 값에 대해 이중 for문이나 여러가지알고리즘을 수행

https://acmicpc.net/problem/24511이 문제는 시간 초과 때문에 꽤 많이 시도했다.쓸데 없는 과정을 줄이는 알고리즘을 작성하는 것이 관건이었다.큐에서의 원소는 항상 다음 자료구조로 넘어가고 스택에서의원소는 다음 자료구조로 넘어가지 않는다

https://www.acmicpc.net/problem/15649이 문제는 백트래킹 문제이다.dfs로 모든 경우를 탐색할 때 visited 배열을 사용해서 중복을 체크한다.(visited 배열로 중복 확인이 가능한 이유는 dfs를 호출하게 되면 호출한 경우에

https://www.acmicpc.net/problem/14888이 문제는 백트래킹 문제이다.arr에 숫자들을 저장하고, dfs를 사용하여 현재의 최댓값, 최솟값보다 초과, 미만이면 저장하는 방법으로 작성했다.코드는 다음과 같다.

https://www.acmicpc.net/problem/11054이 문제의 핵심은 증가하는 하는 부분에서 감소하는 부분을잘 체크하는 것이었다.N의 범위가 1000이어서 O(N^2)으로 시도해보았다.수열의 원소 하나당 그 전 원소들을 모두 탐색하며 dp테이블에

https://www.acmicpc.net/problem/2579이 문제는 점화식을 어떻게 세우는지가 관건인 문제였다.i번째 계단에 이르게 되는 경우는 두가지가 있다.i-3번째 계단까지의 최댓값 + i-1번째 계단 값ori-2번째의 계단까지의 최댓값이다. 따라

https://www.acmicpc.net/problem/1520이 문제는 dfs와 dp를 잘 조합해 활용해야 풀 수 있는 문제이다.dfs만 사용하게 되면 최악의 경우 약 4^(500\*500)의 시간 복잡도가생길 수 있다.따라서 dp를 적절히 활용해야하는데,

https://acmicpc.net/problem/1697이 문제는 bfs 문제이다.bfs로 가장 먼저 도달한 지점이 항상 최소 시간이므로도달한 지점에 또 도달하지 않게 작성해주면 된다.코드는 다음과 같다.

https://acmicpc.net/problem/2156이 문제는 dp 문제이다.이 문제가 계단오르기와 비슷해서 같은 방식으로접근했다가 꽤 오래 잡고 있었던 문제이다.(얍문님의 접근을 참고하였습니다.)먼저 dpi에는 i번째까지의 포도주를 마셨을때의 최댓값을

https://www.acmicpc.net/problem/14502구현의 비중이 높은 bfs 문제이다.먼저 이 문제는 0인 곳에 벽을 세우는 모든 경우의 수를 탐색해야 한다.따라서 브루트포스와 bfs를 적절히 사용해야한다.벽을 3개 세우는 경우를 모두 탐색해

https://acmicpc.net/problem/1914하노이 탑 재귀 알고리즘을 아는지 물어보는 문제였다.이 문제에서의 걸림돌은 큰 수를 처리하는 과정이었다.long long 자료형은 절댓값 2\*\*63-1 까지 저장할 수 있기 떄문에long long으로

https://www.acmicpc.net/problem/10844이 문제는 dp 테이블을 2차원 배열로 잡는 방법을 사용하는 문제이다.먼저 계단 수의 개수 간에 관계를 살펴보면 1~8은 다음 자리 수의 +-1이 되는 수를 유발하고, 0,9는 1,8을 유발한다

https://acmicpc.net/problem/2468이 문제는 백준 1012와 유사한 문제이다.수위를 0부터 지대의 최대 높이 전까지의 경우를 dfs를 사용하여모두 확인하고 최대 안전 영역을 그때 마다 갱신하면 되는 문제이다.

https://acmicpc.net/problem/2468이 문제는 백준 1012와 유사한 문제이다.수위를 0부터 지대의 최대 높이 전까지의 경우를 dfs를 사용하여모두 확인하고 최대 안전 영역을 그때 마다 갱신하면 되는 문제이다.

https://www.acmicpc.net/problem/1309 이 문제는

https://www.acmicpc.net/problem/1654이 문제는 parametric search를 사용해 푸는 문제이다.랜선 길이마다의 몫을 구해서 그때 마다 이분탐색을 했다.long long을 사용하지 않아서 조금 애먹었다.코드는 다음과 같다.

https://www.acmicpc.net/problem/2805떡볶이 떡 만들기와 유사하다.코드는 다음과 같다.

https://www.acmicpc.net/problem/20920이 문제는 다양한 방식의 정렬을 활용하면 되는 문제이다.이 문제의 포인트는 정렬 함수였다.빈도수길이알파벳 순일단 map에서 알파벳 순으로 정렬해주어서 이 부분은 정렬하지 않아도 되고,차례대로 길

https://www.acmicpc.net/problem/11057이 문제의 dp 테이블은 백준 쉬운 계단 수와 그냥 동일하다.같은 방식으로 0~9의 개수를 탐색하고 dp 테이블에 저장한다.사실 조합으로도 풀 수 있고, 다른 점화식으로도 풀 수 있었다.조합9+

https://acmicpc.net/problem/15659이 문제는 연산자 끼워넣기 문제의 연산자 우선순위 조건을 바꾼 문제이다.일반 대수학의 연산자 우선순위처럼 곱하기,나눗셈 먼저, 우선순위가 같다면앞에서부터 차근차근 계산하는 것을 구현하기 위해 백트래킹을

https://acmicpc.net/problem/3273

https://www.acmicpc.net/problem/1182 백트래킹으로 수열을 하나 하나 만들고 길이가 $$N$$이면 종료하는 solve함수를 사용해 해결했다. 탐색할 때 범위를 자기 인덱스 + 1을 해주어 겹치는 경우의 수를 제거했다. 코드는 다음과 같

https://www.acmicpc.net/problem/1448이 문제는 그리디를 써서 푸는 문제이다.일단 변의 길이 배열을 비오름차순 정렬하고 변 길이의 합의 최댓값을 찾아야하기 때문에 최대값부터 탐색한다.arri를 최댓값이라고 하면 arri+1 + arr

https://www.acmicpc.net/problem/5525이 문제는 문자열의 길이 범위가 10^6이라서 문자열 간 비교하는알고리즘으로는 시간 초과가 났다.따라서 다른 방법으로 접근해야했다.다음의 알고리즘은 $$O(N)$$으로 설계했다. 과정은 다음과 같

https://www.acmicpc.net/problem/2225이 문제는 dp 점화식 세우기가 매우 어려웠다.먼저 점화식을 세우기 전 수들의 규칙부터 살펴야 하는데,이를 정리하면 다음과 같다.K개의수로 I를 만드는 경우의 수를 나타낸 표다.위를 살펴보면 i를

https://www.acmicpc.net/problem/1344이 문제는 풀고 정말 기뻤던 문제이다.사실 이 문제를 풀려고 한 이유가 dp 경험 쌓으려고 푼 문제인데,조합으로 풀어서 AC를 받았다.$P_A$를 A팀이 간격 내 득점할 확률,$P_B$를 B팀이

https://www.acmicpc.net/problem/2343파라메트릭 서치 문제.이 문제를 풀면서 파라메트릭 서치의 답을 도출할때 무엇을 선택해야 할지다시 생각하게 된 문제이다. (s,mid,e 중 하나)풀이블루 레이의 값을 이분탐색해준다. (s는 강의

https://www.acmicpc.net/problem/17214낮은 정답률을 가지고 있는 문제, 이게 왜 골드 문제지 하고 제출했다가많이 실수 할 수 있는 문제이다.문제 풀이일단 경우의 수는일차항+상수항일차항상수항이렇게 3가지가 있는데 1차항과 상수항을 적

https://www.acmicpc.net/problem/16953이 문제는 dp로 접근했다가 오랜시간을 붙잡고 있었다.그래서 bfs로 다시 코드를 짰다.long long 을 사용하지 않아서 런타임 에러가 났다.코드는 다음과 같다.

https://www.acmicpc.net/problem/2096이 문제는 dp 문제이다.처음에는 dp테이블 두개, 값 저장용 arr를 썼더니 MLE가 떠서 다른 방법을 선택했다.인풋을 받고 바로 사용하는 방법을 선택했다.코드는 다음과 같다.

https://www.acmicpc.net/problem/1715 이 문제는 그리디 문제이다.

https://www.acmicpc.net/problem/9465이 문제는 dp로 접근했다.개인적으로 dp 접근법을 열어준 문제가 포도주 시식, 계단 오르기이렇게 있는 것 같은데 위 문제들과 같은 방식으로 접근했다.먼저 i번째 위쪽, 아래쪽 스티커를 떼는 경우

https://www.acmicpc.net/problem/1005이 문제는 위상 정렬을 배우고 풀었다.먼저 위상 정렬 없이 시도해본 결과 메모리 초과가 났다.벡터는 문제가 없는데, 아마 큐에 엄청나게 많이 담겨 메모리 초과가 난 것으로예상이 되었다.따라서 위상

while(cin >> a) 이런식으로 사용하자.https://www.acmicpc.net/board/view/120317이 글을 참고했습니다.

https://www.acmicpc.net/problem/1753이 문제는 다익스트라 알고리즘을 사용해야 하는 문제이다.다익스트라 알고리즘 글시작점을 기준으로 다익스트라를 실행한다.

https://www.acmicpc.net/problem/1446 이 문제는 dp, 다익스트라로 풀리는 문제이다. 처음에는 다익스트라 연습용으로 푼 문제였는데, 다시 생각해보니까 dp로도 풀 수 있는 문제였다. 비슷한 엣코더 문제 (최근 ABC340에 출제된 문

https://www.acmicpc.net/problem/1916이 문제는 다익스트라를 활용한 최단 거리를 구하는 문제이다.코드는 다음과 같다.

https://acmicpc.net/problem/12851 이 문제는 메모이제이션을 이용한 bfs 문제이다. bfs 사용 시 항상알고 가야될 생각이 있는데, 이 문제를 처음 풀 때 그 생각을 놓쳐서 탐색하지 못하는 부분이 생겼다. 아래는 틀린 코드이다. 따라

https://acmicpc.net/problem/1027문제 접근이 문제는 완전탐색이고, 겹치는 경우가 없게 탐색해야 한다.$i$번째 건물과 $j$번째 건물이 서로를 볼 수 있으려면,$(i,H_i)$ 와 $(j,H_j)$ 를 이은 일차함수가그 사이 건물들에

https://www.acmicpc.net/problem/11501이 문제는 뒤에서부터 탐색하는 방법이 잘 떠오르지 않아,많이 헤멘 그리디 문제이다.$i$번째 항은 $i+1$항부터 $n$번째 항까지의 최댓값에 팔아야 이득이다.따라서 뒤에서 부터 최댓값을 갱신하

https://www.acmicpc.net/problem/1080그리디 문제.문제 접근만약 현재 칸을 뒤집어야 한다면 && 뒤집을 수 있다면 뒤집고,뒤집지 않아도 된다면 뒤집지 않는 알고리즘을 작성했다.이 값은 최소를 보장할 수 있는데 뒤집는 범위를 다음과 같

https://www.acmicpc.net/problem/1449그리디 문제.문제 접근테이프를 붙일 때에 최대한 테이프의 손실이 없게 하면서,최대한 많이 붙여야한다.그리고 위치에 따라 순차적으로 붙여야 하기 때문에,arr를 정렬해주고 알고리즘을 수행해야 한다.

https://www.acmicpc.net/problem/1744그리디 문제.문제 접근큰 수끼리 곱하고, 1이면 곱하지 않고 더한다.음수가 남았을때는 0이 있으면 무시하고, 0이 없으면 더한다.코드는 다음과 같다.

https://www.acmicpc.net/problem/11000그리디 문제.문제 접근강의들 중 연결시킬 수 있는 것들은 최대한 연결시켜야 하기 때문에,끝나는 시각 우선순위 큐, 시작 시간 우선 순위 큐를 사용하여먼저 시작하는 회의들을 차근차근 시작한다.이때

https://www.acmicpc.net/problem/1783 그리디 문제. > 문제 접근 나이트가 최대한 많은 곳을 방문해야 하기 때문에, 우측으로 한칸 씩만 이동해야 한다. 근데 n과 m의 조합에 따라 움직일 수 없는 경우가 있기 때문에, 사실상 많은

https://www.acmicpc.net/problem/18310 그리디 문제. 처음에는 평균에 가까운 수가 답이라고 생각했지만 틀렸다. > 문제 접근 집이 n개가 있다고 했을 때,

https://www.acmicpc.net/problem/1339그리디 문제.문제 접근합을 크게 해야 되기 때문에 모든 수를 최대한 크게 만들어야한다. 예를 들어 다음과 같은 예시가 있다고 해보자.4AABBCBBAAD AACDADDDD이때는 직관적으로 A에 9

https://www.acmicpc.net/problem/12904 그리디 문제. > 문제 접근 처음에

https://www.acmicpc.net/problem/14908(이 영상을 참고했습니다)이 문제는 그리디 알고리즘의 증명법 영상을 찾아보다가 알게되어 풀게 되었다.그리디 알고리즘의 증명은 일반적으로는 어렵다.그중 여러가지 증명방식이 있는데 이번에 본 증명방

https://www.acmicpc.net/problem/11497그리디 문제.문제 접근통나무의 높이 차를 최소로 하려면 어떤 통나무의 높이와차이가 제일 적게 나는, 즉 어떤 통나무의 높이 다음으로 크거나,다음으로 작은 통나무를 인접시켜야 한다.근데 위 논리를

https://www.acmicpc.net/problem/11779다익스트라 문제.문제 접근최단 경로를 마지막으로 갱신한 노드가 최단 경로를 의미하므로,최단 경로를 갱신할 때 과정을 ans 벡터에 기록하고 출력했다.코드는 다음과 같다.

https://www.acmicpc.net/problem/10282다익스트라 문제.문제 접근a가 b를 의존한다는 것은 b가 감염된 후 a가 감염된다는 것을 의미하기 때문에, 그래프 상에서 b와 a가 간선으로 연결되어 있다고 생각할 수 있다.마지막 컴퓨터가 감염

https://www.acmicpc.net/problem/18428백트래킹 문제. 문제 접근장애물에 대해 백트래킹을 해주었고,처음 입력 받을 때 선생님의 위치를 받아놓았다가가로 세로로 탐색해 경우를 판별했다.코드는 다음과 같다.

https://www.acmicpc.net/problem/2141 그리디 문제. 백준 안테나 문제와 유사한 문제. > 문제 접근 안테나 문제와 마찬가지로 우측 좌측의 사람의 수 차이 만큼 거리가 감소 혹은 증가 하기 때문에 우측, 좌측 사람 수 차이가 양수에

https://www.acmicpc.net/problem/2565dp문제.문제 설명 LIS 응용문제를 보고 풀어서 아쉬웠다.문제 접근전깃줄이 겹치지 않는 조건은 어떤 전봇대에서 위치 $i$에 전깃줄이 연결되어 있을 때위치 $i$ 전에 연결되어 있는 전깃줄의 위

https://www.acmicpc.net/problem/1106dp 문제.범위 체크, 다른 도시여도 같은 지불값이 들어올 수 있다는 것을인지해야 되는 문제.문제 접근c의 범위가 1000이하의 자연수이고,고객 유치 가격과 얻는 고객의 수가 100이하 자연수이기

https://www.acmicpc.net/problem/1024수학 문제.문제 접근연속된 수열이므로 이는 $d=1$인 등차수열이다.따라서 등차수열의 합 공식을 사용하면 쉽게 풀 수 있는 문제이다.$d=1$인 등차수열의 합 공식 중 초항이 $a$ 길이가 $l$

https://www.acmicpc.net/problem/14497bfs 문제.문제 접근주난이가 뛸 때마다 bfs를 돌려주었다.1이면 0으로 바꾸고, 범인이 나오면 횟수를 출력했다.

https://www.acmicpc.net/problem/9663 백트래킹의 고유명사. > 문제 접근 한 행에 두개의 퀸이 존재 할 수 없기 때문에, N퀸 문제는 일차원 배열으로 해결할 수 있다. 놓을 수 있는지 판단하는 check 함수로 대각선, 열이 같은지

https://www.acmicpc.net/problem/10026bfs 문제.그냥 같은 구간이면 bfs를 돌려주었다.코드는 다음과 같다.

https://www.acmicpc.net/problem/1038백트래킹 문제.stoi를 사용해서 오류가 났었다.stoll(string to long long)을 알게된 문제.문제 접근감소하는 수를 순서대로 백트래킹 하기 어렵기 때문에,예제에서 50000번째

https://www.acmicpc.net/problem/11659구간 합 문제.처음에 투포인터로 풀었지만 TLE가 나서 구간 합을 알게 되었다.문제 접근구간합을 저장해주고 그 구간에 해당하는 $e$ $s$를 제외한 $1$~$s-1$를빼주고 출력한다.코드는 다

https://www.acmicpc.net/problem/9935TLE 때문에 시간을 많이 쓴 문제.연쇄적으로 폭발하는 경우를 고려해서 작성해야 했다.최악의 경우 반례:aaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbb

https://www.acmicpc.net/problem/2206전에 업로드 했던 글사실 이 문제는 처음에 해결하고 나서 조금 찜찜한 상태로 놔두었던 문제,두고두고 언젠가는 정복하겠다는 생각을 가지고 있었다.처음 풀 때보다 발전된 지금, 더 넓은 시야로 이 문

https://www.acmicpc.net/problem/2447재귀를 사용한 별 찍기 문제.문제 접근$3\\cdot3$ 형태를 가장 기본 형태로 취해 string vector의 행에 하나씩 넣는 방식을 채택.$3^k$ 꼴의 모양이 출력된 후 행의 조정이 필요

https://www.acmicpc.net/problem/11729하노이탑 문제.하노이탑 설명하노이탑의 규칙 특성상 가장 아래에 있는 원판을 옮기려면 위 원판을 옮겨야 한다.이 논리는 원판의 크기가 2인 원판까지 통해 재귀적으로 실행이 가능하다.일단 하노이탑의

https://www.acmicpc.net/problem/16139구간합 문제.문제 접근구간 내에 문자 $\\alpha$가 몇번 나오는지는 구간합과 유사한 방식으로구할 수 있기 때문에, 구간합으로 접근한다.$|S|\\cdot 26$의 배열이 필요했다.길이에 포

https://www.acmicpc.net/problem/2580백트래킹 문제.문제 접근스도쿠판의 빈칸들을 하나 하나씩 채워가며 백트래킹을 진행한다.이때 중요한 점은 빈칸을 1~9의 숫자로 채우지 못했을때그 조합은 실패한 조합이기 때문에 전 과정으로 돌아가서

https://www.acmicpc.net/problem/9251LCS(Longest Common Subsequence) 최장공통부분수열 문제.LCS 알고리즘최장공통부분수열은 어떻게 구할까?배우지 않았을때는 접근하기가 매우 어려웠다.LCS는 DP로 해결할 수

https://www.acmicpc.net/problem/11660구간 합 문제.문제 접근세로 구간합을 구해주고 범위 내 구간에 해당하는 값들을 더해 출력한다.코드는 다음과 같다.

https://www.acmicpc.net/problem/2630분할 정복이란 큰 문제를 여러가지 문제로 쪼개어해결할 수 있는 작은 문제들을 해결해 큰 문제의 답을구하는 문제 풀이 방법론이다.분할 정복을 사용한 예는 대표적으로 병합 정렬(merge sort)가

https://www.acmicpc.net/problem/1992분할 정복 문제.색종이 만들기와 유사한 문제이다.문제 접근출력 패턴을 보면 압축한 영상의 크기가 작아질때마다 괄호가 열리고,닫히는 것을 볼 수 있다.따라서 영상을 네 개로 분할할 때마다 괄호를 열

https://www.acmicpc.net/problem/10986구간합 문제.문제 접근어떤 구간합이 $M$으로 나누어 떨어질 때를 구해야 한다.근데 구간합은 $10^{15}$까지 되어 int 형으로는 커버되지 않는다.long long을 써도 되지만 메모리 사

https://www.acmicpc.net/problem/10026

https://www.acmicpc.net/problem/2252위상정렬 문제.문제 접근위상정렬 해주고 bfs를 돌려주면 된다.코드는 다음과 같다.

https://www.acmicpc.net/problem/1461그리디 문제.문제 접근이 문제의 핵심적인 그리디 해법은 가까운 지점부터 간다는 것이다.먼 지점부터 가게 되면 남은 책들이 남아있을때 가까운 지점을 먼저 가는 경우보다더 많이 걸어야하기 때문이다.코

https://www.acmicpc.net/problem/20500dp 문제.문제 접근15의 배수는 5의 배수이면서 3의 배수이다.5의 배수는 일의 자리수가 0 또는 5로 끝나야하며,3의 배수는 모든 자리수의 합이 3의 배수여야 한다.따라서 다음과 같은 점화식

https://www.acmicpc.net/problem/9082문제 접근지뢰의 배치는 확정되어 있기 때문에 확정된 위치를 큐에 넣고 bfs 돌려주었다.확정된 위치 란 0이거나 3 또는 지뢰가 다 결정된 경우를 말한다.기준을 가볍게 숫자가 낮을 때만 고르는 그

https://www.acmicpc.net/problem/15711정수론 문제.기본 지식골드바흐의 강한 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.에라토스테네스의 체소수 판별법 중 하나 :어떤 수 $N$에 대하여 $\\sqrt N$까지만 확인

https://www.acmicpc.net/problem/1987백트래킹 문제.문제 접근$i$번째 알파벳까지 왔을 때 어떤 알파벳이 사용되었는지 확인하기 위해bool 배열을 파라미터로 받아주었다.$(0,0)$부터 시작해서 백트래킹을 돌려주었다.코드는 다음과 같

https://www.acmicpc.net/problem/1202그리디 문제.문제 접근보석의 가격을 최대로 하여 담으려면,1\. 모든 가방에 최대한 담는다.2\. (반례가 있는 그리디한 방법)(1번을 충족시키기 위해) 현재 가방에 최대 무게를 담는다.3\. 1

https://www.acmicpc.net/problem/2812그리디 문제.문제 접근첫번째 방법 TLE크게 만들기 위해서는 가장 앞에 자리수부터 큰 수를 배정해야한다.이를 구현하기 위해 우선순위 큐에 pair<계수, 인덱스>(불가능한 경우를 탐색하기 위

https://www.acmicpc.net/problem/2056위상정렬 문제.문제 접근다른 위상정렬과 같이 1번 작업부터 N번 작업까지위상정렬 알고리즘을 수행해주면 된다.여태까지 위상정렬 알고리즘 문제를 풀 때에는 필요한 노드들을 기록하는벡터를 사용했었는데,

배낭 문제의 정해가 원래 평범한 배낭과 같다고 생각했는데, 백준 7579 앱을 풀면서 (처음에는 어디선가 본 배열 선언에 대한 제한 때문에 생각해 다른 방법을 찾게 되었다.) 정해를 알게 되어 글을 쓴다. 평범한 배낭 문제로 예를 들어보면, 원래 코드는 다음과

https://www.acmicpc.net/problem/2166벡터의 외적이란 벡터 곱 중 하나로써, 내적과는 다르게 스칼라 값이 아닌외적이 진행된 후에는 벡터값이 도출된다.두 3차원 벡터 $\\vec{a}=(a_1,a_2,a_3)$ 와 $\\vec{b}=(

https://www.acmicpc.net/problem/1520내리막 길과 굉장히 유사한 문제.내리막 길 문제를 푼지 어언 3달이 되어 잊어버려서, 대충 dfs로 접근했는데 TLE났다.문제 접근$(i,j)$칸이 칸의 길이가 더 추가될 여지가 있는 칸이면 그

https://www.acmicpc.net/problem/2987문제 접근어떤 점 하나가 $\\triangle ABC$에 속한다는 것을 생각해보았다.삼각형 위의 점 $A,B,C$에 대하여 시계방향, 반시계방향을 따졌을 때$A$보다 $X$좌표가 크거나 같거나,

https://www.acmicpc.net/problem/9370 최단경로 문제.

https://www.acmicpc.net/problem/25682이 문제는 체스판 다시 칠하기 1과는 다르게 $N,M$의 범위의상한이 $2000$이기 때문에 매번 $K\\cdot K$의 경우를 확인하면 TLE가 난다.따라서 다른 방법을 써야 하는데, 매번 확

https://www.acmicpc.net/problem/1941 쉬운 백트래킹 문제인 줄 알았으나, 여러가지 조건으로 인해 시간을 길게 보낸 문제. 처음에는 DFS를 돌려봤으나 어떤 중간지점에서 끊기는 경우는 탐지하지 못하였다. 따라서 다른 방법이 필요했다.

정말 풀고 싶었던 문제.문제 접근이 문제는 최소 경로로 가는 경우의 수가 여러가지여서많은 조건 분기를 사용해야했다.거리를 $dist=sqrt(x^2+y^2)$라 하자이 경우는 점프를 하면 오히려 손해이므로 그냥 걸어간다.이 경우는 점프 두 번에 도착, 점프 한 번만에

https://www.acmicpc.net/problem/1301문제 접근처음에는 단순하게 보고 백트래킹을 돌렸지만 TLE.다른 방법이 필요해 dp로 접근해보았으나,구슬의 개수를 모든 경우마다 카운트 정렬을 사용하는 것이 불가능했다.따라서 다른 방법을 써야 했

https://www.acmicpc.net/problem/14855꼼꼼히 살피지 않아 많이 틀린 문제.기본적인 배낭문제의 형태를 띄고 있으나,이 문제는 Bounded Knapsack Problem으로 알려져있다.Bounded Knapsack Problem은 0

https://www.acmicpc.net/problem/2110파라메트릭 서치 문제.이 문제는 다른 파라메트릭 서치 문제들과는 다르게조금 꼬인 느낌의 문제였다.문제 접근인접 공유기의 거리를 최대로 하려면 일단 두 공유기가 멀리 있어야 하는데,이는 다른 공유기

https://acmicpc.net/problem/2226dp문제.문제 접근각 이진수들을 살펴보면 항상 자기 자신 앞에 반대 수가 붙게 된다.이 성질은 모양 뭉탱이에게도 성립하는데,예를 들어$0110$ 은 항상 $10010110$이 된다.그리고 이를 통해 알

https://www.acmicpc.net/problem/27361처음엔 그리디인 줄 알고 헤메다가 태그 까고 DP로 풀었다.전형적인 배낭문제였지만,범위 계산 착오로 맞왜틀 당하고 복기 차에 글을 쓴다.!! 항상 범위를 꼼꼼히 계산하자 !!

https://acmicpc.net/problem/11570DP 문제.문제 접근DP 문제를 접하게 되면 처음에는 일차원 배열 DP를 배우게 된다.하지만 DP 방법론 특성상 다양한 형태의 점화식이 가능하기 때문에DP 문제를 일차원 배열로 푼다는 생각은 내려두고

https://www.acmicpc.net/problem/2157DP 문제.문제 접근간선의 개수가 최대 $1e5$이기 때문에 깡 BFS를 돌리면 결과는 TLE다.따라서 가능한 경우를 탐색하면서도 TLE가 나지 않는다른 방법인 DP를 사용해야 한다.$DP(i,j

https://www.acmicpc.net/problem/14807 https://www.acmicpc.net/problem/14808

https://www.acmicpc.net/problem/3257 DP 문제. 처음에는 그리디 접근했다가 시간을 많이 사용했다. 현재의 선택이 미래에 영향을 끼칠 수 있기 때문에 DP를 사용해야 한다. 비슷한 접근의 DP 문제와 비슷한 유형을 더 많이 풀어봐야

https://www.acmicpc.net/problem/1562큰 임팩트가 있었던 DP문제.앞으로 비트마스킹 문제를 더 많이 풀어봐야 할 것 같다.이전 쉬운 계단 수 문제와 난이도 차이가 꽤 나는 문제이다.0부터 9가 모두 등장하는 계단 수를 찾는 문제이다.

https://www.acmicpc.net/problem/11657벨만 포드 문제.벨만 포드를 구현해주면 된다.

https://www.acmicpc.net/problem/31849대회 때 못 푼 문제.문제 접근처음에는 모든 편의점에서 BFS를 시도했지만 TLE가 났다.따라서 다른 방법이 필요했다.문제 제한에서 $NM<=1e6$이 기 때문에 BFS를 각 편의점마다 수

https://www.acmicpc.net/problem/6549이 문제는 태그나 답지 도움 없이는 쉽게접근 할 수 없는 문제이다.더 많은 경험을 하는 것이 문제풀이에 도움이 될 것 같다.문제 접근히스토그램에서 가장 큰 직사각형이 존재하는 경우는 3가지이다.중

https://www.acmicpc.net/problem/1033문제 접근재료 a와 재료 b가 p와 q비율을 가지려면(편의상 a의 질량을 a, b의 질량을 b로 칭함)$a\\cdot q=b\\cdot p$ 그리고 $a/p=b/q$ 이다.문제 조건 중 하나인"필

https://www.acmicpc.net/problem/13974DP 문제.파일 합치기와는 달리 $O(n^3)$ DP로는 TLE를 받는다.따라서 크누스 최적화를 사용해 $O(n^2)$에 통과시켜야 한다.코드는 다음과 같다.

배경 지식 1. 확장 유클리드 알고리즘배경 지식 2. 모듈러 역원배경 지식 3. 페르마의 소정리오늘은 정말 많은 것을 배운 것 같아서 뿌듯하다.문제 내용은 간단하다 이항 계수 $n\\choose k$를 구하면 된다.하지만 n의 범위가 $4e6$이기 때문에 조합의 성질인

https://www.acmicpc.net/problem/1222팀당 인원은 무조건 참가하는 대학 인원들의 $GCD$로 설정해야 한다.$GCD$로 설정해야 남는 인원 없이 팀을 구성할 수 있기 때문이다.따라서 답은 $GCD(구성하는모든팀)$ $\\cdot\\;

https://www.acmicpc.net/problem/2517세그먼트 트리 문제.문제 접근자신보다 앞에 달리고 있는 선수이면서, 자신보다 평소실력이 낮은 선수가총 몇 명인지를 구하는 문제이다.답이 ( 현재 등수 - 자신보다 앞에 달리고 있는 선수이면서, 자

MITM이라고도 불리우는 Meet In The Middle 기법은많은 연산을 줄이기 위해 발명된 테크닉이다.https://www.acmicpc.net/problem/1450이 문제를 풀려고 할 때 모든 무게의 조합의 개수는$2^N$ 개 이므로 $(2^{30}\

https://www.acmicpc.net/problem/1280세그 문제.풀이 과정전에 심었던 나무들의 좌표를 관리 해야 하기 때문에 세그를 사용해전에 심었던 나무들의 좌표와 개수를 구해준다.현재 나무의 위치와 전에 심었던 나무들의 위치의 절댓값을 구하는 방

https://www.acmicpc.net/problem/1727DP 문제점화식이 LCS 문제와 유사했다.항상 유념하는 것이지만DP는 State를 잘 설정하는 것이 중요한 것 같다.(사실 이 부분이 DP 문제의 전부인 것 같다.)문제 접근우선 커플은 $min(

https://www.acmicpc.net/problem/1234DP 문제."같은 것이 있는 순열"을 복습하게 해준 문제이다.PS할 때 조합론 역시 중요하다는 것을 다시 한번 깨닫게 해준 문제.문제 접근$DPik$ 를 빨강 $i$, 초록 $j$, 파랑 $k$개

https://www.acmicpc.net/problem/1256DP 문제.역추적에 관한 지식을 더해준 문제이다.문제 접근$N,M$ 의 범위가 낮아 $NM$ DP 일거라고 예상하고끼워 맞추고 $DPi$ 를 $i,j$ 까지 봤을 때 경우의 수라고 두었다.DP 테

https://www.acmicpc.net/problem/11689 처음엔 포함 배제의 원리를 사용해 푸는 문제인 줄 알았으나 포함 배제 원리를 사용해서 푸려면 세어야 하는 경우가 너무 많아 TLE가 날 뿐더러 코드 역시 복잡하게 된다. 따라서 오일러 피함수에

https://acmicpc.net/problem/10412 거의 10개월 정도를 알고 지냈던 문제이다. 에디토리얼을 보고도 이해가 잘 되지 않아 풀다 안풀다 했던 문제이다. > 문제 접근 처음에는 $n,m$ 범위가 낮아 백트래킹을 시도해봤지만 당연히 TLE를

https://www.acmicpc.net/problem/1219

https://www.acmicpc.net/problem/9359 포함 배제의 원리를 사용하는 정수론 문제. 포함 배제를 사용해 풀고 있었는데 계속 WA를 받아서 답을 봤더니 포함 배제를 통한 접근이 맞아서 기분이 좋았다. 하지만 포함 배제하는 과정에서 부분 수

사실 이 글을 임시글에 담아놓은 지 1달 정도 되었으나 이제야 글을 쓴다. 피보나치 수열과 같이 구하는 값이 선형 점화식 형태를 띄고 있을 때 우리는 분할 정복을 이용한 행렬 거듭제곱을 빠른 시간 내에 구해 원하는 값을 구할 수 있다. 1. 피보나치 수 6 피

https://www.acmicpc.net/problem/9345세그 응용은 정말 다양해서 문제를 많이 풀어봐야겠다.문제 접근처음에는 공차가 1인 등차수열만 생각해서 합공식으로 접근하다가공차가 1이 아닌 등차수열을 생각하기 전까지 무한 WA를 받았다.따라서 새

https://www.acmicpc.net/problem/18118재미있었던 DP 문제문제 접근태그를 까고 나서 바로 접근이 생각났다$d(i,j,k)$를 $i$번째 세그먼트가 $j$이면서$\\mod m$ 값이 $k$인최대 자연수를 담는다고 하고 접근했다.이후