본문 바로가기
반응형

코딩 테스트

[백준 1744] 수 묶기 (JAVA)
CodingTEST 2023. 8. 12. [백준 1744] 수 묶기 (JAVA) 백준 1744번 문제 - 수 묶기 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 분석 수열이 주어졌을 때, 순서와 상관없이 더하거나 곱해 최대 값을 알아내 출력해라 곱하는 것은 한번 혹은 안하는 것만 가능하다 해결 키 포인트 Arrays.sort() 사용 그리디 알고리즘 사용 양수와 음수 다르게 계산 양수: 큰 수끼리 곱한다. 음수: 작은 수끼리 곱한다. 그리디 알고리즘 (탐욕 알고리즘) 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 쉽게 말해..
[백준 1715] 카드 정렬하기 (JAVA)
CodingTEST 2023. 8. 12. [백준 1715] 카드 정렬하기 (JAVA) 백준 1715번 문제 - 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 분석 모든 카드를 합치기 위해 사용되는 합치는 최소 횟수를 구하고 출력해라. 해결 키 포인트 그리디 알고리즘 사용 가장 작은 수들끼리 먼저 합치는 것이 이 문제의 핵심 하지만, 시간도 메모리도 여유롭지 않다 List 사용 - 메모리, 시간 초과 ArrayList 사용 - 시간 초과 뽑아내고 넣고 정렬하고의 반복으로 메모리, 시간 초과가 난다 우선순위 큐 사용으로 메모리, 시간을 최소화한다. 그리디 알고리..
[백준 11047] 동전 0 (JAVA)
CodingTEST 2023. 8. 12. [백준 11047] 동전 0 (JAVA) 백준 11047번 문제 - 동전 0 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 분석 가능한 동전 가치 n개를 오름차순으로 입력 받고, 앞서 입력받은 k 값을 만들기 위한 최소한의 동전 수를 구해 출력해라. 해결 키 포인트 그리디 알고리즘 이용 입력 받고, 동전을 확인할 때는 내림차순으로 확인 그리디 알고리즘 (탐욕 알고리즘) 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 쉽게 말해..
[백준 1300] K번째 수 (JAVA)
CodingTEST 2023. 8. 12. [백준 1300] K번째 수 (JAVA) 백준 1300번 문제 - K번째 수 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 분석 N*N 배열을 1차원 배열로 정렬해서, k번째 수를 출력해라 해결 키 포인트 이진탐색으로 해결한다는 마인드를 가져야 함 (본인도 이를 못해서 힌트를 찾음) NxN배열에서 k보다 큰 수를 배열을 만들어서 정렬한 뒤 찾으려면 메모리 초과로 불가능 n보다 큰 값은 i번째의 행의 i / n 개의 수가 존재한다. 3X3배열에서 4보다 큰 값 1번째 행 4 / 1 3 2번째 행 4 / 2 2 3번..
[백준 2343] 기타 레슨 (JAVA)
CodingTEST 2023. 8. 12. [백준 2343] 기타 레슨 (JAVA) 백준 2343번 문제 - 기타 레슨 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 분석 주어진 순서대로 녹음되어야한다. 해당 순서를 따랐을때, 이들을 M개로 나눠서 녹음할 때 가장 최소 강의 길이를 출력해라 (강의 길이는 M개 모두 같아야한다) 해결 키 포인트 값을 입력 받을 때 입력 값들의 최대 값을 start(최소 블루레이 시간) 입력 값들의 합을 end(최대 블루레이 시간) start가 end보다 커질 때까지 반복하면서 블루레이 시간을 알아낸다 start와 end의 중앙 값을 알아내 이를 블루레이 시간으..
[백준 1167] 트리의 지름 (JAVA)
CodingTEST 2023. 8. 11. [백준 1167] 트리의 지름 (JAVA) 백준 1167번 문제 - 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 분석 정점을 입력 받는다 어떤 정점의 간선을 입력 받을 지 먼저 입력 | 간선으로 이어질 정점 | 간선까지의 거리를 입력 | (반복) | -1 1 3 2 -1 입력받은 정점들 간의 거리 중 가장 긴 거리를 출력해라 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 정점의 간선을 순서대로 입력 받는게 아니라, 맨 앞에 정점을 선언하여 불규칙적으로 입력 받을 수 있다 ex) 2 4 4 -1 1 3 2 -1..
[백준 2178] 미로 탐색 (JAVA)
CodingTEST 2023. 8. 9. [백준 2178] 미로 탐색 (JAVA) 백준 2178번 문제 - 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 분석 N X M 미로를 입력 받고, 미로의 첫부터 끝까지 이동할 때 최소 이동 횟수를 구해라 해결 키 포인트 BFS(너비 우선 탐색) 개념 파악 미로에 따른 인접 노드를 어떻게 판단할 것인지 정해야한다. BFS list는 [N][M] 2차 배열 형식으로, 상하좌우로 이동 가능한지 숫자로 삽입한다. ex) 0 = 오른쪽 | 1 = 아래 | 2 = 위 | 3 = 왼쪽 한번 count 증가할 때, 큐에 들어있는 모든 노드를 확인한다. 큐에 넣기 위해 Node..
[백준 1260] DFS와 BFS (JAVA)
CodingTEST 2023. 8. 9. [백준 1260] DFS와 BFS (JAVA) 백준 1260번 문제 - DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 분석 정점 수와 간선, 그리고 시작할 노드를 입력받는다. 이를 토대로 해당 노드에서 시작했을 때 DFS와 BFS를 출력한다. 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 BFS(너비 우선 탐색) 개념 파악 깊이 우선 탐색(DFS) 그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 ..
[백준 2023] 신기한 소수 (JAVA)
CodingTEST 2023. 8. 6. [백준 2023] 신기한 소수 (JAVA) 백준 2023번 문제 - 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 분석 자리수가 입력되면 해당 자리 수 중에서 다음 조건을 만족하는 수(신기한 소수)들을 출력해라 N번자리부터 오른쪽으로 0부터 N-1까지 숫자를 같이 봤을 때 모든 수가 다 소수인 수 ex) N = 4 | 주어진 숫자 = 2333 일 때 해당 수는 신기한 소수에 포함 (다음 표 참고) i N부터 i까지 오른 쪽 숫자 소수 판별 0 2 O 1 23 O 2 233 O 3 2333 O 해결 키 포인트 DFS(깊이 ..
[백준 11724] 연결 요소의 개수 (JAVA)
CodingTEST 2023. 8. 3. [백준 11724] 연결 요소의 개수 (JAVA) 백준 11724번 문제 - 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 분석 입력된 간선들을 토대로 정점들의 연결을 알아내, 연결 요소의 개수를 알아내 출력 해결 키 포인트 DFS(깊이 우선 탐색) 개념 파악 연결 요소 개념 파악 연결 요소: 각 노드들이 뭉쳐진 묶음 개수 간선을 입력받아서 각 정점에 존재하는 연결 노드를 알아내야 한다. 해당 정보를 가지고, 후에 연결 요소 개수를 알 수 있다. 모든 정점을 확인했는지 판..
[백준 10989] 수 정렬하기 3 (JAVA)
CodingTEST 2023. 8. 1. [백준 10989] 수 정렬하기 3 (JAVA) 백준 10989번 문제 - 수 정렬하기 3 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 분석 : 오름차순으로 정렬해서 출력해라 해결 키 포인트 오름차순 정렬 Arrays.sort() 사용 기수 정렬 사용 중요한 포인트는 메모리 제한(JAVA일 경우, 512MB)을 지켜야 한다는 것이다. 최대 10,000,000개의 데이터를 입력 받은 후에 데이터를 정렬해야하는데 512MB는 메모리 제한을 고려해서 코딩해야한다는 것 기수배열 정렬할 때 최대 세개의 배열 사용 가능 int [] nums = new int [N] → 실제 입력..
[백준 1517] 버블 소트 (JAVA)
CodingTEST 2023. 7. 29. [백준 1517] 버블 소트 (JAVA) 백준 1517번 문제 - 버블 소트 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 문제 분석 : 오름차순으로 정렬할때 일어나는 swap 개수를 출력해라 해결 키 포인트 오름차순 정렬 병합 정렬 병합 정렬하면서 앞 배열의 값보다 뒷 배열의 값이 더 작을 때 swap 개수 증가 swap 개수 누적 배열 1 [0하고 1] 3[0] 2[1] 1[2] 2 [0하고 2] 2[1] 3[0] 1[2] 3 [1하고 2] 2[1] 1[2] 3[0] 3 1[2] 2[1] 3[0] 증가되는 swap 개수 ..
반응형

티스토리툴바