본문 바로가기

c++33

[백준/C++] #2467 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2467   알고리즘: two pointer 풀이 + 코드가장 기초적인 투포인터 문제다.(정렬된) 용액 특성들을 배열에 넣고, 두개의 포인터를 이용하여 배열 값들의 합을 구하며 0과 가장 가까운 값이 나타나면 답을 갱신한다.  #include #include #include #include #define MAX 100001#define INF 987654321#define endl "\n"using namespace std;/*2467번 용액산성 용액: 1부터 1,000,000,000, 알칼리성 용액: -1부터 -1,000,000,000같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합같은 양의 두 용액을 혼합하여.. 2024. 7. 3.
[백준/C++] #1484 다이어트 (Two Pointer) 문제https://www.acmicpc.net/problem/1484   구상두 제곱수의 차가 G가 되는 경우를 출력하는 문제였다. 제곱수로 이루어진 배열 만들고, 투 포인터로 두 수 찾아서 출력하면 되는 간단한 문제였다.  풀이 + 코드G는 100,000보다 작거나 같은 수이기에 두 제곱수의 차가 100,000보다 큰 최대한 작은 제곱수를 구해보면 대략 51,000 이 나온다. (51,000^2 - 50,999^2 = 101,999) 제곱수로 이루어진 배열 (1^2 ~ 51000^2) 만들고 투 포인터 이용해서 제곱수의 차 구하면 된다.  int형의 크기는 4 byte / -2,147,483,648 ~ 2,147,483,647 인데, 51000^2는 2,601,000,000로 int 범위를 넘어섰다. .. 2024. 7. 3.
[백준/C++] #1644 소수의 연속합 (Two Pointer) 문제https://www.acmicpc.net/problem/1644 구상"연속된" 소수의 합으로 나타낼 수 있는 경우를 구하라길래 바로 two pointer를 사용한 prefix sum 형태의 배열이 떠올랐다. 그러면 소수로 이루어진 배열이 필요한데, 어떻게 소수를 판별해서 소수로만 이루어진 배열을 만들까? 라는 생각이 들었다. 실제로 해당 부분을  오랜 시간 고민했고, 가장 구현이 빡셌다. 소수 판별은 N까지만 되면 되었고, 4부터 판별 시작하면 되었다. 4부터 해당 수에 대한 배수들을 구해서 false로 판별하면 되겠다는 생각이 들었다. 배수는 2의 배수부터 sqrt(N)의 배수까지 확인하면 되었고, 배수라는게 겹치는 건 생각안해도 되기에 제곱수부터 고려하면 되었다.  표로 설명하는게 이해하기 쉬워.. 2024. 7. 3.
[백준/C++] #16946 벽 부수고 이동하기 4 (Flood Fill / BFS) 문제https://www.acmicpc.net/problem/16946알고리즘: Flood Fill / bfs 구상처음에는 단순하게 bfs를 통해 얼마나 많은 칸으로 이동할 수 있는지 구하는 줄 알고, 엥 왜 골드 3이지? 하고 풀었는데, 배열 크기가 최대 1000*1000까지 커질 수 있기에 시간초과가 났다.. 그래서 긴 탐색 시간을 줄여야한다고 생각했다. 하지만, 각각의 벽에서 이동할 수 있는 칸의 개수를 알아내야 했기에 이땐 변함없이 이중 for문이 필요했다. 그래서 떠오른게, 이동할 수 있는 칸들은 뭉텅이로 존재하는데, 뭉텅이의 크기를 파악하면, 벽의 상하좌우에 위치한 뭉텅이들의 크기만 고려할 수 있지 않을까?였다. 즉, 어떤 칸과 연결된 영역을 찾는 알고리즘인 flood fill을 통해 전처리만.. 2024. 7. 3.

티스토리툴바