본문 바로가기
반응형

전체 글1305

[HackerRank] Cavity Map 출처: https://www.hackerrank.com/challenges/cavity-map/problem 가장자리를 제외한 cell 영역에서 cavity인지를 판단하는 문제이다. 'Cavity 여부'는 해당 지점의 값이 상하좌우 값 보다 높을 때이다. 해당 지점을 [X]로 해서 표시해서 출력한다. 문제 Test Case 중 input data 입력 방식이 Sample Case와 달리 공백으로 주어져서 제출코드에서는 공백을 없애는 과정을 추가함. import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Solution { public static void main(String[] args) { Sca.. 2021. 2. 18.
[HackerRank] 3D Surface Area 출처: https://www.hackerrank.com/challenges/3d-surface-area/problem Input 3 3 1 3 4 2 2 3 1 2 4 Output 60 윗면, 아랫면 각 Cube의 높낮이와 상관없이 h * w * 2이다. 그렇기에 옆면의 높이를 비교해서 총 면적을 구한다. import java.util.Arrays; import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); int[][] cube = new int[h][w];.. 2021. 2. 18.
[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.
반응형

티스토리툴바