본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2577 숫자의 개수 출처: https://www.acmicpc.net/problem/2577 Input 150 266 427 Output 3 1 0 2 0 0 0 2 0 0 3개의 3자리 자연수들의 곱 결과에서 숫자 0 ~ 9가 몇개 이루어져 있는지 확인하는 문제입니다. 곱한 결과를 나머지 연산으로 한자리씩 구해서 ans[] 배열에서 세어줍니다. ans[0~3] = x → 숫자 0~9가 x번 나타남을 의미합니다. #include int A, B, C, result, ans[10]; int main() { // freopen("input.txt", "r", stdin); scanf("%d %d %d", &A, &B, &C); result = A * B * C; while (result) { ans[result % 10]++;.. 2021. 2. 17.
[BOJ] 백준 2487 섞기 수열 출처: https://www.acmicpc.net/problem/2487 Input 6 3 2 5 6 1 4 Output 6 이 문제를 주어진 카드 순서를 섞기 수열에 맞게 위치를 변경해가며 처음 상태로 돌아왔는지 확인하는 것은 TLE 발생 #include const int MAX_N = 20000; int N, arr[MAX_N + 5], pivot[MAX_N], temp[MAX_N + 5]; void shuffleCard() { for (int i = 1; i 2021. 2. 17.
[BOJ] 백준 7578 공장 출처: https://www.acmicpc.net/problem/7578 Input 5 132 392 311 351 231 392 351 132 311 231 Output 3 A, B 배열이 주어졌을 때, 교차점의 개수를 어떻게 구할지 생각해야 합니다. 먼저 A배열을 모두 입력 받고, B 배열 원소를 한개씩 입력받을 때, A 배열상 뛰쪽에 위치하는 숫자의 개수로 확인합니다. ① [392]: 숫자 외에는 존재하지 않으므로 +0 ② [392 → 351]: A 배열에서 392는 351 앞쪽에 위치하므로 +0 ③ [392 → 351 → 132]: 392, 351 두 개 모두 132보다 뒤에 위치하므로 +2 ④ [392 → 351 → 132 → 311]: 351만 311보다 뒤에 위치하므로 +1 ⑤ [392 → .. 2021. 2. 17.
[BOJ] 백준 2465 줄 세우기 출처: https://www.acmicpc.net/problem/2465 Input 12 120 167 163 172 145 134 182 155 167 120 119 156 0 1 0 0 3 2 6 7 4 6 9 4 Output 134 167 120 119 156 120 167 182 155 163 172 145 height[] = {120, 167, 163, 172, 145, 134, 182, 155, 167, 120, 119, 156} S = {0 1 0 0 3 2 6 7 4 6 9 4} → answer[] = [134 167 120 119 156 120 167 182 155 163 172 145] 수열 S는 answer[]에서 자기보다 작은 키의 숫자입니다. ex) 마지막 사람의 키 145cm 이.. 2021. 2. 17.
[BOJ] 백준 2630 색종이 만들기 출처: https://www.acmicpc.net/problem/2630 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com 한 변의 길이 N에 대해서 같은 색깔로 이루어져 있는지 검사합니다. - 같은 색깔로 이루어진 경우에는 4등분 하지 않습니다. - 같은 색깔로 이루어져 있지 않다면 4등분 합니다. 이때, 분할정복을 착안해서 4등분된 곳의 좌측 상단 좌표와 영역의 길이를 넘겨줍니다. 전달된 정보를 바탕으.. 2021. 2. 17.
[BOJ] 백준 2479 경로 찾기 출처: https://www.acmicpc.net/problem/2479 Input 5 3 000 111 010 110 001 1 2 Output 1 3 4 2 ① src → dest로 가는 최단 경로를 BFS 탐색 ② BFS 조건은 아래와 같습니다. - 자기자신 제외 - vistied[] 배열로 더 좋은 최단거리 - 해밍 거리 = 1인 경우 ※ [BOJ] 3449 해밍 거리는 문자열과 xor 연산을 이용해서 처리 ③ 경로 추적할 때는 trace[y] = x를 이용합니다. : y 지점을 방문하기 위해 바로 직전에 지점 x 재귀함수로 역추적하며 도착점에서 출발점까지 거슬러 찾아갑니다. #include const int MAX_N = 1000; const int MAX_K = 30; const int INF.. 2021. 2. 17.
[BOJ] 백준 3449 해밍 거리 출처: https://www.acmicpc.net/problem/3449 Input 4 0 1 000 000 1111111100000000 0000000011111111 101 000 Output Hamming distance is 1. Hamming distance is 0. Hamming distance is 16. Hamming distance is 2. 최대 100자리이므로 int, long형으로 처리할 수 없기에 문자열로 받아서 처리해야 합니다. ① 두 문자열을 입력 받습니다. ② 문자열의 길이를 구해서 for문으로 한 자리씩 접근합니다. ③ xor 비트 연산을 통해서 해밍 거리를 도출합니다. ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 .. 2021. 2. 17.
[BOJ] 백준 2666 벽장문의 이동 출처: https://www.acmicpc.net/problem/2666 Input 7 2 5 4 3 1 6 5 Output 5 문제 이해: 미닫이 문으로 구성된 옷장을 연상하면 됩니다. 벽장문을 최소한으로 움직여서 주어진 순서대로 벽장을 사용을 사용하는 것입니다. 벽장의 문을 움직이면 열려있던 곳은 닫히게 되고, 문이 위치한 곳은 열리게 되는 구조로서 한칸씩 움직일 수 있으므로, 만약 x 위치에서 y위치에 존재하는 문을 사용한다면 ▶ 이동 횟수 = abs(x - y) 문을 선택하는 경우는 2가지로, 초기에 주어지는 첫번째, 두번째 벽장문을 선택하는 Case ▶ DFS(첫번째 문의 위치, 두번째 문의 위치, 현재 열려는 벽장 위치 순서, 누적 이동 횟수) #include int N, M, ans; int.. 2021. 2. 17.
[BOJ] 백준 2668 숫자 고르기 출처: https://www.acmicpc.net/problem/2668 Input 7 3 1 1 5 5 4 6 Output 3 1 3 5 윗줄에서 N ~ 0개의 정수를 뽑아서 둘째 줄과 조합되는 경우를 완전 탐색하는 경우는 TLE 발생 DFS 탐색으로 그래프 탐색하듯이 cycle이 형성되는 구간을 찾는 문제입니다. 첫째 줄: [1 2 3 4 5 6 7] 둘째 줄: [2 3 4 2 6 1 7] ① for문으로 각 정점을 출발점으로 DFS 탐색합니다. 이때, 이미 조사가 끝난 구간(visited[])는 그냥 넘어갑니다. ② DFS 탐색에서 cycle 구간을 파악하기 위해서는 chk[] 배열에 표시합니다. 한번의 DFS탐색이 끝났을 때, 표시한 chk[] 값을 다시 해제합니다. ③ chk[]로 DFS 탐색 .. 2021. 2. 17.
[BOJ] 백준 2578 빙고 출처: https://www.acmicpc.net/problem/2578 Input 11 12 2 24 10 16 1 13 3 25 6 20 5 21 17 19 4 8 14 9 22 15 7 23 18 5 10 7 16 2 4 22 8 17 13 3 18 1 6 25 12 19 23 14 21 11 24 9 20 15 Output 15 사회자가 부르는 숫자를 target[] 배열에 저장합니다. 해당 숫자를 한개씩 빙고판에 mark() 표시하며 visited[][] 표시합니다. 방문 표시가 끝나면 표시(mark)된 곳에서 가로줄, 세로줄을 확인합니다. 마크된 곳과 별개로 대각선 두 곳도 각각 5곳이 칠해지지 않았다면 계속 확인합니다. ▶ 가로줄, 세로줄 (+ 대각선 2개)를 확인했을 때, "bingo"가 .. 2021. 2. 17.
반응형

티스토리툴바