목록분류 전체보기 (104)
개발자 김수진
[문제] programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [풀이] 에라토스테네스의 체 , next_permutation, set를 모두 공부할 수 있는 문제 에라토스테네스의 체는 어떤 수가 소수인지 아닌지 판별할 때 사용된다. 1. 소수를 판별할 만큼 배열을 할당하고 배열을 자기 자신으로 초기화한다. 2. 2부터 자기 자신에 해당하는 것을 제외하고 배수들은 모두 0으로 바꿔서 소수에서 제외시킨다. #defin..
[문제] programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr [풀이] input으로 숫자 number와 number에서 제외할 숫자의 개수인 k가 주어진다. number에서 k개의 숫자를 제거하여 만들 수 있는 최댓 값을 구하면 된다. 처음에는 DFS를 사용하여 모든 경우에 대해 다 확인해봤는데 생각해보니 number의 길이가 1부터 1,000,000까지이다. 그래서 다른 방법을 생각해보니 number의 시작부터 큰 수를 골라 총 number.size()-k의 숫자를 골라서 answer로 return 하면 된다. 1. number의 처음부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다. 2..
[문제] www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net [풀이] NXM으로 표현되는 맵이 문제 입력으로 주어진다. 맵에는 벽이 존재하는데 최대 한번 벽을 부수고 이동할 수 있다. 이 때 시작점에서 (N,M)까지의 최단 거리를 구하면 된다. 최단거리를 구하는 문제라서 BFS를 사용하고 pos 구조체에 crash 변수를 추가하여 이전 경로에서 벽을 부수고 왔는지를 확인했다. 원래 visited 배열은 2차원 배열로 아래와 같이 선언했었..
[문제] www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net [풀이] N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다. 규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다. DP[i] = DP[i-1]+DP[i-2]; [코드] 시간 : 0ms #include #define MAX 90 using namespace std; long long DP[MAX]={0,}; int N; int main(void) { ci..
[문제] www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [풀이] DP를 사용해서 이전 경로까지의 최대, 최솟값을 저장해놓고 이전 경로와 현재 위치의 값을 더해서 최대, 최솟값을 구했다. 처음에는 N의 범위가 N(1 ≤ N ≤ 100,000)이므로 DP배열을 [100001][3]의 크기고 잡고 시작했는데 메모리 초과가 나왔다. 생각해보니 문제 조건에서 주어진 메모리 제한은 4MB인데 [100001][3]의 크기로 잡고 풀면 min, max 배열이 2개 이므로 4MB를 넘어..
[문제] www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net [풀이] 처음에는 2중 for문 사용해서 하나를 기준으로 현재 지원자를 기준으로 서류 점수가 더 우수한 지원자가 있다면 면접 점수를 비교하는 방식으로 풀었다. 모든 면접자에 대해서 한번씩 모두 비교해야 하므로 당연히 시간초과가 나왔다. 따라서 두번째에는 서류 점수를 기준으로 오름차순으로 정렬하고 한명의 지원자를 기준으로 앞에 있는 지원자보다 면접 점수도 낮다면 제외하였다. 이렇..
[문제] www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net [풀이] MST의 가중치를 구하는 문제로 Kruskal 알고리즘을 사용해서 풀었다. 정점간의 연결 정보를 입력 받고 벡터에 저장했다. 가중치를 기준으로 벡터를 정렬하고 , 가중치가 작은 것부터 Union-Find를 사용해 묶어줬다. Union을 하기 전에 Find를 통해 부모가 같은지 미리 확인한다. ( 부모가 같은 상태에서 union을 해버리면 사이클..
[문제] www.acmicpc.net/problem/3020 [풀이] 처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면 반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 따라서 이분 탐색 방법으로 풀어야겠다고 생각했다. lower_bound는 x 이상인 값이 처음 나오는 index를 return하고 upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다. [코드] 시간 : 60ms ( 이분 탐색 직접 구현해서 다시 풀어봐야겠다.) #include #include #include #define MAX 100000 using name..