[목차]310 [백준 2003번 / C++ / 투포인터] 수들의 합2 투포인터를 활용한 문제이다. 1. s, e 포인터를 생성하여 벡터의 첫번째 원소를 가리킨다. 2. e 포인터가 벡터의 사이즈보다 작을때 동안 반복문을 돌린다. 3. 만약 sum값이 m보다 작다면 s포인터가 가리키고 있는 원소의 값을 sum값에 빼주면서 포인터의 위치를 하나 증가 4. sum값이 m가 같다면 result 값 증가 5. s 포인터가 증가 시켜야하는 조건문에 부합되지 않으면 continue에 걸리지 않는다. 그러므로 end 포인터를 증가시켜야하는 코드부분에 도달하게 된다. 여기서 주의할 점은 증가된 e포인터가 원소의 값을 갖고 있을때만 sum에 더해준다. #include #include using namespace std; int main() { int n, m; cin >> n >> m; v.. 백준/증가수열 & 투포인터 2022. 2. 16. [백준 2512번 / C++] 예산 이분 탐색을 이용하여 풀면 된다. 1. 벡터 V에 값을 저장 후 오름차순으로 정렬 2. high 값은 벡터의 제일 큰 원소의 값으로 저장 3. sum 변수에 mid값과 벡터의 원소의 값을 비교하여 작은값을 더함 4. sum값이 m보다 크거나 같으면 result 값에 mid 값 저장 후 이분 탐색 #include #include #include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector v; ll s, e; for (int i = 0; i > a; v.push_back(a.. 백준/이분탐색 2022. 2. 16. [백준 1300번 / C++] K번째 수 이분 탐색 문제이다. 처음에 접근할 때 벡터를 생성하고 i*j 값을 push_back 해서 오름차순으로 정렬한다. k 위치에 해당하는 벡터의 원소를 출력한다. 이렇게 해선 안된다. N은 최대 10^5 이며 NxN 이기에 최악의 경우 100억의 벡터를 생성해야하는데 이러면 메모리 초과다. 그렇기 때문에 따로 벡터나 배열을 생성하지 않고 이분탐색으로만 확인하는 과정을 찾아보자. 1. low 에는 1 의 값을 저장하고 high 값에는 최악의 경우 10000000000(100억) 의 값을 저장한다. 2. 이차원 배열에는 i 행과 j 열이 있는데 각 원소는 i와 j의 곱의 결과가 저장되어있다. 현재 mid 값은 갱신되는 기준값이며 해당 기준값에서 i를 나눠준 몫이 j 값이다. 그렇기 때문에 i 행에서 mid값보다.. 백준/이분탐색 2022. 2. 16. [백준 18113번 / C++] 그르다 김가놈 이분 탐색 문제이다. 접근 방식 1. 벡터 V에 꼬다리를 조건에 맞게 제거한 김밥 길이를 저장한다. - 김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 - 김밥 길이가 kcm이거나 그보다 짧으면 김밥 폐기 - 위의 조건에 해당되지 않으면 두쪽 꼬다리를 자름 2. p(mid) 의 최댓값을 구하기 위해서 low 값이 갱신될 때 result 값에 mid값을 넣어준다. 3. p의 값이 존재하지 않을 경우 - 1을 출력한다. #include #include using namespace std; typedef long long ll; int main() { //꼬다리 잘라낸 김밥 -> 손질된 김밥 //김밥 N개, kcm 잘라낸다 양쪽 균일하게 //김밥 길이가 2kcm 짧으면 한쪽만 꼬다리 짜름 // 김밥 길이가 k.. 백준/이분탐색 2022. 2. 16. [백준 15810번 / C++] 풍선 공장 이 문제를 처음 접할 때 바로 이분 탐색을 떠올려야한다. low는 0 으로 초기화를 하고 high 같은 경우엔 1,000,000,000,000으로 초기화한다 ( 스태프가 1명이고 풍선 하나를 만드는데 걸리는 시간이 1,000,000초가 걸릴 때 풍선 1000,000개를 만들 경우 ) 최소시간을 구하기 위해서 high 값을 갱신하면서 해당 조건문 블록에서 mid 값을 result 변수에 저장해준다. #include #include using namespace std; typedef long long ll; vector v; int main() { int n, m; cin >> n >> m; for (int i = 0; i > a; v.push_back(a); } .. 백준/이분탐색 2022. 2. 16. [백준 17144 / C++] 미세먼지 안녕! 살짝 노가다 문제이긴 한데 한번 풀어보면 괜찮은 문제이다. 1. map 에서 미세먼지의 수치가 저장되어 있는 좌표값들을 모두 큐에 넣는다. 2. 큐에 있는 좌표값들을 꺼집어 내서 상하좌우에 해당하는 규칙에 따라 값을 갱신한다. 3. 갱신한 맵을 공기청정기를 중심으로 공기가 정화되게끔 map의 원소값을 시계 방향, 반시계 방향으로 이동시킨다. 4. time이 입력한 값이 되면 맵의 모든 미세먼지 값을 더해서 출력해준다. #include #include #include #include #include using namespace std; queue q; int map[50][50]; int map_sum[50][50]; int m, n, time; int dy[4] = { 0,0,-1,1 }; int dx[.. 백준/DFS BFS 2022. 2. 15. [백준 1107번 / C++] 리모컨 완전 탐색을 통해 해결하면 되는 문제이다. 1. 0부터 1000000 까지 모든 채널을 확인한다. 2. 각 채널에서 표시되는 숫자값을 하나하나 확인하면서 고장난 것이 하나라도 있으면 반복문을 종료한다. 3. 고장난 것이 없다면 "현재 채널의 길이 + ((절댓값)목표 채널 - 현재 채널) " 최솟값을 구한다. 4. 반복문이 종료된 후 저장된 최솟값과 현재 수빈이가 있는 100 채널에서 + 또는 - 로 이동할 수 있는 최솟값과 비교해서 작은값을 출력하도록 한다. #include #include #include #include #include #include using namespace std; int inf = 1000001; int ch; int n; bool check[10]; int main() { i.. 백준/완전 탐색 2022. 2. 14. [백준 1759번 / C++ ] 암호 만들기 모든 경우의 수 정렬 벡터를 정렬할 때 정렬 될 수 있는 모든 경우의 수를 물어보는 문제가 있다. 이러한 경우 해당 함수를 사용한다. 즉, A B C 를 정렬하고 싶은데 모든 경우를 정렬하면, ABC ACB BAC BCA CAB CBA 순으로 정 baebalja.tistory.com next_permutation 함수를 활용해서 쉽게 접근할 수 있다. next_permutation은 모든 경우의 수를 정렬하게 되는데 이때 bool 벡터를 생성하여 변화되는 문자들만 활용해서 문자열을 생성할 수 있다. 이때, 체크해야 할 것은 모음이 1개 이상, 자음이 2개 이상이여야 한다는 점을 주의하자. 1. 알파벳 벡터 내림차순으로 정렬 2. check 벡터 오름차순으로 정렬 ex) 두 개의 문자를 비교할 때, e d.. 백준/구현 2022. 2. 14. [백준 2234번 / C++] 성곽 이 문제는 "비트연산, 완전탐색, BFS"를 활용한 문제이다. 이 세가지에 대한 이해도가 확실하면 정말 재밌게 풀 수 있을것이다. 먼저 구해야 할 값은 총 3가지이다. 1. 처음 BFS 함수를 호출 하는 개수(방의 개수) 2. BFS함수에서 Queue값을 pop() 하는 개수(방의 영역) 3. 하나의 벽을 허물었을 때 나오는 최대 방의 영역. 먼저 , 첫 번째 답과 두 번째 답을 풀기 어렵다면 쉬운 bfs 문제를 풀고 오기를 권한다. 이 문제에서 조금 다른점은 벽의 위치를 2진수 방법으로 표현했다는 것이다. 예를들어, 10진수 "11"은 2진수로 "1011" 이라는 값이 나오는데 오른쪽부터 위치한 1은 서쪽에 벽이있고 그 다음 1은 북쪽에 벽이 있고 그 다음 0은 동쪽에 벽이 없고 그 다음 1은 남쪽에 .. 백준/비트마스킹 2022. 2. 11. [프로그래머스 Level_3 / C++ / 카카오] 보석 쇼핑 투포인터를 활용해서 풀었다. 1. 먼저 본인은 문자열을 상당히 싫어하기 때문에 unordered_map 을 활용해서 문자열을 모두 숫자로 변경하였다. - 즉, 위의 예제에서 나오는 보석이름을 숫자로 변경해서 v라는 벡터에 저장하였다. gams {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"} => v { 1, 2, 2, 1, 1, 3, 4, 1 } 2. START, END 변수를 생성하여 벡터의 인덱스 번호를 저장 시킨 후, 문자열 종류의 개수에 도달하지 않았다면 END변수를 계속해서 증가 시켜준다. ( 위의 예제에서 문자열 종류의 개수는 4개이다. ) 이때, 방문했던 값을 인덱스로 가진 check 라는 벡터에 개수를 하나씩 증가시켜.. 프로그래머스/Level_3 2022. 2. 10. 이전 1 ··· 18 19 20 21 22 23 24 ··· 31 다음 반응형