알고리즘

14503번: 로봇청소기 큐를 이용하여 청소가 끝나는 시점까지 반복문을 돌도록 해주었다. 입력 조건을 보면 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다. 라는 설명이 있다. 그래서 따로 맵의 끝 부분을 예외 처리 해주지 않았다. 이미 청소

1806번: 부분합 투포인터를 활용한 문제이다. start를 기준으로 반복문을 돌며 내부 반복문에서 end를 옮기며 S보다 합이 큰 연속된 부분합의 길이를 구했다. 그 후 더 짧은 길이의 부분합을 구하기 위해 end까지 start를 옮기고 발견하면 그 길이를 구하고

12904번: A와 B문제에서 S를 T로 바꾸는 두 가지의 조건을 알려준다.문자열의 뒤에 A를 추가한다.문자열을 뒤집고 뒤에 B를 추가한다이를 역순으로 T의 뒷 문자를 제거해가며 S로 바꾸는 방식으로 답을 찾았다.이번 문제는 그리디 치고는 생각보다 간단한 문제였다.

16234번: 인구 이동 단순한 BFS 문제에서 조금 더 생각을 해야하는 문제였다. 총 3가지의 루틴을 반복한다.

11054번: 가장 긴 바이토닉 부분수열바이토닉 부분 수열의 설명을 보고 우선 오름차순과 내림차순으로 나누어 답을 찾으면 되겠다고 생각했다.asc와 des로 나누어 부분 수열의 오름차순과 내림차순의 길이를 dp를 활용해 구해주었다. 그 후 두 길이의 합이 가장 큰 값을

14442번: 벽 부수고 이동하기 2BFS 변형문제이다. 우선 K에 맞춰 방문한 곳을 저장하기 위해 3차원 배열 visit를 사용했다. 반복문을 돌면서 방문하지 않은 곳이면 true로 바꿔주고 벽인 경우는 k 값을 올려서 큐에 push 해주었다. 이렇게 풀고도 계속해서

1005번: ACM Craft위상 정렬을 할 줄 안다면 어렵지 않게 풀 수 있는 문제이다. 나는 BFS를 통한 위상 정렬을 이용했다. 위상 정렬을 통해 처음부터 W까지 순차적으로 방문하면서 방문한 정점의 가중치, 즉 건설 시간을 누적으로 합하여 int dp\[1001]

1520번: 내리막 길dfs와 dp를 응용해서 푸는 문제이다. 단순히 dfs를 사용하여 상하좌우로 모두 탐색을 진행하게되면 시간 초과가 나오게 된다. 즉 dp를 사용해야 한다. 여기서 dp는 현재 위치에서 M-1, N-1까지 도달할 수 있는 경우의 수를 말한다. 탐색을

1753: 최단경로전형적인 다익스트라 알고리즘 문제이다. 다익스트라 개념만 알고 있다면 어렵지않게 풀 수 있다. 일반적인 배열을 사용한 방식을 이용하면 시간 초과가 나기 때문에 힙을 이용한 우선순위 큐를 사용한 방식으로 했다. 우선순위 큐의 우선순위는 내림차순을 기준으

7576번: 토마토간단한 BFS 문제였다. 큐에 좌표와 일수를 넣어 제일 마지막으로 나오는 일수가 총 걸린 일수가 된다. 다만 출력 조건을 자세히 봐야한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면

1238: 파티다익스트라 알고리즘을 이용하는 문제이다. 기존 다익스트라 문제와 다른 점은 각 정점의 왕복 최단 거리를 찾는 것이다. 왕복 거리를 구하기 위해 기존 다익스트라 알고리즘을 두번 사용하여 합을 구했다. 다익스트라 알고리즘을 알고 있으면 어렵지 않은 문제이다.

14890번: 경사로문제에서 제시해준 조건들에 맞춰 구현을 해주면 되는 문제이다. 조건은 4가지로 분류했다.다음 칸의 높이가 동일할 때다음 칸의 높이가 1만큼 높을 때다음 칸의 높이가 1만큼 낮을 때그 외의 경우먼저 배열을 입력받을 때 map2에 행열을 뒤집어서 저장해

1644번: 소수의 연속합소수를 응용한 투 포인터 문제이다. 문제 자체는 간단하다. 주어진 N까지의 소수를 구한 후 투 포인터를 이용해 합이 N과 같은 경우의 수를 찾으면 된다. 문제는 평소대로 소수를 구하면 시간 초과가 나게 된다. 여기서 필요한 것은 에라토스테네스의

11066번: 파일 합치기전형적인 메모이제이션을 활용한 동적 프로그래밍 문제이다. 오랜만에 dp 문제를 풀어봤더니 굉장히 오래걸렸다. 왜 dp를 사용하는지 질문 게시판에 굉장히 좋은 설명이 나와있었다. 이 설명을 참고하길 바란다. dp 문제를 더 자주 봐야겠다. 복습이

1937번: 욕심쟁이 판다처음 이 문제를 봤을 때 지도 위에서 상하좌우로 이동을 한다는 것을 보고 BFS라고 판단하고 알고리즘을 구상했다. 그러나 칸마다 최대 이동 개수가 정해져있으며, 단순한 BFS로는 시간 초과가 난다는 점에서 dp를 구상해야겠다고 판단했다. 우선

9466번: 텀 프로젝트처음에는 단순히 모든 학생들이 DFS를 돌며 팀이 완성되면 DFS를 돌지 않는 방식으로 구상하여 문제를 풀어보았는데 시간 초과가 났었다. 아무리 나름대로 최적화를 해주었다해도 계속 시간 초과가 발생해서 결국 구글링을 해보았다. 알고보니 접근 방식

12865: 평범한 배낭

1987번: 알파벳대충 보면 BFS문제처럼 보일 수 있지만 백트래킹을 이용한 DFS 문제이다. 문제에서 한번 방문한 종류의 알파벳은 방문할 수 없다고 명시되어 있기때문에 방문한 알파벳들을 저장할 필요가 있다. BFS로는 이부분이 힘들기에 DFS를 사용했다. visit배

2447번: 별 찍기 - 10분할 정복을 활용한 별 찍기 문제이다. 빈 칸이 나오는 경우의 패턴을 확인해보면 쉽게 문제를 풀 수 있다. 이번 문제 같은 경우는 정사각형의 중간 부분에 빈 칸이 찍히게 된다. n에 따른 빈칸 위치를 살펴보면 다음과 같다.이를 통해 i/(n

14500번: 테트로미노완전 탐색을 이용한 구현 문제이다. 문제를 보면 총 5가지 종류의 테트로미노가 존재하는데 거기다가 회전과 대칭까지 존재한다. 구현 자체는 어렵지 않지만 굉장히 귀찮은 문제였다. 다른 분들이 푼 것을 보니 DFS를 이용하여 문제를 푼 분들도 있던데

2146번: 다리 만들기이 문제의 경우 두가지 순서로 알고리즘을 구현할 수 있다.각 섬들에 번호 붙이기섬들간의 최단 거리 구하기각 섬들에게 번호를 정하는 부분이 findLand() 함수 부분이다. BFS를 이용해 붙어있는 땅들에게 번호를 붙여주는데 처음에 1로 주어졌기

9251번: LCS동적 프로그래밍을 활용한 최장 공통 부분 수열 구하기 문제이다. 사실 이 문제는 LCS 알고리즘으로 많이 알려져있는 문제이다. 그렇기에 어렵지않게 풀 수 있었다. 문자열의 크기만큼 반복문을 돌면서 같은 문자열을 발견하게 되면, 해당 위치의 LCS 배열

11049번: 행렬 곱셈 순서dp를 활용한 분할 정복 문제이다. 이 문제의 핵심은 점화식을 잘 세우는 것이다. 먼저 행렬의 곱 방식을 보자. 행렬 A (2,3), 행렬 B (3,4)가 있다고 할 때, 둘의 곱은 (2,4)가 되고 곱샘 횟수는 2 X 3 X 4가 된다.

2667번: 단지번호붙이기이전에 풀었던 다리만들기와 비슷한 문제이다. BFS와 DFS를 이용해 풀 수 있는데 이전의 정보를 저장할 필요가 없기에 BFS를 사용했다. 먼저 맵의 벽들을 -1로 바꿔주고 반복문을 돌면서 처음 만나는 -1에서 BFS를 돌렸다. BFS를 돌면서

10026번: 적록색약BFS를 이용한 간단한 문제이다. 문제에서 구해야하는 답은 적록색약이 아닌 사람과 적록색약인 사람이 봤을 때의 구역의 수이다. 그렇기에 BFS와 BFS2 함수 두가지를 사용하여 답을 구하였다. BFS2 함수는 적록색약을 대상으로하는 함수이기때문에

2206번: 벽 부수고 이동하기지난 번에 풀었던 벽 부수고 이동하기 2보다 쉬운 버전의 문제이다. 이전 문제와 굉장히 유사하게 풀었다. visit배열을 벽을 부순 유무를 추구한 3차원 배열로 구성하여 BFS를 돌면서 벽을 부수고 이동했는지 확인을 해주었다. 나머지는 기

15684번: 사다리 조작개인적으로 문제 이해가 좀 힘들었던 문제였다. 사다리에서 조작에 필요한 가로선 개수를 찾는 문제인데 우선 조건이 두가지 주어진다. 두 가로선이 연속하거나 서로 접하면 안 된다.가로선은 점선 위에 있어야 한다.사다리 위에서 조작에 필요한 위치를

7569번: 토마토3차원 배열에 BFS를 사용하는 문제이다. 일반적인 BFS문제에 z축이 생겼다고 보면된다. 모든 토마토가 익어있을 경우를 찾기 위해 처음에 bool변수를 이용해주었다. 그리고 BFS함수를 보면 z축을 따로 추가하여 BFS를 수행해주면서 며칠째인지는 c

16235번: 나무 재테크생각보다 시간이 오래걸린 구현 문제였다. 봄, 여름, 가을, 겨울을 K만큼 돌면서 마지막에 남은 나무의 갯수를 구하면 되는 문제이다. 조건들이 굉장히 많이 나오는데 유심히 봐야한다. 나는 처음에 모든 칸에 양분을 5만큼 준다는 조건을 보지 못해

2293번: 동전 1생각이 필요한 dp 문제이다. 주어진 동전을 이용해 k원이 될 경우의 수를 구하는 문제인데 처음에는 DFS를 사용했다가 시간 초과가 났었다. dp 배열 구조에 대해 말해보자면 아래와 같다.dp\[j] = i -> j원의 경우의 수 = i개dp\[j]

1699번: 제곱수의 합간단하게 접근했다가 생각을 많이하게된 문제이다. 자연수 N의 제곱수의 합의 최소 개수를 구해야한다. dp 배열은 각 숫자의 최소 개수를 나타낸다. 예를 들어보자. N = 5 라고 하면 최소 개수는 5 - 2 \* 2를 하면 1이므로 N = 1 의

1107번: 리모컨생각이 많이 필요했던 브루트 포스 문제이다. 버튼을 최소 몇번 누르는지 구하는 문제였는데 여러 조건들이 떠오르면서 생각이 많아졌었다. 우선 채널의 시작은 100번이라는 것, 그리고 101, 99와 같이 +, - 만으로 가는게 더 빠른 경우, 그리고 버

1149번: RGB거리색칠 비용의 최솟값을 구하는 dp문제이다. dp\[0]은 각 색칠 비용의 첫번째 값으로 초기화를 해주고 i=1부터 반복문을 돌려준다. 반복문을 돌면서 dp\[i]\[j]는 연속적으로 같은 색을 칠하지 않는 조건에 맞춰 색마다 현재 비용 + 이전 비

1695번: 숨바꼭질dp같아 보이는 bfs문제이다. N이 K에 도착했을 때 최소 시간을 구하는 문제로 처음에 dp로 접근해서 생각을 하느라 시간이 좀 걸렸다. 생각해보니 굳이 dp를 쓸게 아니라 bfs로 제일 먼저 K에 도착한 것이 최소 시간이 된다는 것을 깨닫고 bf

1916번: 최소비용 구하기다익스트라 개념을 물어보는 문제이다. 우선순위 큐를 사용하여 선형 탐색보다 더 빠르게 구할 수 있도록 하였다. 우선순위 큐는 기본적으로 내림차순으로 정렬되기 때문에 cost를 음수화하여 오름차순으로 정렬되도록 해주었다. 다익스트라 개념에 대해

1932번: 정수 삼각형간단한 dp 문제이다. 삼각형 값의 최댓값을 구하는 것이 목적이므로 현재 위치에서의 최댓값을 구해 더해나가야 한다. 현재 위치에서의 최댓값은 현재 위치까지의 합, 왼쪽 위 대각선 값 + 현재 위치 값, 오른쪽 위 대각선 값 + 현재 위치 값 중

2294번: 동전 2흔한 dp 문제이다. 최소 동전을 이용하여 합이 k가 되도록 만들어야 한다. dp는 dp\[합] = 최소 개수를 나타낸다. 즉 dp\[합] = min(dp\[합], dp\[합 - 동전] + 1)이 된다. 동전의 합으로 k를 나타낼 수 없다면 -1을

2225번: 합분해생각을 많이 해야 했던 dp 문제이다. 0부터 N까지 중 정수 K개의 합이 N이 되는 경우의 수를 구해야 한다. 중요한 점은 순서가 다르거나 중복되는 수를 사용해도 다른 경우로 샌다는 점이다. dp\[K]\[N] = 경우의 수로 dp를 구성하였다. 예

2580번: 스도쿠생각보다 어려웠던 문제였다. 9 X 9 사이즈 스도쿠를 풀면 되는 문제이다. 일단 0에 해당하는 좌표를 벡터에 저장을 해두고 백트래킹을 해주었다. 여기서 포인트가 두가지가 있다. 첫번째는 exit(0)이다. 문제에서 답이 여러가지가 나올 경우 한가지만

2156번: 포도주 시식조건들을 생각해야 했던 dp 문제이다. 최대로 마실 수 있는 포도주 양을 출력하되 3잔을 연속으로 마실 수 없는 조건이 있다. 여기서 dp는 dp\[n] = n번째 잔을 마실 때 최대 양이다. dp를 처음부터 채워나가보면 아래와 같다.n = 1

2638: 치즈시뮬레이션과 그래프 탐색을 적절히 섞은 문제이다. 치즈가 모두 녹는 시간을 구해야하며 치즈는 내부 공기가 아닌 외부 공기와 두 변 이상 접해있어야 녹는다. 우선 처음에 치즈에 해당하는 좌표를 v벡터에 저장해주고 반복문을 돌려준다. inside()합수에서

11404번: 플로이드플로이드 워셜 알고리즘 문제이다. 도시 간의 최소 비용을 구하면 되는 문제로 간단하게 풀 수 있다. 주의할 점은 출발 지점과 도착 지점이 같은 버스가 주어질 수도 있는데 이 때는 최소 비용이기에 더 낮은 비용의 값을 저장한다.

14891번: 톱니바퀴한 톱니바퀴가 회전하게 되면 인접한 톱니바퀴부터 회전할지 안 할지 결정해야 하므로 큐를 사용하여 나타내었다. 회전 조건 수 만큼 반복문을 돌면서 회전을 해주게 되는데 rotation이 회전을 해주는 함수이다. 함수를 보면 조건에 따라 큐에 추가해주

11729번: 하노이 탑 이동 순서하노이 알고리즘 알고리즘 구현 문제이다. 하노이 알고리즘은 워낙 유명하기 때문에 어렵지 않게 풀 수 있었다. 문제 제출 시에 시간 초과와 실패를 했는데 두가지 이유가 있었다.endl은 "\\n"보다 시간이 오래 걸린다. 참고cmath의

2565번: 전깃줄dp 응용 문제이다. 전깃줄이 교차하지 않게 하기 위해 없애야 하는 최소 개수를 구해야한다. 교차하지 않는 다는 것은 주어진 input을 왼쪽 값을 기준으로 정렬했을 때 오른쪽 값이 전보다 커야한다는 것을 의미한다. 즉 왼쪽을 정렬한 상태에서 오른쪽

7579번: 앱배낭 문제를 응용한 dp 문제이다. 배낭 문제는 최대 무게 내에서 최대 가치를 구하는 문제였던 반면, 이번 문제는 주어진 메모리를 넘겨 최소 비용을 구하는 문제이다. 점화식은 아래와 같다.dp\[앱 번호]\[비용] = 최대 메모리, 즉 i번째 앱까지 확인

13549번: 숨바꼭질 30-1 bfs를 응용한 문제였다. 0-1 bfs 유형은 처음이라 푸는데 시간이 오래 걸렸다. 수빈이의 위치에서 동생을 찾는 최단 시간을 구하면 되는데 이는 0-1 bfs 뿐 아니라 다익스트라로도 풀 수 있다. 0-1 bfs를 구현하기 위해 de

10844번: 쉬운 계단 수N이 주어졌을 때, N 자릿수에 해당하는 계단수의 갯수를 찾는 문제이다. N=2라고 생각해보자. 첫째 자리가 3일 경우, 둘째 자리에 올 수 있는 수는 2, 4이다. 즉 23, 43이다. N=3이면 둘째 자리는 2,4이고 2일 경우 셋째 자리

1197번: 최소 스패닝 트리크루스칼 알고리즘을 응용한 문제이다. 먼저 주어진 간선들을 오름차순으로 정렬을 해주고 가중치가 작은 간선부터 이어주기를 시작한다. 간선을 이어주던 중 만약 부모 노드가 같은 노드끼리 이어지게 되면 사이클이 발생하므로 부모 노드가 같은지 확인

5014번: 스타트링크bfs를 응용한 문제이다. S에서 G에 도달할 때 버튼 수를 찾으면 되는데 이 때 버튼은 U, D로 각각 위로 몇 층, 아래로 몇 층을 가는지 알려준다. 즉 D가 0이면 아래 층으로 갈 수 없다는 뜻이다. 먼저 S와 G를 입력받을 때 두 수가 같다

1991번: 트리 순회기본적인 트리 순회 문제이다. 전위, 중위, 후위 순회 결과를 순서대로 출력하면 된다. 먼저 입력받은 노드들을 숫자로 바꿔 node배열에 저장하였다. 순회는 재귀를 사용했으며 각 함수의 구조는 동일하지만 출력하는 위치가 다르다.오랜만에 본 순회 문

13023번: ABCDE문제에 주어진 조건을 만족하면 1, 아니면 0을 출력해주면 되는 문제이다. dfs를 이용해 조건에 해당하는지 확인을 해주었다. 관계를 입력받을 때 벡터를 이용하여 양방향으로 저장을 해주었다. 조건에 해당하는 처음 A를 0부터 n-1까지 대입해보면

11052번: 카드 구매하기전형적인 dp 문제이다. 배낭 문제와 같은 맥락으로 쉽게 풀 수 있다. 간단하게 풀 수 있었다.

1504번: 특정한 최단 경로다익스트라를 이용한 문제이다. 기존 다익스트라와 다른 점은 주어진 두 정점 v1, v2를 반드시 지나는 1부터 N까지의 최단 경로를 구하는 것이다. 이것은 두가지의 경우로 볼 수 있다.1 -> v1 -> v2 -> N1 -> v2 -> v1

1629번: 곱셈분할 정복을 이용한 문제이다. 거듭 제곱을 분할 정복을 활용하여 더 빠르게 구할 수 있다. 예를들어 2^8 = 2^4 \* 2^4와 같이 2를 8번 곱하는 것이 아닌 2를 4번 곱한 수끼리 곱하면 빠르게 값을 알 수 있다. 즉 아래와 같다.값이 long

2407번: 조합string을 활용한 조합 문제이다. 조합 자체를 구현하는 것은 어렵지 않지만 최댓값이 100이기 때문에 자료형을 long long으로 해줘도 오버플로우가 발생한다. 이를 해결하기 위해 파스칼 삼각형 점화식을 이용하여 이를 string으로 구현을 해주었

9465번: 스티커dp를 활용한 문제이다. 변을 공유하지 않는 스티커 점수의 합의 최댓값을 구해야한다. 합을 구하는 방법에는 두가지가 있다. n = 3의 최댓값을 구한다고 할 때, 방법은 아래와 같다.위의 두 합 중 큰 값을 구하여 dp에 저장하고 이를 반복하여 최댓값

1967번: 트리의 지름노드 간의 가장 긴 거리를 구하는 문제이다. dfs를 사용했다. 먼저 경로들을 벡터에 양방향으로 저장을 해주고 노드의 갯수만큼 반복문을 돌려주었다. dfs 함수에서 경로를 따라 sum을 구해 res와 비교 후 더 큰 값을 저장해주었다. 최종적으로

1043번: 거짓말dsu를 활용한 문제이다. 크루스칼 알고리즘에서 활용된 find-union 방식을 활용하여 진실을 아는 사람이 포함된 파티들을 확인하였다. 각 파티의 첫번재 번호가 부모가 되고 이를 parent배열에 표시해주었다. 각 파티마다 반복문을 돌면서 진실을

2096번: 내려가기dp를 활용한 문제이다. 다음 줄의 인접한 인덱스로 내려가면서 더한 최대 점수와 최소 점수를 구하면 된다. tmp와 dp 두 배열을 이용하여 문제를 해결했다. 처음 dp 배열에 A 배열의 첫 줄을 저장하고 maxSum 함수에 들어간다. 함수 내에서

1717번: 집합의 표현dsu를 활용한 문제이다. find-union 방식을 알고 있다면 어렵지 않게 풀 수 있는 문제이다. 문제에서 주어지는 집합을 합치는 경우는 루트를 union하는 값으로 바꿔주는 방식으로 저장하였다. 만약 두 값이 같은 집합 내에 있다면, 두 값

17298번: 오큰수스택을 활용한 문제이다. 오큰수를 주어진 수열 뒤부터 구하는 방식으로 풀었다. 반복문을 활용해 수열 뒤부터 접근을 시작하며 스택이 비엇는지 확인한다. 여기서 스택은 오큰수 후보들을 저장할 곳으로 사용되며 오름차순에 해당하는 값만 저장된다. 오큰수는

2468번: 안전 영역bfs를 활용한 문제이다. 장마철에 잠기는 높이가 주어지지 않기 때문에 0부터 최대 높이까지 모두 구해봐야한다. 0부터 구하는 이유는 비가 안 올 경우도 존재하기 때문이다. 구해야하는 값은 물에 잠기지 않은 구역의 갯수의 최댓값이므로 bfs를 이용

1516번: 게임 개발위상 정렬을 이용한 문제이다. 모든 건물의 최소 시간을 구하면 된다. 기존 위상 정렬 방식을 그대로 사용하였다. 입력을 받아온 값들을 bfs를 통해 값들을 구해나가 출력하였다.기존에 풀었던 백준 1005 ACM Craft (C++)와 굉장히 유사한

17070번: 파이프 옮기기 1알고리즘 분류에 dp가 포함되어 있지만 dp를 활용하지 않고 문제를 풀었다. bfs를 이용하여 답을 구했다. 큐에 현재 위치와 파이프 방향을 저장하고 반복문을 돌면서 (N-1,N-1)에 도달하는 개수를 저장하여 출력하였다. 파이프는 오로지

2110번: 공유기 설치이분 탐색을 이용한 문제이다. 시작과 끝을 집 양 끝으로 두고 반복문을 시작한다. 반복문을 돌면서 mid를 구해 집 간 거리가 이보다 크면 카운트를 한다. 만약 카운트가 C보다 크면 mid값을 키우기 위해 start를 옮겨주고 반대면 end를 옮

11444번: 피보나치 수 6

11053번: 가장 긴 증가하는 부분 수열dp를 활용한 문제이다. 반복문을 돌면서 수열을 차례로 접근하면서 현재 위치를 기준으로 그 이전의 값들 중 작은 값을 찾아 카운트하여 dp에 저장하였다. 그 중 가장 큰 dp값을 구해 출력해주었다.이전에 풀었던 가장 긴 바이토닉

9019번: DSLRbfs를 이용한 문제이다. 우선 문제에서 주어지는 D, S, L, R을 각각 구현해주었다. 그 후 bfs를 통해 A = B가 되는 시점을 찾아 출력해주었다. 가장 먼저 A = B가 되는 시점이 최소한인 시점이므로 바로 출력해주었다.처음 L과 R을 구

1992번: 쿼드트리분할 정복을 이용한 문제이다. 먼저 반복문을 돌면서 n 크기만큼 합을 구해 모두 0 또는 1로 되어있는지 확인한다. 모두 0 또는 1로 되어있지 않다면 4 구역으로 나누어 다시 함수를 호출하고 이를 반복한다.어렵지 않게 풀 수 있었던 문제였다. 생각

2589번: 보물섬bfs를 이용한 문제이다. 먼저 주어진 지도를 입력받을 때 땅을 1, 바다를 0으로 저장하였다. 그리고 각 위치에서의 최단 거리를 구하기 위해 반복문을 돌며 땅에 해당하면 모두 bfs를 사용했다. bfs에서는 반복문마다 res에 최단 거리를 저장하여

2133번: 타일dp를 이용한 문제이다. 먼저 점화식을 생각해내야 한다. 2x1 타일로 채우기 때문에 n이 홀수인 경우는 다 채울 수 가 없다. 즉 n이 짝수인 경우를 생각해야한다. n = 2 일 경우, 경우의 수는 3가지n = 4 일 경우, n = 2 경우의 수 \*

1068번: 트리dfs를 이용한 문제이다. 처음 입력받을 때 vector를 활용해 부모 노드에 자식 노드를 차례대로 저장해주었다. 그 후 dfs를 통해 지워지는 노드인 M과 자식 노드들을 제거해주고 자식 노드로 M을 가지는 노드를 찾아 제거해주었다. 자식 노드가 없는

11057번: 오르막 수dp를 이용한 문제이다. 점화식을 먼저 생각해 봐야한다. 아래 표를 통해 도출해볼 수 있다.행은 N에, 열은 맨 앞자리 수에 해당한다. 에를 들어 dp2일 경우, 길이가 2이고 맨 앞자리가 9인 오르막 수의 갯수가 10개에 해당한다. 이를 점화식

1922번: 네트워크 연결최소 스패닝 트리를 이용한 문제이다. 이전에 풀었던 MST와 알고리즘이 완전 똑같다고 볼 수 있다. 중요한 점은 정렬을 통해 비용이 낮은 순부터 합쳐주어 결과적으로 최소 비용이 나온다는 점이다.MST를 떠올리지 못하고 알고리즘 분류를 보고 생각

2470번: 두 용액투 포인터를 이용한 문제이다. 문제에서 요구하는 것은 합이 0에 가까운 두 용액을 구하는 것이다. 그래서 우선 입력받은 값들을 정렬을 해주어 첫번째 값과 마지막 값을 시작으로 합을 구해가며 반복문을 돌려주었다. 만약 두 용액의 합이 음수라면 star

17135번: 캐슬 디펜스구현 문제이다. 아래 알고리즘이 복잡해 보이지만 크게 3가지 단계의 반복으로 볼 수 있다.궁수 3명을 배치한다.궁수를 기준으로 D 거리 안의 적을 왼쪽부터 공격한다.적이 한칸 앞으로 온다. 이 때 N-1 위치에 있는 적은 사라진다.궁수 3명을

1260번: DFS와 BFSdfs와 bfs를 할 줄 아는가 묻는 문제이다. 정점과의 연결을 벡터로 저장해주고 dfs와 bfs를 돌려주었다. 현재 정점과 연결된 정점이 여러 개인 경우 번호가 작은 정점부터 방문하도록 오름차순으로 정렬을 해주었다. dfs와 bfs를 돌면서

12100번: 2048 (Easy)2048을 구현하는 문제이다. 우선 상하좌우를 구현해주었다. 현재 위치 다음 값이 0일 경우 다음으로 이동시켜주고, 현재 위치와 같은 값이면 두 값을 합쳐주고 현재 위치를 0으로 바꿔준다. 여기서 주의할 점은 한번의 이동 내에서 한번

11403번: 경로 찾기플로이드-워셜을 이용한 문제이다. 반복문을 돌면서 A\[i]\[k]와 A\[k]\[j]의 간선이 존재한다면 A\[i]\[j]에 1을 저장해주고 출력해주었다.플로이드-워셜 알고리즘을 풀어본 적이 있어서 간단하게 풀 수 있었다.

2583번: 영역 구하기bfs를 이용한 문제이다. 먼저 주어지는 직사각형의 위치에 해당하는 곳을 true로 바꿔주었다. 그 후 반복문을 돌며 false인 위치를 찾아 이를 카운트한 후 bfs를 해주었다. bfs를 하면서 사이즈를 카운트해 벡터에 저장해주었다. 영역의 개

5639번: 이진 검색 트리이진 트리를 이용한 문제이다. 먼저 전위 순회로 입력되는 값을 트리를 구현하여 저장해주었다. 그 후 후위 순회로 값들을 차례로 출력해주었다.처음에는 배열로 노드를 구성하여 이를 순회하며 출력해주었는데 아웃바운드가 발생했다. 이유는 값이 많아질

2011번: 암호코드dp를 이용한 문제이다. 점화식을 잘 세우면 빠르게 풀 수 있다. 문제에 주어진 예시가 힌트였다. 1111111111을 차례대로 생각해보자.1 : 1개11 : 2개111 : 3개1111 : 5개11111 : 8개 즉 dp\[n] = dp\[n-2]

16928번: 뱀과 사다리 게임bfs를 이용하는 문제이다. 먼저 사다리와 뱀의 위치와 이동하는 위치를 배열에 저장해주었다. 그 후 bfs를 돌면서 위치를 이동시켜주며 카운트해주었다. 처음 100에 도달할 때 카운트를 저장한 후 출력해주었다.처음에는 백트래킹으로 접근하여

11286번: 절댓값 합우선순위 큐를 이용하는 문제이다. 우선순위 큐를 선언할 때 pair를 사용해 절댓값과 원본값을 저장해주었고 오름차순으로 정렬되도록 greater를 추가해주었다. 이렇게되면 top에 절댓값과 원본값이 가장 작은 값이 있게되고 이를 출력 후 pop해

11758번: CCWCCW 알고리즘을 이용한 문제이다. ccw 알고리즘을 사용한 값을 구했을 때, 양수이면 반시계, 음수이면 시계, 0이면 일직선이 된다. 이에 맞춰 출력해주었다.ccw 알고리즘이란 것을 처음 알게 되었다. 기하학관련 알고리즘은 처음이었다. 기억해두자.

11000번: 강의실 배정우선순의 큐를 이용한 문제이다. 먼저 시작과 종료 시간을 벡터로 입력받은 후 정렬을 해준다. 이 후 우선순위 큐를 이용해 반복문을 돌며 그리디 알고리즘을 사용한다. 종료 시간을 우선순위 큐에 넣고 현재 위치의 시작 시간과 우선순위 큐의 top과

1707번: 이분 그래프이분 그래프를 dfs를 이용하여 나타내었다. 먼저 간선에 대한 정보를 벡터에 입력받아 저장해준 후 벡터 전체를 돌며 color가 0인 경우 dfs를 돌려주었다. dfs는 백터를 따라 색을 칠해주게 되는데 1과 -1을 번갈아가며 칠해준다. 반복문을

2573번: 빙산bfs를 이용한 문제이다. 과정은 아래와 같다.빙산이 모두 녹았는지 확인한다.빙산이 두덩이 이상으로 분리되었는지 확인한다.빙산을 녹인다.반복문을 이용해 위의 과정을 반복해주었다. 빙산이 모두 녹았는지는 백터를 이용해 확인해주었다. 처음 입력값을 받을 때

17142번: 연구소 3bfs를 응용해서 풀어야하는 문제이다. 우선 문제를 잘 이해해야한다. 입력값으로 활성화된 바이러스 수 만큼만 bfs를 해주어야하므로 조합으로 바이러스를 선택해야한다. 이를 dfs로 구현하해주어 카운트가 M과 같을 경우 bfs를 해주었다. 여기서

2467번: 용액투포인터를 이용한 문제이다. 입력 값을 받을 때 정렬된 형태로 값을 받기 때문에 따로 정렬을 해 주지 않고 투포인터를 해주었다. 투포인터를 통해 절댓값이 최소가 되는 위치를 찾은 후 출력해주었다.이전에 풀어본 문제와 유사했기 때문에 금방 풀 수 있었다.

11779번: 최소비용 구하기 2다익스트라를 이용하는 문제이다. 간단한 다익스트라 구현 문제이다. 여기서 추가된 점은 최소비용을 가지는 노드들을 출력해야 한다는 점이다. 이부분은 다익스트라 과정에서 이전의 인덱스를 저장하여 해결하였다. index 배열은 이전의 위치를

1389번 케빈 베이컨의 6단계 법칙플로이드-워셜을 이용한 문제이다. 플로이드-워셜을 구현하여 배열에 각 유저간의 최소 거리를 구하고 저장해주었다. 그 후 반복문을 돌며 각 유저간의 최소 거리를 더해주고 그 중 합이 가장 작은 유저를 출력해주었다.간단한 문제였다. 플로

5557번: 1학년dp를 이용한 문제이다. 단순 완전 탐색으로 문제를 풀게 되면 겹치는 구간이 많이 생겨 시간 낭비가 생긴다. 예를 들어 5,2,2라고 할 때, 5-2+2 와 5+2-2 의 값은 같은데 두번 탐색하게 되고 이것이 반복되면 시간 초과가 일어난다. 그래서

9205번: 맥주 마시면서 걸어가기bfs를 활용한 문제이다. 문제 조건인 20병의 맥주를 들고 50m마다 한 병씩 마신다.는 최대 1000m를 갈 수 있다는 것을 의미한다. 이를 토대로 너비 우선 탐색 방식을 사용했다. 즉 로직은 아래와 같다.현재 거리에서 페스티벌까지

2166번: 다각형의 면적이전에 풀었던 ccw를 활용한 문제이다. ccw를 이용해 3점의 외적을 구하는 과정을 반복하고 이를 모두 더해주었다.3점의 외적을 구하는 방식이기 때문에 겹치는 부분이 발생하므로 2로 나누어주고 방향에 따라 음수가 나올 수 있기때문에 절댓값으로

1038번: 감소하는 수완전 탐색을 활용하여 문제를 풀었다. d\[N]는 N번째 감소하는 수를 의미한다. 예를 들어 42?의 경우, 물음표에는 0과 1 즉 2개가 올 수 있다. 이를 통해 10으로 나눈 나머지만큼 감소하는 수가 있다는 것을 알 수 있다. 반복문을 통해

1926번: 신입 사원그리디를 활용한 문제이다. 먼저 서류심사 성적 순위 순으로 정렬을 한 후, 반복문을 돌면서 면접 성적 순위를 비교하여 순위가 더 높을 경우 카운트를 해주었다. 알고보면 간단한 문제였지만 문제를 이해하지 못해서 시간이 오래 걸렸다....

1309번: 동물원dp를 활용한 문제이다. 우선 하나씩 그려보면서 경우의 수를 N=1부터 세어보았다.N=1, 경우의 수는 3N=2, 경우의 수는 7N=3, 경우의 수는 17N=4, 경우의 수는 41N일 때 경우의 수를 dp\[N]이라고 한다면 점화식은 아래와 같다.dp

6064번: 카잉 달력최소공약수를 이용하여 해결한 문제이다. 문제를 보면 x나 y가 M, N을 넘어가면 1로 돌아간다고 되어있다. 즉 x를 M으로 나눈 나머지가 x가 된다는 뜻이다. y도 마찬가지이다. 달력의 마지막 해는 두 수의 최소공배수를 의미하므로 먼저 최소공배수

프로그래머스 캠핑 Level32017 카카오코드 예선 문제이다. 이 문제를 풀 때는 문제를 이해하는데 시간이 오래 걸렸다. 주어지는 두 좌표가 텐트의 대각선에 해당한다는 점을 잘 이해해야한다. 먼저 x 좌표를 기준으로 정렬을 한 후, 반복문을 돌면서 하나씩 비교를 해가

2504번: 괄호의 값간단한 구현 문제이다. 반복문을 통해 문자열을 차례대로 접근하면서 (이거나 \[일 경우 스택에 넣어주고 해당하는 괄호의 값을 곱해주었다. 그리고 )이나 ]일 경우 먼저 올바른 괄호인지 확인을 한 후 바로 이전이 여는 괄호였다면 answer에 더해주

9953번: 문자열 폭발스택을 이용한 문제이다. 나는 string을 스택 방식으로 사용하여 풀었다. 주어진 문자열 크기 만큼 반복문을 돌며 answer에 한 단어씩 push_back을 해준. 이때 현재 단어가 bomb의 마지막 단어와 같고 answer의 크기가 bomb

20055번 컨베이어 벨트 위의 로봇문제가 까다로웠던 구현 문제이다. 문제 자체 구현에는 어렵지 않았다. 4가지 순서를 메소드로 나누어 구현해준 후 이를 반복문을 돌며 몇단계인지 카운트해주었다. 문제는 역시나 이번에도 !! 문제 이해였다. 나는 처음에 올리는 위치만을

20946번: 합성인수분해소인수분해 관련 문제이다. 문제에서는 합성인수분해가 여러개일 경우 사전 순으로 가장 앞서는 것을 출력하다고 되어있다. 그래서 먼저 소인수분해를 구한 후 이를 P(0)\*P(1), P(2)\*P(3) ... 과 같은 방식으로 출력해주었다. 만약

15685번: 드래곤 커브좌표 위의 점의 이동을 구현하는 문제이다. 각 세대마다 이전 세대는 시계 방향으로 90도 회전시킨 후 끝 점에 이어 붙인다. 점을 90도 회전하는 공식은 (xcosθ - ysinθ, xsinθ + ycosθ)를 사용했다. 90도를 회전하므로 회

15486번: 퇴사2dp를 활용한 문제이다. 보통 기간이 주어진 문제의 경우 나는 뒤에서 부터 접근을 먼저 시작해본다. 역시 맞았었다. N-1부터 시작하여 반복문을 돌면서 dp에 해당 위치의 최고 금액을 저장해주었다. 간단하게 풀 수 있었던 문제였다.

13273번: 로마숫자문자열을 활용한 구현문제이다. 숫자로 주어질 경우와 문자열로 주어질 경우 두가지 경우가 있다. 두가지 경우를 나누어 알고리즘을 작성하였다. 먼저 숫자의 경우 자릿수만큼 반복문을 돌며 비교하여 각각 해당하는 문자를 result에 넣어주었다. 만약 4

12781번: PIZZA ALVOLOC선분 교차 판정을 이용한 문제이다. 선분 교차를 확인하는 법은 ccw를 이용한다. 한 점을 기준으로 다른 두점과의 직선 방향을 ccw를 이용해 구했을 때 서로 방향이 다르다면 선분이 교차함을 의미한다. 원래는 추가로 다른 한 점을

2531번: 회전 초밥완전 탐색을 통해 결과를 구한 문제이다. 문제 유형은 두 포인터로 되어 있는데 사실 슬라이딩 윈도우에 더 가까운 문제이다. 처음에는 중복 제거를 위해 set을 통해 원소들을 저장해 최대 크기를 구하는 방식으로 알고리즘을 구현했었는데 시간 초과가 났

1890번: 점프dp를 활용한 문제이다. 처음에는 bfs로 접근을 했는데 이 문제는 bfs로는 풀 수가 없는 문제이다. 이유는 여기에 어떤 분이 정리를 잘 해주셨다. 후에 dp로 접근을 했다. 해당 좌표에 몇번 접근했는지 카운트를 해서 더해주면서 최종 카운트를 출력해주

1643번 쿠폰확룔을 이용한 구현 문제이다. 출력을 구현하는 것 자체는 쉬웠는데 확률 공식을 찾는데 오래... 굉장히 오래 걸렸다. 공식은 이 사이트를 참고했다. 사이트의 공식을 분수와 분자를 각각 구하는 알고리즘으로 구현한 후 이를 형식에 맞추어 출력해주었다. 확률과

2725번: 보이는 점의 개수유클리드 호제법으로 최대 공약수를 구해 푸는 문제이다. 먼저 gcd를 구현하고 N = 1000까지 최대 공약수가 1인 값들을 true로 두는 배열을 구해주었다. 그리고 입력받은 N까지 개수를 구해 출력해주었다. 간단히 풀 수 있었던 문제였다

15991번: 1, 2, 3 더하기 6dp를 이용한 문제이다. 점화식은 간단하다. 아래와 같다.1, (N - 2), 1 -> 양 옆이 1인 경우2, (N - 4), 2 -> 양 옆이 2인 경우3, (N - 6), 3 -> 양 옆이 3인 경우즉 dpN = dpN - 2

2668번: 숫자고르기dfs를 이용한 문제이다. 기존 dfs와 다른 점이라면 조건을 만족할 때 지나온 값들을 모두 정렬하여 출력해야 한다는 점이다. 그래서 중복을 제거해주고 정렬을 해주는 set을 이용했다. 1부터 N까지 반복문을 돌면서 dfs를 해준다. dfs를 하면

2023번: 신기한 소수백트랙킹을 통해 소수를 찾는 문제이다. 이 문제에서 주의해야 할 점은 메모리이다. 처음에 에라토스테네스의 체를 이용해 8자리 까지의 소수를 미리 모두 구한 후 조건에 만족하는 소수를 찾아주는 방식으로 문제를 접근했더니 메모리 초과가 나왔었다. 메

1012번: 유기농 배추bfs를 이용한 문제이다. 배추가 심어져 있는 위치를 check에 true로 저장을 해주고 밭의 크기만큼 반복문을 돌면서 현재 위치가 true 일 경우 bfs를 돌려준다. bfs를 통해 true를 모두 false로 바꿔주고 이를 반복하며 카운트해

2251번: 물통bfs를 이용한 문제이다. bfs를 구현하여 물을 옮기는 경우의 수에 맞춰 물을 옮기면서 A 물통이 비었을 경우의 C 물통의 물 양을 저장해주면 된다. 문제자체는 어렵지 않게 해결할 수 있었다. 다만 경우의 수를 어떻게 반복문으로 표현할 지 떠올리는데

6593번: 상범 빌딩bfs를 이용한 문제이다. 이번 문제는 기존 bfs와 다르게 주어지는 맵이 3차원으로 이루어져 있다. 그래서 이동 방향이 동,서,남,북,상,하 6가지가 된다. 맵을 입력받을 때 S와 E를 찾아 위치를 저장해주고 bfs를 돌려준다. 최초로 E 좌표에

6588번: 골드바흐의 추측에라토스테네스의 체를 이용한 문제이다. 에라토스테네스의 체를 먼저 이용해 최댓값까지의 소수를 모두 구해주고 시작하였다. 반복문을 돌면서 현재 소수일 경우 n - i 또한 소수인지 확인한 후 소수이면 이를 출력해주었다. 문제자체는 어렵지 않았지

14719번: 빗물간단한 구현 문제이다. 현재 위치를 기준으로 왼쪽과 오른쪽에서 각각 가장 큰 수를 구해 현재 위치의 값과의 차이를 구해준다. 이를 반복하여 결과를 구해주었다.

1926번: 그림bfs를 이용한 문제이다. 반복문을 돌면서 A 배열이 true일 경우 bfs를 돌려주며 넓이를 계산해주고 큰 값을 저장해주었다. 동시에 그림의 개수도 카운트 해주었고 넓이와 갯수를 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.

12852번: 1로 만들기 2dp를 이용한 문제이다. 먼저 배열 dp에 dp\[1] = 0, 나머지는 큰 값으로 초기화 해주었다. N에서 1이 아니라 1에서 N 순서로 반복문을 돌면서 최솟값을 구해주었다. 각 조건에 맞을 경우의 최솟값을 구해주고 1을 더해주는 것을 반

5582번: 공통 부분 문자열LCS를 응용하여 풀었다. 문자열 크기만큼 반복문을 돌면서 같은 문자일 경우 이전 문자 카운트 + 1을 배열에 저장해주고 result 보다 클 경우 이를 result에 저장한 후 출력해주었다. 오랜만에 LCS도 상기시켜준 좋은 문제였다.

3055번: 탈출bfs를 이용한 문제이다. 특이한 점이라면 bfs를 통해 좌표를 이동하는 것이 여러 개라는 점이다. 맵을 입력받을 때 돌, 시작 지점과 굴의 좌표를 먼저 저장해주었다. 고슴도치의 위치와 물의 좌표를 큐에 넣을 때 물의 경우 카운트를 -1로 넣어주고 bf

10986번: 나머지 합누적 합을 이용한 문제이다. 먼저 배열을 입력받을 때 누적 합들을 구해 S에 저장을 해주었다. 그 후 M과의 나머지 각각의 수를 rem에 카운트를 해준다. 여기서 나머지가 0이 되는 (i, j)를 찾아주면 된다. 만약 (S\[j] - S\[i])

2519번: 부등호백트래킹을 이용한 문제이다. 재귀를 통해 입력받은 부등호 조건에 만족할 경우 s에 숫자를 추가해주고 s의 크기가 k + 1과 같아질 경우 최댓값과 최솟값을 갱신해준다. 그 후 백트래킹을 통해 다음 숫자를 대입해보며 갱신을 해준 후 출력해주었다. 어렵지

2212번: 센서그리디를 이용한 문제이다. 집중국이 K 개라면 집중국 사이의 공백은 K - 1개가 된다. 주어진 센서 간의 거리를 구해 저장해준 후 이를 내림차순으로 정렬해 공백 개수인 K - 1 개를 제외한 나머지의 합을 출력해주면 된다.3 6 7 8 10 12 14

21608번: 상어 초등학교로직을 구현하는 문제이다. 문제에 있는 3가지 단계를 직접 구현을 해주면 된다. 학샏 수 만큼 반복문을 돌며 이를 3가지 step으로 나누어 진행하였다. 각 step마다 자리 전체를 반복문을 돌며 각 조건에 맞을 경우를 count하여 이 때의

1325번: 효율적인 해킹dfs나 bfs를 이용한 문제이다. 주어지는 신뢰하는 관계를 먼저 vector에 차례대로 저장해주었다. 그리고 각 인덱스에서 탐색을 하면서 카운트를 해주어 저장해주었고 최댓값을 가지는 인덱스를 출력해주었다. 이 문제는 dfs와 bfs 두가지 방

5525번: IOIOI문자열을 이용한 문제이다. 반복문을 돌면서 I 인 경우 while을 실행한다. while문을 돌면서 s\[i + 1] == 'O', s\[i + 2] == 'I'가 만족할 경우 카운트를 해주고 이를 반복한다. 어렵지 않게 풀 수 있었다.

1080번: 행렬그리디를 이용한 문제이다. 풀이는 단순하다. 반복문을 돌면서 배열 A와 B의 현재 위치 값이 다를 경우 현재 위치에서의 3x3만큼 A를 바꿔주면서 횟수를 카운트해주었다.. 그 후 A와 B를 비교한 후 같을 경우 횟수를 출력하고 다를 경우 -1을 출력했다

1743번: 음식물 피하기bfs를 이용한 문제이다. 풀이는 간단하다. 입력받은 음식물 위치들을 반복문을 돌면서 bfs를 돌려준다. bfs를 통해 연속으로 이어진 음식물의 개수를 카운트하여 이를 result와 비교하여 큰 값을 저장해주었다. 그 후 result를 출력해주

1850번: 최대공약수유클리드 호제법을 이용한 문제이다. 먼저 주어지는 A와 B의 자릿수의 최대공약수를 구해준다. 그리고 구한 수 만큼 반복하여 1을 출력해주었다. 쉽게 풀 수 있었던 문제였다.

3020번: 개똥벌레이분 탐색과 누적 합을 이용한 문제이다. 먼저 문제 조건을 잘 읽어봐야 한다. N과 H가 주어지고 N 만큼 석순과 종유석이 번갈아 주어지게 된다. 이를 각각 s와 j 배열에 해당 위치마다 카운트를 해주었다. j는 종유석이기 때문에 높이에서 뺀 만큼

2343번: 기타 레슨이분 탐색을 이용한 문제이다. 로직은 주어지는 강의 길이를 모두 더하고 이를 이분 탐색을 하며 최솟값을 구하는 방식이다. 이분 탐색을 진행하면서 반복문을 돌며 mid와 비교하여 카운트를 해준 뒤 카운트가 M보다 크지 않다면 result와 비교하여

2805번: 나무 자르기이분 탐색으로 분류되어있지만 이분 탐색을 사용하지 않고 문제를 풀었다. 먼저 벡터에 입력값들을 받은 후 오름차순으로 정렬을 해주었다. 그 후 벡터의 맨 마지막 값, 즉 가장 긴 나무의 길이를 따로 저장해준 뒤 반복문을 이 길이를 시작으로 0까지

1747번: 소수&팰린드롬에라토스테네스의 체를 이용하여 푸는 문제이다. 먼저 에라토스테네스의 체를 이용하여 소수를 구해주었다. 그 후 반복문을 돌면서 소수인 수 중에서 팰린드롬에 해당하는지 확인을 한 후 해당하면 저장을 한 후 출력해주었다. 로직 자체는 어렵지 않은 문

15903번: 카드 합체 놀이그리디 알고리즘을 이용한 문제이다. 가장 작은 점수를 출력하기 위해서는 카드 합체를 진행할 때 작은 값끼리 진행해야 한다. 그래서 오름차순으로 정렬해주는 우선순위 큐를 사용하였고 이를 내림차순으로 바꾸어 저장해주기 위해 -1을 곱해 저장하였

2170번: 선 긋기정렬을 이용한 문제이다. 먼저 입력받은 시작 점과 끝 점들을 오름차순으로 정렬해주었다. 그 후 반복문을 돌며 조건에 맞춰 s와 e를 바꾸어주었다. 조건은 3가지가 될 수 있다.1 4, 3 5 와 같이 일부가 겹처져 있는 경우1 4, 2 3 과 같이

13398번: 연속합 2dp를 이용한 문제이다. 이 문제에서는 dp 배열을 두개를 구해주었다. 먼저 왼쪽에서부터 연속된 합의 최댓값을 구하는 dp 배열을 구해주고 오른쪽에서부터 최댓값을 구하는 dp 배열을 구해주었다. 그 후 수를 제거하지 않았을 경우부터 최댓값을 구해

14002번: 가장 긴 증가하는 부분 4dp를 이용한 문제이다. 먼저 반복문을 돌면서 가장 긴 길이와 그에 해당하는 인덱스를 dp를 이용해 구해준다. 그리고 반대로 반복문을 돌면서 len을 1씩 빼면서 dp와 비교하여 같을 경우 벡터에 저장한 후 정렬한 뒤 출력해주었다

2302번: 극장 좌석dp를 이용한 문제이다. dp를 구하기 위해선 먼저 case 2가지를 알아야 한다. dp\[N] = VIP석 없이 N명을 배치할 경우의 수라고 할때 case는 아래와 같다.N번 학생이 N번 자리애 앉는 경우 -> 1 ~ N - 1번 학생들이 앉는

1495번: 기타리스트dp를 이용한 문제이다. 처음에는 단순히 dfs로 접근을 해볼려고 했는데 시간 초과가 날 것 같아 dp로 구현을 했다. 로직은 간단하다. 음악, 볼륨을 나타내는 이중 배열을 만들어 반복문을 통해 이전 음악의 볼륨에서 더했을 때와 뺐을 경우가 각각

16194번: 카드 구매하기 2dp를 이용한 문제이다. 주어진 N만큼 반복문을 돌면서 1부터 i-1까지 값들을 비교를 해서 최솟값을 dp에 저장해준 뒤 출력해주었다. 쉽게 풀 수 있었던 문제였다.

18405번: 경쟁적 전염bfs를 활용한 구현 문제이다. 반복문을 많이 사용해 시간 초과가 발생할 줄 알았는데 한번에 통과했다. 먼저 맵을 입력 받으면서 해당 바이러스의 번호를 구분하여 좌표를 벡터에 저장해주었다. 그 후 반복문을 돌면서 bfs를 사용하게 되는데 이 때

17609번: 회문투 포인터를 이용한 문제이다. 입력받은 문자열을 반복문을 돌면서 회문인지 확인을 해준다. 만약 start와 end를 비교하고 만약 같지 않을 경우 start + 1 을 했을 때와 end - 1을 했을 때 둘 중 회문이 있는지 비교를 해주고 만약 있다면

10164번: 격자상의 경로dp를 이용한 문제이다. 먼저 findO를 통해 주어진 K에 해당하는 좌표를 구해주었다. 그리고 findNM를 이용해 K의 좌표를 끝으로 하는 배열과 K의 좌표가 시작인 배열 두개에서의 dp를 구해주었다. 이때 K가 0이면 findNM을 한번

14940번: 쉬운 최단거리bfs를 이용한 문제이다. 로직은 간단하다. 목표 지점의 좌표를 구해 bfs를 시작하여 카운트를 해주면서 저장을 해준 뒤 갈 수 있는 땅인데 카운트가 0인 곳은 -1로 바꿔주고 목표 지점의 카운트를 0으로 바꿔준 뒤 출력해주면 된다. 처음에

1914번: 하노이 탑기본적인 알고리즘인 하노이 탑을 구현하는 문제이다. 하노이 탑을 구현하는 것은 간단하게 할 수 있었지만 옮긴 횟수를 구할 때 신경을 써야한다. 문제에서 n의 최댓값이 100이기 때문에 단순히 int로 구한다면 실패를 하게된다. 문자열을 이용해서 옮

21610번: 마법사 상어와 비바라기문제 로직을 직접 구현을 하는 문제이다. 푸는 법은 간단하다. 그냥 문제 설명 순서대로 구현하면 된다. 나는 설명 순서대로 step을 나누어 구분하였다. 문제 그대로 구현한 코드이므로 문제 지문과 비교하면서 읽어보면 바로바로 이해가

1092번: 배그리디를 이용한 문제이다. 먼저 입력받은 크레인과 박스 무게들을 내림차순으로 정렬을 해주었다. 그리고 박스의 크기만큼 반복문을 돌면서 크레인 각각의 무게 제한과 비교하는 반복문을 통해 크레인이 옮길 수 있을 경우 박스를 erase하여 제거해주고 이를 반복

1261번: 알고스팟이 문제는 다익스트라나 0-1 BFS로 풀 수 있는 문제이다. 나는 다익스트라로 풀어봤다. d 배열은 현재 좌표까지 벽을 부순 최솟값을 나타낸다. 입력받은 맵을 bfs를 돌면서 현재 좌표와 다음 이동할 좌표의 d 배열값을 비교하고 최솟값을 저장해주었

2660번: 회장뽑기플로이드-워셜을 이용하는 문제이다. 먼저 친구 관계를 입력받을 때 이를 배열에 저장해주었다. 친구는 양방향이므로 A\[a]\[b]와 A\[b]\[a] 둘 다 1을 저장해주었다. 그 후 플로이드 워셜 알고리즘을 통해 각각의 최단 거리를 구해주었다. 이

1013번: Contact정규 표현식을 이용하는 문제이다. 문제를 읽어보니 정규 표현식과 같은 패턴을 가지고 있다는 점을 알 수 있다. C++에서는ㄷ regex라는 헤더를 통해 직접적으로 정규 표현식을 사용할 수 있다. 이를 통해 주어진 문자열과 패턴을 비교하여 일치하

2448번: 별 찍기 - 11재귀를 이용한 문제이다. 문제를 보면 가운데 빈칸이 있는 작은 삼각형 모형이 반복되고 있음을 알 수 있다. 이를 재귀를 통해 배열에 저장해주었다. 먼저 배열을 빈칸으로 초기화를 시켜준 다음 재귀를 돌려준다. y와 x는 가장 작은 삼각형의 가

3184번: 양bfs를 이용한 문제이다. 기존 다른 bfs 문제와 로직이 유사하게 흘러간다. 반복문을 돌면서 울타리가 아닐 때, 방문한 적이 없는 좌표일 경우 bfs를 돌아준다. bfs를 돌면서 o나 v를 만날 경우 이를 카운트 해주고 두 개수를 비교해 sheep과 w

2230번: 수 고르기투 포인터를 이용한 문제이다. 두 값의 차이가 M 이상인 최솟값을 구해야하므로 이번엔 첫 인덱스부터 점점 범위를 넓혀가는 식으로 값을 구해보았다. 먼저 입력받은 값을 정렬을 해준 후 start = 0과 ebd = 1 에서 시작해 반복문을 돌며 두

1976번: 여행 가자오랜만에 분리 집합 문제이다. 먼저 root를 초기화해주고 반복문을 돌며 도시가 연결되있을 경우 root를 union 해준다. 그 후 여행 경로에 있는 도시들의 root를 비교해 결과를 출력해주었다. 오랜만에 분리 집합 문제라 시간이 오래 걸렸다.

6198번: 옥상 정원 꾸미기스택을 이용한 문제이다. 로직 자체는 간단한데 이것을 이해하는데 생각보다 오래 걸렸다... 먼저 첫번째 건물 높이를 스택에 넣어준다. 그 뒤 반복문을 돌면서 스택의 top과 현재 인덱스의 건물 높이와 비교하게 되는데 만약 top이 볼 수 없

4386번: 별자리 만들기크루스칼 알고리즘을 이용한 문제이다. 먼저 입력받은 별들 간의 거리를 모두 구해 벡터에 저장해주고 거리를 기준으로 오름차순으로 졍렬을 해주었다. 그리고 크루스칼을 통해 루트를 바꿔주게 되는데 거리 순으로 정렬을 했으므로 가까운 거리부터 루트를

1303번: 전쟁 - 전투bfs를 이용한 문제이다. 기존 bfs 흐름과 같다. 반복문을 돌면서 B와 W 그륩들을 각각 카운트하여 제곱을 한 후 더해주고 출력을 해주면 된다. 간단하게 풀 수 있었던 문제였다.

2636번: 치즈bfs를 아용하는 문제이다. 문제를 보면 치즈의 겉면부터 한 겹씩 녹는 것을 알 수 있다. 즉 치즈가 아니라 공기를 기준으로 bfs를 해주어야 한다. 먼저 배열을 입력 받으면서 치즈 칸 갯수를 카운트 해준다. 반복문을 돌면서 0,0에서 bfs를 돌려준다

2623번: 음악프로그램위상 정렬을 이용한 문제이ek. 전형적인 위장 정렬 로직을 따라간다. 주의할 점은 보조 PD의 담당 가수를 입력 받을 때 바로 앞 가수에 해당하는 백터 인덱스에 현재 가수를 저장해주어야 하기 때문에 앞 가수를 따로 저장해두어야 하는 점이다. 위상

1041번: 주사위그리디를 이용한 문제이다. 주사위의 면이 보이는 경우는 총 3가지가 된다. 1면만 보이는 경우, 2면만 보이는 경우 그리고 3면이 보이는 경우이다. 주사위로 이루어진 정사면체를 바닥에 두었다고 생각해보자. 그러면 1면만 보이는 경우에 해당하는 주사위

2240번: 자두나무dp를 이용한 문제이다. 생각보다 까다로운 dp 문제였다. 두가지의 경우를 생각해봐야 한다. 이동을 했을 경우, 이동을 하지 않았을 경우. 먼저 시작 지점이 1번 나무이므로 첫 자두가 떨어지는 나무에 따라 dp의 처음 시작을 초기화해준다. 그리고 반

2615번: 오목완전 탐색을 이용한 문제이다. 이중 반복문으로 모든 좌표에 접근을 하면서 0이 아닌 숫자를 만나게 될 경우 현재 좌표를 기준으로 오목이 완성되는지 확인을 해준다. 대각선 포함 8방향으로 깊이 우선 탐색을 통해 카운트를 해주게 되는데, 탐색 전에 탐색 반

15681번: 트리와 쿼리dfs와 dp를 이용한 문제이다. 입력으로 U와 V의 연결을 알려주는데 어느 방향이 루트로 향하는 방향인지 알 수가 없다. 그렇기에 양방향으로 입력을 받은 후 createTree를 통해 루트에서 자식 노드로 다시 방향을 구해주었다. 그리고 서브

1865번: 웜홀벨만 포드 알고리즘을 이용한 문제이다. 벨만 포드 알고리즘을 통해 음수 사이클이 존재하는지 확인을 하면 된다. 모든 간선을 N-1번 반복하여 방문하면서 최단 거리를 구한 후, 한번 더 방문했을 때 최단 거리가 갱신이 된다면 음수 사이클이 존재한다는 것,

10942번: 팰린드롬?dp를 이용한 문제이다. 기존 팰린드롬을 확인하는 방식으로 알고리즘을 짜게 되면 시간 초과가 난다. 팰린드롬은 좌우가 대칭이 되는 구조를 말한다. 즉 n\[s] == n\[e]라면 n\[s+1] == n\[e-1]이 무조건 성립이 되어야 한다.

15989번: 1, 2, 3 더하기 4dp를 이용한 문제이다. 1,2 그리고 3의 합으로 이루어진 경우의 수를 구해야하므로 3가지 경우로 나누어 볼 수 있다.dpi -> 1로만 이루어진 경우의 수. 무조건 1이다.dpi -> 1과 2로 이루어진 경우의 수.dpi ->

4811번: 알약dp를 이용한 문제이다. w와 h 개수에 따른 경우의 수를 dp를 이용해 구해주었다. 먼저 w=0인 경우는 h만 남았다는 의미이므로 나머지 h를 뒤에 이어 붙이는 경우 밖에 없기에 경우의 수는 1이 된다. 그리고 h=0인 경우는 w만 남았다는 의미이므로

18428번: 감시 피하기완전 탐색을 이용한 문제이다. 먼저 맵을 입력받을 때 빈칸과 선생님의 위치를 따로 저장을 해준다. 그리고 재귀를 돌면서 빈칸에 장애물을 하나씩 추가해주면서 3개가 됬을 때 선생님의 위치 기준으로 학생이 보이는지 확인해주었다. 아이디어만 떠올리면

9252번: LCS 2dp를 이용한 문제이다. 먼저 dp를 이용해 LCS를 구해준다. 두 문자열을 반복문을 돌며 비교하여 문자가 같을 경우 1씩 더해가며 dp를 구해주었다. 그 후 dp를 역추적해 LCS를 구해준다. 같은 문자인 경우 1을 더해주었으므로 dp에서 위,

11497번: 통나무 건너뛰기그리디를 이용한 문제이다. 문제를 읽어보면 배열의 첫 값과 마지막 값은 연결이 되어있다. 이 상태에서 최대 난이도가 최소인 경우를 찾아야 한다. 즉 배열을 정렬을 해줄 때 가운데에 가장 큰 값을 두고 양 옆으로 점점 작아지는 피라미드 형태로

13913번: 숨바꼭질 4bfs를 이용한 문제이다. 이전에 풀었던 숨바꼭질과 연계되는 문제이다. bfs를 이용해 최단 시간을 찾는 것은 동일하다. 다른 점은 방문했던 곳을 체크할 때 true, false가 아닌 이전 위치를 저장해주었다. bfs를 끝낸 후 도착 지점부터

13164번: 행복 유치원그리디를 이용한 문제이다. 조마다 차이가 최소가 되도록 조를 만들어야 하므로 우선 조원끼리의 차이를 구해주고 오름차순으로 정렬을 해준다. 조에는 인원이 한명만 있을 경우 차이가 0이 되기때문에 값을 구할 필요가 없다. 각 조마다 먼저 한명씩 넣

2812번: 크게 만들기그리디를 이용한 문제이다. 먼저 N자리의 숫자를 문자열로 입력을 받고 또 다른 문자열 result에 입력받은 문자열의 맨 앞숫자를 저장해준다. 이 후 반복문을 돌면서 result의 가장 뒷숫자와 비교하며 작은 숫자는 reulst.pop_back을

1240번: 노드사이의 거리dfs를 이용한 문제이다. 트리의 경우 노드 사이의 연결 방향이 양방향이므로 연결된 노드와 거리를 입력받을 때 양방향으로 저장해주었다. 그리고 M만큼 반복문을 돌며 dfs를 이용해 연결된 노드들을 따라 거리를 모두 더해 저장해준 뒤 출력해주었

2143번: 두 배열의 합누적 합, 이분 탐색을 이용한 문제이다. 먼저 A와 B의 모든 누적 합들을 구해준다. 그리고 B의 누적합을 오름차순으로 정렬을 한 후 A의 누적 합 크기만큼 반복문을 돌면서 T와의 차이와 같은 값을 B 누적 합에서 찾아 시작과 끝 인덱스를 구해

7662번: 이중 우선순위 큐우선순위 큐를 이용한 문제이다. 우선순위 큐를 양방향으로 구현해주기 위해 오름차순과 내림차순 두가지 우선순위 큐를 사용해주었다.반복문을 돌며 커맨드에 따라 동작을 하게 되는데 중요한 점은 cnt를 통해 n의 개수를 카운트해주는 점이다. 이

1351번: 무한 수열dp를 이용한 문제이다. N의 범위를 보면 int의 범위를 넘기때문에 자료형을 long long으로 해주었다. 기존 dp에서는 최대 범위만큼 배열을 만들어 저장해주었지만 범위가 크기때문에 map을 이용하여 저장해주었다. 재귀를 통해 m\[N]을 구

16987번: 계란으로 계란치기백트래킹을 이용한 문제이다. 사실상 문제에서 조건들을 다 알려주었기에 조건대로 로직을 짜주면 된다. 가장 왼쪽 계란부터 시작하여 dfs를 시작한다. 반복문을 돌며 하나씩 비교해 내구도를 바꾸어주면서 깊이 탐색을 이용한다. 이때 더이상 깨지

2436번: 공약수정수론을 이용한 문제이다. 먼저 공식에 대해 알고 있어야 한다. 두 수 A, B가 있을 때, A = a \* GCD(A,B), B = b \* GCD(A,B)을 만족하는 a, b가 있다고 하자. 이럴 경우 LCM(A,B) = a \* b \* GCD(

16139번: 인간-컴퓨터 상호작용누적 합을 이용한 문제이다. 먼저 문자열을 입력받고 모든 알파벳을 대조하며 카운트를 해주었다. 이때 카운트는 0 ~ r 까지의 카운트를 저장하게 된다. 그 후 질문을 입력받으면서 입력에 해당하는 값을 출력해주었다. 이 때 시작 지점 l

1939번: 중량제한이분 탐색과 bfs를 이용한 문제이다. 입력 단위가 크기 때문에 bfs만을 사용하면 시간 초과가 발생한다. 그렇기에 이분 탐색을 이용해주었다. 0을 left, 10억을 right로 지정하고 가운데 값을 mid로 주어 반복문을 돌며 bfs를 돌려주었다

12851번: 숨바꼭질 2bfs를 이용한 문제이다. 기존 bfs와 비슷하게 흘러가지만 주의할 점이 있다. N = 1일 때 1 + 1과 1 \* 2가 구분이 안되게 된다. 구분을 하기 위해 푸시를 할 때 check\[next] = true를 해주는 것이 아닌 큐에서 꺼냈

2138번: 전구와 스위치그리디를 이용한 문제이다. 이 문제의 키포인트는 i==0일 때 상태를 바꾸냐 안 바꾸냐이다. 현재 위치를 i라고 한다면 i의 상태를 바꾸면 i-1과 i+1의 상태가 바뀌게 된다. 그렇기에 i-1의 상태를 바꿀려면 i를 바꾸어주면 된다. 반복문이

4485번: 녹색 옷 입은 애가 젤다지?그래프 탐색을 이용한 문제이다. 이 문제는 bfs와 다익스트라 두 방식으로 해결할 수 있다. 사실상 우선순위 큐를 사용했냐 안했냐 차이이다. 우선순위 큐를 이용한 다익스트라 쪽이 시간이 거의 1/2 일 정도로 더 빠르다. 지나온

1052번: 물병그리디를 이용한 문제이다. 같은 양의 물이 들어있는 물병끼리는 하나로 합칠 수 있다. 그렇기에 N을 2로 나누어가다보면 최종적으로 남는 물이 들어있는 물병의 개수를 알 수 있다. 만약 개수가 K 이하라면 물병을 추가로 구매할 필요가 없다. 코드는 반복문

1915번: 가장 큰 정사각형dp를 이용한 문제이다. 1로 이루어진 가장 큰 정사각형을 구해야 하는데 이를 dp 배열을 이용해 구해주었다. 먼저 가장 위쪽과 왼쪽에 1일 경우 dp에 1을 저장해주었다. 그리고 i=1, j=1에서 반복문을 시작하여 정사각형의 길이를 구해

16637번: 괄호 추가하기직접 구현을 하는 문제이다. 재귀를 이용해 구현하였다. 괄호를 사용했나 하지 않았나 두가지로 분기하여 재귀를 사용해주었다. pre의 경우 현재 인덱스 포함 이전 까지의 연산 결과를 저장한다. 재귀를 통해 최댓값을 구해 출력해주었다. 굉장히 어

15661번: 링크와 스타트백트래킹을 이용한 문제이다. 기존 백트래킹과 비슷하게 진행이 된다. 다른 점이라면 result를 구하는 조건이다. 만약 N=4일 때 check에 저장될 수 있는 기록 중 1 0 0 0과 0 1 1 1은 같은 결과를 리턴하게 된다. 그렇기에 N

1655번: 가운데를 말해요우선 순위 큐를 이용하여 풀 수 있는 문제이다. 문제를 보면 주어지는 입력마다 정렬을 하여 가운데에 해당하는 수를 출력해주어야 한다. 그리고 제한 시간도 0.5초밖에 되지 않기에 힙 정렬을 사용하는 우선 순위 큐를 사용해주어야 한다. 큐는 오

12015번: 가장 긴 증가하는 부분 수열 2이분 탐색을 이용한 문제이다. lis 알고리즘을 이용하여 문제를 해결했다. 입력받은 값들을 벡터 result에 차례대로 넣어주는데 이때 현재 백터에 들어갈 값이 result.back()보다 작다면 lower_bound를 통해

1713번: 후보 추천하기주어진 조건을 직접 구현하는 문제이다. 맵을 사용하였으며 키에는 추천받은 학생 번호를, 값에는 추천수와 값이 위치한 인덱스를 저장해주었다. 현재 값이 맵에 이미 있을 경우 그 값의 추천수를 +1해주고, 없다면 새로 추가해주었다. 추가해줄 때 만

1202번: 보석 도둑그리디와 우선 순위 큐를 이용하는 문제이다. 각 배낭마다 최대 무게가 있고 최대 한개의 보석만을 담을 수 있다. 우선 입력받은 보석 정보들과 가방 무게들을 오름차순으로 정렬해주었다. 그 후 반복문을 돌며 해당 배낭의 무게에 담을 수 있는 보석들의

1167번: 트리의 지름dfs를 이용한 문제이다. 먼저 트리의 지름을 구하는 법에 대해 알아야 한다. 트리의 지름은 임의의 두 점의 거리 중 가장 긴 것을 말한다. 이를 공식화 해볼 수 있는데 아래와 같다.정점 x에서 가장 거리가 먼 정점 y를 구한다.정점 y에서 가장

11725번: 트리의 부모 찾기dfs를 이용한 문제이다. dfs를 통해 입력받은 연결된 노드들을 순차적으로 순회하며 parent 배열에 현재 노드를 저장해주었다. 간단하게 풀 수 있었던 문제였다.

15650번: N과 M (2)백트래킹으로 간단히 구현할 수 있는 문제였다. 쉽게 풀 수 있었다.

15654번: N과 M (5)백트래킹을 이용한 문제이다. 간단하게 풀 수 있었다.

15663번: N과 M (9)백트래킹을 이용한 문제이다. 이전 문제와의 차이점이라면 이미 출력한 수열과 같은 값을 가지는 수열은 다시 출력을 하지 않는다는 점이다. 이부분을 set을 이용하여 풀어보았다. 쉽게 풀 수 있었던 문제였다.

1766번: 문제집위상 정렬을 이용한 문제이다. 난이도가 낮은 순서대로 접근을 해야하기 때문에 우선순위 큐를 사용하여 위상 정렬을 구현해주었다. 위상 정렬에 대해 잘 아는지 확인하는 문제였다. 어렵지 않게 풀 수 있었다.

2749번: 피보나치 수 3피사노 주기라는 공식을 이용하는 문제이다. 피보나치 수를 구하는 공식 중 피사노 주기라는 공식이 있다. 피보나치 수를 특정 값으로 나눌 때 항상 일정 주기를 가지게 되는데 이를 피사노 주기라고 한다. 공식은 다음과 같다.주기의 길이를 P라고

4195번: 친구 네트워크분리 집합을 이용한 문제이다. 먼저 입력받은 사람들의 이름이 문자열로 주어지므로 이를 set을 이용해 중복을 제거하며 모두 입력받은 후 map에 인덱스를 value로 하여 저장해주었다. 그리고 루트에 해당하는 노드를 구하는 parent와 해당

2473번: 세 용액투 포인터를 이용한 문제이다. 이 문제에서는 세가지 용액의 값을 구해야하므로 세가지의 위치를 구해야한다. 반복문을 돌면서 i를 기준으로 투 포인터를 이용해주었다. 먼저 입력받은 값을 오름차순으로 정렬을 해주고, i를 고정으로 두고 i + 1과 끝의

1722번: 순열의 순서팩토리얼을 이용하여 구현을 하는 문제이다. 이 문제는 두가지 경우로 나뉘는데 해당 순서에 맞는 배열을 출력하는 것과 해당 배열의 순서를 출력하는 두가지이다. 두가지 경우 모두 팩토리얼을 이용해 순서를 구해야한다. 첫번째 경우 주어진 순서 k에 해

17299번: 오등큰수스택을 이용한 문제이다. 문제에서 구해야할 것은 현재값보다 오른쪽에 위치하면서 카운트가 가장 큰 왼쪽에 있는 값이다. 먼저 문제를 입력받으면서 해당 값을 카운트를 해주었다. 그리고 NFG를 -1로 초기화를 해주고 반복문을 돌면서 오등큰수를 찾아주었

2437번: 저울그리디 방식으로 푸는 문제이다. 풀이 방식 자체는 간단하다. 예를 들어 1, 2, 4, 15 배열을 왼쪽부터 접근한다고 가정해보자. 첫 무게인 1의 경우 1 ~ 1만 측정이 가능하다. 2의 경우 이전의 범위에 더한 1 + 2 ~ 1 + 2, 즉 1 ~

17836번: 공주님을 구해라!bfs를 이용한 문제이다. 시작 지점을 0,0, 시간 그리고 그람 유무를 가지는 큐를 만들어주었다. 그리고 bfs를 돌며 그람을 가질 경우 true로 바꿔주고 공주를 만날 경우의 시간을 저장해주고 T와 비교하여 답을 출력해주었다. 지나온

2533번: 사회망 서비스(SNS)트리와 dp를 이용한 문제이다. 먼저 트리의 간선을 입력받으면서 벡터에 양방향으로 저장을 해준다. 그 후 아무 값에서 시작하여 트리를 모두 접근을 하면서 dp에 값을 저장해준다. dp는 각 노드마다 두개의 배열을 가지게 되는데 0은 해

11437번: LCA트리를 이용한 문제이다. 공통되는 부모 노드를 찾기 위해 먼저 주어진 간선을 이용해 각 노드의 부모 노드와 깊이를 따로 저장해주었다. 그리고 공통 부모 노드를 찾기를 원하는 두 노드의 깊이를 비교해 두 노드의 깊이가 같아질때까지 더 깊은 노드의 레벨

2042번: 구간 합 구하기세그먼트 트리를 이용한 문제이다. 구간 합을 구하는 방식을 세그먼트 트리를 이용하여 O(logN)으로 합을 구할 수 있다. 먼저 입력받은 값을 이용해 세그먼트 트리를 만들어준다. 그리고 1일 경우 update를 해주고 2일 경우 sum을 이용

2629번: 양팔저울배낭 문제를 이용한 dp 문제이다. 각 추마다 0부터 40000까지 반복문을 돌면서 세가지 조건에 따라 dp를 갱신해준다. 아무것도 하지 않을 경우현재 무게에서 추의 무게를 뺀 경우현재 무게에서 추의 무개를 더한 경우dp\[i]\[j]일 때, i는

1106번: 호텔배낭 문제를 이용한 문제이다. 비용을 나타내는 dp\[]를 이용하여 문제를 해결하였다. 배열의 최댓값은 100 \* 1000으로 100000으로 설정하였다. 반복문을 돌면서 도시 하나씩 dp에 현재 비용에 해당하는 위치에 비교하며 값을 저장해주었다. 그

3109번: 빵집dfs를 이용한 문제이다. 이 문제에서 중요한 부분은 다음으로 이동하는 좌표의 순서이다. 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 3가지의 경우로 좌표를 이동하게 되는데 보통 반복문을 0부터 시작하기 때문에 시작이 첫째 열, 첫째 행이다. 그렇기에

9934번: 완전 이진 트리재귀를 이용한 문제이다. 문제를 보면 상근이는 빌딩을 중위 순회 방식으로 빌딩에 들어가고 있다. 그렇기에 주어진 진입 순서의 중앙이 트리의 루트가 되고, 줃앙을 기준으로 왼쪽, 오른쪽으로 나누어 다시 각각의 중앙이 루트가 되고 이를 반복하게

17779번: 게리맨더링 2지문을 보고 직접 구현하는 문제이다. 문제 자체 구현은 쉽다. 이런 문제들의 특징은 문제에서 해주는 설명을 그대로 구현을 해주기만 하면 되기에 생각보다 어렵지 않게 풀 수 있다. 반복문을 돌면서 1번부터 5번까지의 구역을 모두 구한 후, 이

1647번: 도시 분할 계획최소 스패닝 트리를 이용한 문제이다. 문제는 간단하다. 크루스칼 알고리즘을 통해 최소 가중치를 가지는 트리 경로를 구한 후 이를 다시 정렬하여 가중치가 가장 큰 값을 뺀 값을 출력해주었다.어렵지 않게 풀 수 있었다. 다만 최소 스패닝 트리를

2887번: 행성 터널최소 스패닝 트리를 이용한 문제이다. 문제 유형은 최소 스패닝 트리로 되어 있지만 사실상 크루스칼 알고리즘에서 사용할 경로와 가중치를 구하는 부분이 생각해내는데 시간이 오래 걸린다. 기존 크루스칼 알고리즘을 사용을 하는데 주어진 좌표들을 이용해 경

16948번: 데스 나이트bfs를 이용한 문제이다. 간단한 bfs 구현 문제로 문제에서 주어진 이동 조건을 dy, dx로 구현해 풀어주었다.쉽게 풀 수 있었던 문제였다. 다만 오타로 인해 시간 낭비가 좀 있었다. 오타를 찾지 못해 시간을 허비하는 경우가 잦은 것 같다.

5972번: 택배 배송다익스트라를 이용한 문제이다. 일반적인 다익스트라 구현 문제이다. 먼저 길을 입력받을 때 양방향이므로 양쪽으로 길을 저장을 해준다. 시작 지점이 1, 도착 지점이 N으로 고정이므로 1부터 시작해 다익스트라를 통해 각 위치 간의 최단 거리를 구해주고

5052번: 전화번호 목록해시 셋을 이용한 문제이다. 먼저 모든 입력을 벡터로 받아준 후 이를 오름차순으로 정렬을 해준다. 그리고 반복문을 돌며 해당 전화번호의 한글자 씩 tmp에 넣어보며 해시 셋에 있는 전화번호들과 비교하여 만약 존재할 경우 NO를 출력해주고 없다면

11657번: 타임머신벨만 포드를 이용한 문제이다. 기존 벨만 포드와 동일하게 구현을 해주면 된다. 반복문을 돌 때 간선이 없을 경우가 있기 때문에 d\[from] == INF일 경우 continue를 해주는 조건을 추가해주었다. 반복문을 돌면서 최단 거리를 구한 후

20057번: 마법사 상어와 토네이도문제에 주어진 조건을 통해 구현을 하는 문제이다. 두가지 조건을 구현을 해주면 된다. 첫번째는 토네이도의 이동, 두번째는 모래의 이동이다. 토에니도의 이동은 왼쪽, 아래쪽, 오른쪽, 위쪽 순으로 스텝을 나누어 구현해주었다. 한바퀴마다

1300번: K번째 수이분 탐색을 이용한 아이디어가 필요한 문제이다. 먼저 N=5 일때의 표를 한번 보자.만약 r=4라고 할때, 1행부터 차례대로 r보다 작거나 같은 값의 갯수는 4,2,1,1,0이다. 이는 min(mid/i, N)으로 나타낼 수 있다. 즉 반복문을 돌

1062번: 가르침백트래킹을 이용한 문제이다. 입력으로 주어지는 문자에 앞과 뒤에는 고정된 문자 anta와 tica가 존재한다. 그렇기에 5개의 문자는 고정으로 배워야하므로 5 미만의 K는 모두 0을 출력해주었다. dfs를 돌면서 문자 하나씩 true로 바꿔주며 문자열

1774번: 우주신과의 교감최소 스패닝 트리를 이용한 문제이다. 크루스칼 알고리즘을 사용하기 위해 가중치와 경로를 구하는 것이 중요한 포인트이다. 먼저 부모 노드를 나타내는 p 배열을 초기화해주고 입력으로 받은 경로를 모두 각각의 부모 노드에 지정해준다. 그리고 각 노

2357번: 최솟값과 최댓값세그먼트 트리를 이용한 문제이다. 해당 구간의 최댓값과 최솟값을 구해 세그먼트 트리를 만들어주고 입력받은 a, b에 해당하는 결과를 찾아 출력해주었다.생각보다 어려웠던 문제였다. 세그먼트 트리를 이용하는 것까지는 생각을 해냈었는데 결과를 찾는

17136번: 색종이 붙이기백트래킹을 이용한 문제이다. 먼저 전체 맵을 5의 크기를 가지는 색종이부터 붙이고 다음 4,3,2,1 순으로 붙여준다. 그리고 백트래킹을 이용해 최솟값을 찾아주어 출력해주었다. 각각의 색종이의 개수가 5개라는 점을 조건으로 넣어주어야만 한다.

12919번: A와 B 2재귀를 이용하는 문제이다. 주어진 S가 T가 될 수 있는지 알아야 한다. S에서 재귀를 통해 찾아가면 너무 많은 경우의 수가 생기므로 T에서 S를 찾아가는 방식을 이용하였다. 제거하는데 있어서 3가지 경우의 수가 있다.맨 앞과 뒤가 A일 경우맨

2502번: 떡 먹는 호랑이완전 탐색을 이용한 문제이다. 첫날 떡 갯수를 a, 둘째날 떡 갯수를 b라고 했을때, 아래와 같은 방식으로 갯수가 늘어남을 알 수 있다.첫째날 - 1a + 0b둘째날 - 0a + 1b셋째날 - 1a + 1b넷째날 - 1a + 2b다섯째날 -

1941번: 소문난 칠공주조합과 bfs를 이용한 문제이다. 문제에서 요구하는 것은 해당 조건을 만족하는 경우의 수이다. 그렇기에 조합을 이용해 경우의 수를 먼저 구한 후 해당 경우가 조건에 만족하는지 확인을 해주면 된다. 주어지는 배열의 크기는 5x5이므로 이는 일차원

4179번: 불!bfs를 이용한 문제이다. 문제 상황을 보면 지훈이와 불은 한 타임에 동시에 움직인다. 그렇기에 입력을 받을 때 지훈이의 위치와 불의 위치를 따로 저장한 뒤 큐에 넣어주었다. 주의할 점은 지훈이부터 큐에 넣어줘야한다는 점이다. 이유는 bfs를 돌 때 불

10775번: 공항분리 집합을 이용한 문제이다. 문제에서의 설명에 의하면 1부터 주어진 입력 g까지 사이의 게이트 중 하나에 영구적으로 도킹을 하고 이후 입력으로 주어진 g까지의 게이트가 모두 차있으면 종료를 한다고 적혀있다. 즉 현재 도킹되어있는 게이트의 여부를 확이

2981번: 검문수학적 공식을 이용한 문제이다. 문제에서 주어지는 값들의 나머지가 모두 같은 값들을 찾아야 한다. 즉 아래의 식으로 나타낼 수 있다.나머지가 같으므로 A\[1] % M = A\[2] % M 이므로, 즉 A\[1] - (A\[1] / M) \* M = A

7490번: 0 만들기백트래킹을 이용한 문제이다. dfs를 이용해 4가지 경우의 수를 확인해보며 결과가 0일 경우 저장해주었다. 4가지 경우의 수는 다음과 같다.'+' 인 경우'+' 다음에 ' ' 인 경우'-' 인 경우'-' 다음에 ' ' 인 경우처음 dfs를 돌 때

13904번: 과제정렬을 이용한 문제이다. 문제에서 주어지는 점수와 마감일을 벡터에 저장을 하는데 이때 마감일 기준 내림차순으로 정렬을 하기 위해 위치를 바꿔 저장을 해준다. 그 후 반복문을 돌면서 배열 cost에 마감일 기한부터 1일까지 중 빈 값을 찾아 점수를 저장

2239번: 스도쿠백트래킹을 이용한 문제이다. 문제에서는 스도쿠 판이 모두 채워진 결과를 원하고 있다. 즉 0을 모두 채운 결과이다. 우선 스도쿠 판을 입력받을 때 0인 경우의 좌표를 벡터v에 저장을 해주었다. 그 후 dfs를 돌면서 v\[depth] 좌표를 기준으로