백준108

• 

  [백준 3055번 / C++] 탈출 bfs 문제이다. #접근방법 1. 고슴도치, 물, 비버의 굴 위치를 저장 후 bfs() 호출 (물과 고슴도치의 위치를 각각 queue에 push) 2. 먼저 물의 위치가 저장된 queue에서 물의 좌표값을 pop 하면서 물이 이동할 수 있는 인접한 구역에 물로 바꾼다. 3. 고슴도치의 위치에서 상하좌우로 갈수 있는 경우 dis라는 배열에 더해나간다. 4. 고슴도치가 더이상 갈 수 있는 길이 없을 때 또는 고슴도치가 비버의 굴 위치에 도달했을 때 리턴 해준다. #include #include #include #include #include using namespace std; int m, n, a_y, a_x; queue w; //물이 차있는 곳 queue q; //고슴도치가 이동할 수 있는 곳 vecto.. 백준/DFS BFS 2022. 2. 17.

• 

  [백준 13549번 / C++] 숨바꼭질 3 bfs를 문제를 활용해서 풀면 된다. #접근방법 1. 방문 배열 100001개 생성 후 큰 값으로 초기화 2. 수빈이의 현재 위치 queue에 push. 3. queue에 들어간 수빈이의 현재 위치에서 갈 수 있는 경로는 현재 값에서 -1 , +1, *2 이다 현재 위치에서 3가지 방향의 값을 연산하여 해당 인덱스의 visited값을 갱신해간다. 4. queue에 값이 있을 동안 반복문을 돌리며 수빈의 위치와 동생의 위치가 동일하다면 해당 인덱스의 visitied값을 출력하고 종료한다. #include #include #include #include #include using namespace std; int n, k; int visited[100001]; queue q; void bfs() { int .. 백준/DFS BFS 2022. 2. 17.

• 

  [백준 2230번 / C++] 수 고르기 투포인터 문제이다. 접근 방법 1. 벡터 오름차순 정렬 및 start, end 포인터 생성 후 0으로 초기화 2. result 값은 벡터 원소중 최솟값과 최댓값의 차이값으로 저장 3. end포인터의 벡터 원소값이 m보다 작으면 end 포인터 증가 4. end포인터의 벡터 원소값이 m보다 크거나 같다면 result 최솟값 갱신 (차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램) #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); int s, e; s = 0; .. 백준/증가수열 & 투포인터 2022. 2. 16.

• 

  [백준 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.