백준문제풀이36 [백준][C++] 1629번: 곱셈 <187> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 입력으로 받을 A, B, C 모두 int형으로 담을수 있는 값이다. 하지만 A^B를 한다 했을때, 이를 직접 계산하려면 1) 변수 크기도 엄청 커지게 된다. 2) 자료의 크기 1억당 => 1초 정도 걸리기 때문에, 2^2,147,483,647 만 계산하려 해도 21초나 걸린다. 따라서 이를 분할정복으로 해결해야 한다. 예를들어 2^8을 구해야 핸다.. Algorithm/백준 2022. 2. 17. [백준][C++] 16719번: ZOAC <186> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 와 이번문제 나는 어려웠다. 단순하게 A부터 찾아서 추가하는 식으로 해결하기도 어렵다. 왜냐하면 문자는 중복이 가능하기 때문이다. A가 2개 이상이라면 어디부터 시작해야 할까? 이또한 문제이다... 따라서 나는 다음과 같은 알고리즘으로 문제를 해결해 나갔다. (다른분의 풀이를.. Algorithm/백준 2022. 2. 14. [백준][C++] 2261번: 가장 가까운 두 점 <184> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 아 이번문제 너무어렵다...... 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 2가지 방식으로 구현이 가능한데, 라인 스위핑 알고리즘 or 분할정복으로 해결이 가능했다. 분할정복에 대한 개념은 있는 상황이라, 좀더 처음 접하는 개념인 라인 스위핑 알고리즘으로 접근하였다. 다음 글은 내.. Algorithm/백준 2022. 2. 12. [백준][C++] 1939번: 중량제한 <183> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 BFS + 이분탐색(파라메트릭 서치) 가 포함된 문제이다. 이분탐색은 가능한 범위 내에서 탐색을 해야 한다. 답으로 가능한 가장 작은 중량제한은 0 부터 ~ 가장 무거운 중량제한은 입력으로 받은 다리의 중량 최대.. Algorithm/백준 2022. 2. 7. [백준][C++] 2661번: 좋은수열 <182> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 DFS 탐색을 진행하다가, 불가능한 경우가 나오면 더이상의 탐색 진행을 하지않고 바로 반환하는 백트래킹 문제이다. 어떠한 수열이 주어질때 "나쁜수열" 인지를 파악하는것 이 핵심이다. 다만 완전탐색 방식으로 길이가 N인 모든 수열의 경우를 만들고 "나쁜수열"인지 파악하는것은 시간초과 .. Algorithm/백준 2022. 2. 4. [백준][C++] 3980번: 선발 명단 <181> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 나는 next_permutation을 통해 11명의 순열을 구한후, 그 배열이 0값을 포함하고 있지 않다면 결과를 도출하는 풀이로 풀었다. 하지만 시간초과가 발생하여 버렸다. 아마 순열을 구하는 과정에서 아예 답을 구할 수 있는데, 순열을 구한후, 다시 한번 순회를 돌기 때문 아닐까 싶다? 따라서 직접.. Algorithm/백준 2022. 2. 3. [백준][C++] 12919번: A와 B 2 <180> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 문제는 문자 S => T를 직접 만들려하면 해결할수가 없는 문제이다. 매번 2가지 선택 사항이 있는데, 문자열의 총 길이가 49까지 가능하니, 2^49가 되므로, 시간초과가 발생할것이다. 따라서 역으로 T => S로 조건에 맞게 변경이 가능한지를 확인해야 한다. 조건 1) 주어진 S의 문자열 맨 끝이 'A'라면 맨 뒤 문자 하나를 제거해 준다. 조건 2) 주어진 문자열 S의 맨앞 문자가 'B'라면, 문자열 전체를 뒤집은 후 맨뒤로온 'B'를 제거해 준다. 여기서 주의할점이 1번과 2번 조건을 else if 로 묶으면 안된.. Algorithm/백준 2022. 1. 31. [백준][C++] 2573번: 빙산 <179> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 문제는 학습할 부분이 많은 문제이다. 1) 정점을 각각 따로 처리하면 안된다. 바로 바닷물과 접해있는 칸 수 만큼 빙산을 녹이는 과정에서, 정점 하나하나 마다 진행하면 안된다는 점 이다. 다음 그림을 살펴보자. 위의 주어진 맵에서 빨강색으로 표시된 정점에 대해서 살펴보자. 빙산의 높이가 4이고, 주변에 바닷물(0)이 2곳 인접해 있기 때문에 1년이 지나면 빨간 곳의 높이는 2가 된다. 파랑색으로 표시된 정점은 1년이 지난다면 인근 바다가 1곳이라 2가 된다. 하지만, 여기서 저 빨강색과 파랑색 사이(1,1지점) 에 있는.. Algorithm/백준 2022. 1. 26. [백준][C++] 13397번: 구간 나누기 2 <178> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 든 생각은 구간을 어떻게 나누지? 였다. 또한 brute force 계열의 문제라고 생각했다. 하나하나 구간을 나눠서 찾아야 한다 생각했다. 하지만 N이 5천이나 되기 때문에 시간안에 불가능할것 같았다. 최대 5천명을, 3구간으로만 나누라.. Algorithm/백준 2022. 1. 25. [알고리즘] 비트마스크 조합, 부분수열 예전부터 비트마스크 활용하는거 정리 한번 해야지... 해야지 하다 안해서... 이번에 정리해본다. 먼저 부분수열부터 문제를 통하여 알아봅시다. 1. 비트마스크를 활용하여 부분 수열 구하기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 위 백준 문제를 통하여 설명해보겠습니다. 문제의 예시처럼 5개의 원소가 있다고 해봅시다. -7 -3 -2 5 8 각 원소 하나마다 (포함 or 미포함) 둘중 하나.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [백준][C++] 14852번: 타일 채우기 3 <177> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 생각했던 방식은 DP[N]을 만들기 위해 끝부분에 2*1 채우는 방식과, 2*2 즉, 다음 그림과 같은 방식이 끝이라고 생각했다. 따라서 점화식이 DP[N] = DP[N-1]*2 + DP[N-2]*3 이라 생각했다. 하지만 예외가 있었다. 길이가 3, 4, 5 ... 등 다음과 같은 추가적인 case가 존재했다. 각각 길이가 3, 4인 case 이다. 즉 DP[N] = DP[N-1]*.. Algorithm/백준 2022. 1. 21. [백준][C++] 17135번: 캐슬 디펜스 <176> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 구현 문제는 생각의 순서를 정하는것이 중요하다. 어떤 순서로 진행되어야 할까? 1. 3명의 궁수를 N+1 번지에 배치한다. 2. 원본 map을 복사한 copyMap 만들기(궁수 배치의 case 마다 한번씩 복사해주어야 한다) 3. 왼쪽 궁수부터 BFS 탐색을 진행하면서, 가장 가까운 적을 공격표.. Algorithm/백준 2022. 1. 19. 이전 1 2 3 다음
