BOJ

백준 1920: 수 찾기Sort + Binary Search문제에서 이진탐색 사용하라고 외치고 있다. std::sort가 nlog(n)이고 binary search가 log(n)인데 m번 하니까 mlog(m) 총 nlog(n) + mlog(m)어쩌다보니 첫 게시물

✔ 문제 링크 BOJ 10816: 숫자 카드 2 > ### ✔ 문제해결전략 이진탐색의 활용 ✔ Code 1) 직접 구현 ✔ Code 2) std::lowerbound, upperbound 사용 ✔ Comment 문제에서 이진 탐색 사용하라고 외치고 있다.

✔ 문제 링크 BOJ 10816: 숫자 카드 2 > ### ✔ 문제해결전략 이진탐색의 활용(upperbound & lowerbound) ✔ Code 1) 직접 구현 ✔ Code 2) std::lowerbound, upperbound 사용 ✔ Comment

✔ 문제 링크 BOJ 2579: 계단 오르기 > ### ✔ 문제해결전략 >> - Dynamic Programming >> - 1 ### ✔ 해결과정 >> #### ✔ 테이블 정의 dp[i] = i번째 계단까지 왔을 때 점수 합의 max 이렇게 정의하면 연속된 세

BOJ 1931: 회의실 배정Greedy완전탐색: O(2^n)이라 불가능DP: di = i번째 회의를 끝으로 할 때 진행한 최대 회의 수(끝나는 순으로 정렬 후) => O(n^2)이라 불가능So, 탐색 범위를 줄여보자회의들을 끝나는 시간 순으로 정렬하고 각 상황에서 가

BOJ 1806: 부분합Two Pointer1<=N<=100000이므로 완전탐색(O(N^2)) 불가능BOJ: 2230: 수 고르기 와 비슷하다. end가 가리키는 값을 sum에 반영하고 mini 값을 업데이트해야 하는데 end를 업데이트하기 직전에 sum 값

BOJ 7562: 나이트의 이동그래프 탐색BFS(Breadth First Search)정직하게 BFS 하면 된다. 보통 2차원에서의 BFS는 상하좌우로 탐색을 하는데 이 문제는 8방향으로 탐색하면 된다.PS 할 때는 보통 전역배열 잡고 하는데 여기서는 fill 함수 사

BOJ 5014: 스타트링크그래프 탐색1차원에서의 BFS(Breadth First Search)정직하게 BFS 하면 된다.

BOJ 2573: 빙산그래프 탐색BFS(Breadth First Search)처음에 한 번의 BFS 사이클 내에 모든 것을 해결하려고 했는데 잘되지 않아서 헤맸다. 생각해 보면 처음에 빙산이 녹는 것에 대해 map을 업데이트하기 위해 한 사이클을 돌리고, 업데이트된 m

✔ 문제 링크 BOJ 2606: 바이러스 > ### ✔ 문제해결전략 >> - 그래프 탐색 >> - BFS(Breadth First Search) > ### ✔ 해결과정 1번 컴퓨터를 시작점으로 정직하게 BFS 하면 된다. 이 문제에서의 경우 컴퓨터 네트워크를 ve

✔ 문제 링크 BOJ 1012: 유기농 배추 > ### ✔ 문제해결전략 >> - 그래프 탐색 >> - 1차원에서의 BFS(Breadth First Search) > ### ✔ 해결과정 정직하게 BFS 하면 된다. ✔ 정답 Code

✔ 문제 링크 BOJ 2468: 안전 영역 > ### ✔ 문제해결전략 >> - 그래프 탐색 >> - BFS(Breadth First Search) > ### ✔ 해결과정 BFS를 여러 번 돌리며 각 사이클에서 물에 잠기지 않는 영역의 개수를 구해 비교하며 최댓값을

✔ 문제 링크 BOJ 1697: 숨바꼭질 > ### ✔ 문제해결전략 >> - 그래프 탐색 >> - 1차원에서의 BFS(Breadth First Search) > ### ✔ 해결과정 훈련소에서 인편으로 이 문제 받았을 때 DP인 줄 알았는데 놀랍게도 BFS다. BF

BOJ 13913: 숨바꼭질 4그래프 탐색1차원에서의 BFS(Breadth First Search)BOJ 1697: 숨바꼭질에서 이동경로가 추가되었다. BFS 하면서 각 점이 어느 점에서 -1, +1, \*2 되어 탐색 대상이 되었는지를 before에 저장하고 동생 위

✔ 문제 링크 BOJ 13549: 숨바꼭질 3 ✔ 문제해결전략 - 그래프 탐색 - 1차원에서의 BFS(Breadth First Search) ✔ 해결과정 - BOJ 1697: 숨바꼭질에서 *2는 0초 만에 가능한 것으로 바뀌었

BOJ 12865: 평범한 배낭 ✔ 문제해결전략 - 0-1 Knapsack Algorithm + Dynamic Programming ✔ 해결과정 - 가방에 담을 수 있는 물건의 무게에 제한이 있을 때, 가방에 담긴 물

✔ 문제 링크 BOJ 1197: 최소 스패닝 트리 ✔ 문제해결전략 Minimun Spanning Tree ✔ 해결과정 Minimun Spanning TreeGiven a connected graph with |V| = n vertices, a spanning

BOJ 1008: A/B 아무 생각 없이 했다가 엄청 틀렸다. c 스타일로 scanf 사용하면 %lf로 해결 가능하겠지만 c++ 사용하니 cout으로 풀어보았다. cout의 정확도는 cout.precision으로 조절한다고 한다. 예를 들어 이면 정확도 10까지 표

BOJ 10989: 수 정렬하기 3 1 ≤ N ≤ 10,000,000인데 메모리 제한이 8MB다. 배열 사이즈를 10,000,000로 잡으면 40MB여서 바로 out이다. 문제에서 각각의 수가 10,000보다 작거나 같은 자연수라고 했으므로 크기 10,001인 배열을

BOJ 11650: 좌표 정렬하기 Std::pair 사용 연습

BOJ 11866: 요세푸스 문제 0 k-1번 dequeue, enqueue 반복하면 k 번째 수가 큐의 맨 앞에 있으므로 출력하고 pop 하면 된다. 이 과정 큐가 빌 때까지 반복

✔ 문제 링크 BOJ 10814: 나이순 정렬 ✔ 문제해결전략 Stable Sort or 구현 ✔ 해결과정 나이 순, 나이가 같으면 가입한 순으로 정렬을 하여야 한다. 나이가 같은 경우가 존재하므로 아무 sorting이나 사용해서는 안 된다. std::sort

✔ 문제 링크 BOJ 7662: 이중 우선순위 큐 ✔ 문제해결전략 Priority Queue Binary Search Tree(balanced) ✔ 해결과정 문제 이름이 이중 우선순위 큐니까 단순하게 생각해 보면 Max heap, Min heap으로 각각 최댓

BOJ 11404: 플로이드 All-Pairs Shortest Path(Floyd) 주어진 그래프에서 모든 정점 쌍 사이의 최단거리(All-Pairs Shortest Path)를 구해야 한다.

✔ 문제 링크 [BOJ 1629: 곱셈] ✔ 문제해결전략 - Recursion ✔ 해결과정 exponent가 거의 INT_M

✔ 문제 링크 BOJ 10830: 행렬 제곱 ✔ 문제해결전략 Recursion ✔ 해결과정 BOJ 1629: 곱셈에서와 같은 논리로 exponent가 너무 크므로 exp/2 계속 재귀호출하면서 O(log N)으로 바운드 시킨다. ✔ 정답 CODE ✔ Com

✔ 문제 링크 BOJ 11444: 피보나치 수 6 ✔ 문제해결전략 Recursion ✔ 해결과정 n이 너무 커서 메모이제이션을 위한 long long 타입 배열을 잡으려면 256mb로는 어림도 없다. ✔ 정답 CODE ✔ Comment BOJ 1629:

✔ 문제 링크 BOJ 14502: 연구소 ✔ 문제해결전략 Brute Force + BFS ✔ 해결과정 1) 벽을 세우고 2) 바이러스가 퍼지고 3)바이러스가 퍼지지 않은 영역의 넓이를 구하면 된다. 벽만 세우고 나면 BFS인데 벽 세우는 것을 어떻게 구현할