백준108

• 

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

• 

  [백준 12851번 / C++] 숨바꼭질 2 bfs를 활용해서 풀면된다. 1. 수빈이와 동생의 위치가 처음부터 같을 경우 바로 결과값 출력 2. 그렇지 않다면 수빈이의 x좌표값과 시간을 queue 넣고 bfs 호출 3. 1초당 수빈이가 갈 수 있는 경우의 수는 총 3가지 이므로 방문하지 않거나 범위를 넘어서진 않는다면 queue에 push하고 bfs 호출 4. 만약 수빈이의 위치가 처음으로 동생의 위치에 도달했을 때 시간 저장 5. 같은 시간대에 도착한 경우가 여러개인 경우 result2 의 값을 증가 #include #include #include #include #include using namespace std; queueq; int n, k; int visited[100001]; int result1, result2; void bfs() {.. 백준/DFS BFS 2022. 2. 10.

• [백준 3474번 / C++] 교수가 된 현우 해당 문제는 어떻게 접근해야할지 먼저 생각을 하고 들어가자. 3! 이면 끝자리의 0의 개수가 몇개인가? 0개이다. 5! 이면 끝자리의 0의 개수가 몇개인가? 1개이다. 10! 이면 끝자리의 0의 개수가 몇개인가? 2개이다. 18! 이면 끝자리의 0의 개수가 몇개인가? 3개이다. 뭔가 규칙이 보인다. 숫자에 0이라는 수를 끝에 위치하게끔 만들수 있는 수는 10이다. 10을 만들기 위해서는 2와 5가 필요하다. 그렇기 때문에 n!에서 2와 5의 쌍을 가지고 있는 개수를 세주면 된다. 2의 경우에는 짝수이면 모두 포함되기 때문에 굳이 카운트 해 줄 필요가 없다.(워낙 많기 때문) 그렇기 때문에 5라는 숫자가 총 몇개 들어가있는지만 카운트 해주면 된다. 만약, 18! 에서 5의 개수는 18/5 를 해주면 몫이 .. 백준/구현 2022. 2. 10.

• 

  [백준 1940번 / C++] 주몽 투포인터를 활용한 문제이다. 두개의 재료가 합쳐져서 M이라는 값과 일치해야만 갑옷이 만들어진다는 점을 고려해서 풀어보자. 1. 벡터에 재료들의 고유번호를 오름차순으로 정렬해서 저장한다. 2. 첫번째 원소와 마지막번째 원소를 S와 E라는 변수에 각각 저장한다. 3. 벡터의 S 포인터의 원소와 E 포인터의 원소를 더했을 때 M인지를 확인한다. - M보다 작다면 S의 값을 올려준다 (원소의 값을 증가시키는 역할) - M보다 크다면 E의 값을 내려준다 (원소의 값을 감소시키는 역할) - M가 일치하면 RESULT 값을 증가시켜 준다. #include #include #include using namespace std; int main() { int n, m; vector v; cin >> n >> m; for .. 백준/증가수열 & 투포인터 2022. 2. 10.

• 

  [백준 12869번 / C++] 뮤탈리스크 스타크래프트를 즐겨하는 사람으로서 뮤탈리스크란 문제를 보고 호기심때문에 풀어봤다. (난 테란 유저이기 때문에 뮤탈리스크를 매우 싫어한다.) 1. 사기 유닛 뮤탈리스크는 소중한 SCV를 최대 3마리까지 공격 가능하다. 순서에 따른 공격 데미지는 총 6가지의 경우가 있으므로 이차원 벡터에 저장하였다. 2. 최대 3마리까지 공격 가능하니 3차원 dp배열을 생성하여 해당 배열에 최소 공격횟수를 저장해준다. 3. 이후 다른 재귀에서 해당 dp배열을 참조할 시 기록해 뒀던 값을 반환하여 사용하면 된다. * 본인은 next_permutation 함수를 활용하여 완전 탐색으로 구현을 시도했지만 시간 초과가 발생하여 3차원 DP를 활용하였다. #include #include #include #include #includ.. 백준/DP 2022. 2. 9.

• 

  [백준 1911번 / C++] 흙길 보수하기 [백준 2170번 / C++] 선 긋기 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬하자. 2. 첫번째 벡터 쌍의 원소 값 두개(X, Y)를 start 와 end 라는 변수에 각각 저장하자. 3. 벡터 사이즈만큼 반복문을 돌 baebalja.tistory.com 위의 문제와 유사하니 풀어보길 권한다. 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬. 2. 첫번째 벡터 쌍의 시작위치값을 start에 저장하고 end 라는 변수에는 시작위치값 + 물웅덩이 길이를 저장. 3. 벡터 사이즈만큼 반복문을 돌린다. 이때, 벡터 쌍의 원소 중 시작 위치 값이 start 변수의 값보다 크다면 이전 웅덩이에서 활용했던 널빤지가 현재 웅덩이에 영향을 주지 않.. 백준/증가수열 & 투포인터 2022. 2. 9.

• 

  [백준 2170번 / C++] 선 긋기 투포인터를 활용한 문제이다. 1. pair 구조를 가진 벡터를 오름차순으로 정렬하자. 2. 첫번째 벡터 쌍의 원소 값 두개(X, Y)를 start 와 end 라는 변수에 각각 저장하자. 3. 벡터 사이즈만큼 반복문을 돌린다. 이때, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 작거나 같으면 선이 이어진다는 의미이므로, 벡터의 두번째 원소의 값과 end 변수에 저장된 값 중 큰 값으로 end 변수를 갱신해나간다. 만약, 벡터의 첫번째 원소의 값(X)이 end 변수의 값보다 크다면 선이 겹치지 않았다는 의미이므로 start, end 변수에는 해당 벡터의 원소의 값들로 새로 저장해준다. #include #include #include using namespace std; int main() { ios.. 백준/증가수열 & 투포인터 2022. 2. 9.

• 

  [백준 2670번 / C++ ] 연속부분최대곱 1. double 타입의 벡터 배열 생성. 2. 벡터 첫번째 원소를 가지고 있는 b라는 변수 생성. 3. 벡터의 사이즈만큼 반복문 돌리면서 연속된 값의 곱셈이 현재 위치의 벡터 원소보다 작으면 b 변수에 현재 벡터 원소 값 저장. 그렇지 않다면 연속된 값 곱하기. 4. reuslt 값이 최대값인 것을 계속 갱신하기. #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n,0); for (int i = 0; i > v[i]; } double b = v[0]; double result = 0; for (int i = 1; i v[i]*.. 백준/증가수열 & 투포인터 2022. 2. 8.

• [백준 14889번 / C++] 스타트와 링크 1. 비트연산을 통해서 두개의 팀으로 나올 수 있는 모든 경우의 수를 구함. ex) abcdefgh 11001010 {a,b,e,g}, {c,d,f,h} 두팀으로 나뉘어짐. abcdefgh 11001011 {a,b,e,g,h}, {c,d,f} 다른 한팀이 인원이 더 많으므로 continue; 2. 이차원 배열에서 해당하는 팀원의 인덱스값을 통해 팀의 sum 값을 갱신해나간다. 3. 두 팀의 차이값이 이전에 구했던 차이값보다 작으면 계속해서 갱신 #include #include #include #include #include using namespace std; int min_number = INT_MAX; int main() { int n; cin >> n; vector v(n, vector(n, 0)).. 백준/비트마스킹 2022. 1. 28.