백준108

• 

  [백준 2667번 / C++] 단지번호붙이기 bfs, dfs 자신있는 것으로 해보자. main문에서 함수 호출할 때 증가하는 cnt는 영역을 표현. 함수에서 또 함수를 호출할 때 증가하는 cnt는 영역안의 넓이를 표현. #include #include #include #include using namespace std; int n; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int map[25][25]; int visited[25][25]; int cnt1; void dfs(int y, int x) { cnt1++; for (int i = 0; i = n || ny < 0 |.. 백준/DFS BFS 2022. 1. 24.

• 

  [백준 10026번 / C++] 적록색약 bfs 문제로 풀면 쉽게 나온다. 1. map 에 RGB 색상에 맞게 숫자로 저장. (그대로 해도 상관없음. 저는 보통 숫자로 합니다.) 2. 반복문을 돌면서 해당 위치가 방문되지 않았다면 bfs() 함수를 호출 한다. 3. bfs 기본적인 알고리즘을 사용해 동일한 색상에 인접한 구간들을 다 방문 처리한다. 4. 메인문에서 bfs 호출된 개수를 출력 ( 첫번째 답안 ) 5. map 에서 R과 G를 동일한 번호로 저장. 6. 2~4 번과 동일. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n; int map[100][1.. 백준/DFS BFS 2022. 1. 24.

• [백준 3986번 / C++] 좋은 단어 stack을 활용한 문제이다. 아치형 곡선이 겹치지 않는다는 말이 스택의 최상단 value값과 현재 문자 값이 일치하면 지워주는것을 반복했을 때 스택에 남는 문자가 없다는 뜻이다. #include #include using namespace std; int main() { int n; cin >> n; int result = 0; for (int i = 0; i > ss; for (auto c : ss) { if (s.size() && c == s.top())s.pop(); else s.push(c); } if (s.empty())result++; } cout 백준/구현 2022. 1. 24.

• [백준 1260번 / C++] DFS와 BFS dfs와 bfs의 원리를 터득하기 위해 올린다. 그렇게 어렵지 않은 문제이니 평소에 dfs나 bfs가 애매한 감이 있다면 풀어보길 권한다. #include #include using namespace std; int map[1001][1001]; int visited1[1001]; int visited2[1001]; int n, m, v; queue q; void bfs() { while (!q.empty()) { int v = q.front(); cout v; for (int i = 0; i > a >> b; map[a][b]=1; map[b][a]=1; } visited2[v] = 1; dfs(v); cout 백준/DFS BFS 2022. 1. 20.

• 

  [백준 7576 / C++] 토마토 bfs를 활용해서 풀면 되는 문제이다. 지금까지 풀어왔던 bfs와는 조금 다른 점이 있었다. 익은 토마토가 하나일 수도 있고 두개일 수도 있고 즉, 여러개일 수도 있다. 다시말해, 여러 영역에서 익은 토마토들이 존재하면 동시에 움직이면서 visited를 세팅 해야한다는 것이다. 주인공이 하나가 아니라는 뜻이다. 익은 토마토들을 먼저 다 queue에 넣어줘서 bfs를 시작하게 된다. 먼저 queue에 넣은 익은 토마토들의 x,y 좌표값을 vector에 넣어주고 vector에 들어있는 각 좌표값의 상, 하, 좌, 우 를 모두 살펴보고 갈 수 있는 길이 있다면 그 값들을 모두 다시 큐에 넣어준다. 그러한 작업이 모두 이루어지고 나면 그때, cnt값을 하나 올려주는 것이다. #include #include #i.. 백준/DFS BFS 2022. 1. 20.

• 

  [백준 1062번 / C++] 가르침 이번 문제는 비트마스킹을 활용해서 완전 탐색을 하여 풀었다. 문제에서 n개의 문자열이 주어지는데 공통된 언어로는 "anta"로 시작되고, "tica"로 끝난다는 것이다. 즉, 'a', 'n', 't', 'c', 'i' 이 단어를 배우지 못하면 어떤 단어도 읽지를 못한다. 그렇기 때문에 배우는 알파벳의 개수가 저 알파벳을 포함해서 최소 5개는 돼야 한다는 것이다. 그렇기 때문에 alpa 라는 값에 최초 초기화해야할 숫자는 'a', 'n', 't', 'c', 'i' 이 단어를 가리키는 이진수의 값으로 나타내야한다. 그리고 dfs 를 돌게 되는데 여기서 중요한 점은 첫번째 인덱스를 돌다가 dfs를 돌 때는 그 인덱스 값을 파라미터 값으로 전달 해줘야한다. 즉, dfs 함수 안에서 또 for문이 동작하게 되는데.. 백준/비트마스킹 2022. 1. 20.

• [백준 1561번 / C++] 놀이 공원 이분 탐색을 통해서 풀어야 할 문제다. 먼저 l과 h 에 최소로 들어갈 숫자 1과 최대로 들어가야할 숫자 60000000000을 저장한다. 즉, h에는 "놀이기구 하나에 운행시간 30 * 사람수의 최대" 가 들어가야한다. 내가 이렇게 초기화 안해서 아래 문제에서 매우 화가난적이 있어서 이제는 최대값이 몇인지를 계산부터 한다. 이 백준문제에서도 h값을 무작정 높은 숫자로 했다가 원하는 결과값이 안나올 수 있으니 초기화에 신경쓰자. [Level 3] 입국심사 (C++) 진짜 이 문제에 시간 엄청 많이 쏟아 부었다. 아무리봐도 이게 정답인데 계속 "6번 9번 테스트케이스"에서 오류가 났다. 너무 스트레스 받아서 시간 보니까 3시간이 지나있었다. 비쥬얼 스튜디오 baebalja.tistory.com 로직은 이렇.. 백준/이분탐색 2022. 1. 19.

• 

  [백준 1644번 / C++] 소수의 연속합 증가되는 소수의 값들을 기준으로 투포인트를 활용해서 푸는 문제이다. 에라토네스의 체를 활용하여 N값까지의 소수들을 벡터에 넣어주고 시작 포인터와 끝 포인터를 지정해서 sum값을 갱신해나간다. while문에서 조건이 총 4개이다. 첫번째, sum 값이 n보다 크거나 같으면 시작 포인트를 하나 올려준다. 두번째, 끝 포인트가 벡터의 사이즈까지 도달했으면 break 해준다. 세번째, sum 값이 n보다 작으면 끝 포인트를 증가시켜준다. 네번째, sum과 n 이 같으면 카운팅 해준다. 시작포인트와 끝포인트는 0번째 인덱스를 시작으로 while문이 시작된다. #include #include #include #include using namespace std; vector check; int main() { vec.. 백준/증가수열 & 투포인터 2022. 1. 19.

• 

  [백준 4375 / C++] 1 이 문제는 다음과 같이 풀면 된다. 1 11 111 1111 ............ .............. ................ 이런식으로 이어질텐데 저 값 순서대로 입력받은 값으로 나누었을 때 나누어지면 그 길이를 출력해주면 된다. 하지만, 여기서 주의할 점은 int형의 범위를 넘어설 수 있으니 long long 의 타입으로 설정을 해주어도 문제를 해결 할 수 없다. 즉, long long 64비트에 해당하는 정수값을 넘어설 수 있다는 얘기다. 그렇기 때문에 좀 더 깔끔한 방법이 필요한데 나머지를 초기화 시켜주는 것이다. 예를 들면, n=3 일 때 (첫번째 방법 - 틀린 것) 11에서 3을 나누었을 때 나누어지지 않으니까 1을 더 추가해서 111로 만들어준 후 다시 3으로 나눈 나머지를 확.. 백준/구현 2022. 1. 19.

• 

  [백준 7795번 / C++] 먹을 것인가 먹힐 것인가 먼저, a라는 배열과 b라는 배열을 오름차순으로 정렬시킨다. 그리고 a 배열의 첫번째 값과 b 배열의 첫번째 값과 비교했을 때 a의 값이 더 클경우 b의 인덱스를 하나 증가 시켜준다. 즉, b값이 a의 값보다 같거나 커질때까지 계속해서 증가시켜주다가 해당 반복문을 통과된다면 더 이상 잡아 먹을 수 없는 인덱스를 갖는 b의 값으로 세팅 되어 있을 것이다. 다시 말해서 새로 세팅한 b배열의 인덱스 값이 a값이 잡아먹을수 있는 개수라고 생각하면 된다. 이 개수를 dp라는 배열에 하나하나 저장 시켜주고 출력 할 때 dp의 모든 값을 더해주면 된다. #include #include #include using namespace std; int main() { int n; cin >> n; while (n--) { .. 백준/증가수열 & 투포인터 2022. 1. 18.