알고리즘, 문제해결103 [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [프로그래머스] 입실 퇴실 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 굉장히 좋은 문제라고 생각합니다! 저는 처음에는 약간 단순한 방법으로 풀었는데... 1. 들어온 시간 기준 a > b, 나간 시간 기준 a < b이거나 그 반대이면 반드시 만난다. 2. 그렇지 않은 경우, 들어온 두 사람의 시간 사이에 들어오지 않은 사람이 먼저 나간 사람보다 더 먼저 나간 경우, 두 사람은 반드시 만난다. 위 조건을 매번 확인하는 식.. 2021. 9. 17. [백준 3687번] 성냥개비 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다. 그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다. 성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함). 1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다. 성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하.. 2021. 9. 9. [백준 11049번] 행렬 곱셈 순서 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 제가 자신없어 하는 편인 DP를 이용하는 문제입니다. 2차원 배열 dp[i][j]를 만드는데, 이때 dp[i][j]는 행렬 i에서 j까지 곱했을 때의 최소 곱연산 횟수라고 정의합니다. 맨 처음에는 배열 matrix에, matrix 1번부터 n번까지 각각의 row와 column의 길이를 입력받습니다 (저는 pair를 이용함(. 다음으로, 주어진 모든 m.. 2021. 9. 8. [백준 13422번] 도둑 난이도: 골드 IV 문제 링크: https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 시간 제한 1초인 문제입니다. 문제의 요구점을 간단히 짚고 넘어가자면 다음과 같습니다. 배열 (집)은 원형으로 이루어져 있으며, 총 n개 (n은 10만 이하의 자연수)로 이루어져 있다. m은 도둑이 한번에 털어야 하는 집의 갯수이며, 총 n개 이하의 자연수로 이루어져 있다. 또한, 도둑은 서로 인접한 집만 털 수 있다. 각 경우의 수에 대해, 도둑이 턴 m개의 집의 금액의.. 2021. 9. 7. [백준 5430번] AC 난이도: 골드 V 문제 링크: https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 각 테스트 케이스별로 입력은 다음과 같이 들어옵니다. RDD 4 [1,2,3,4] 즉 맨 첫줄과 세 번째 줄은 string 형식이고, 두 번째 줄은 int 형식이 됩니다. 이 문제를 해결하려면 두 가지 포인트를 신경써야 합니다. 1. 입력받은 string 형태의 수열을 실제 int형 배열로 변환하기 2. 시간 제한 문제 1의 경우, 예전에 제가 블로그에 올렸던 C++에서 문자열을 쉽게 자르는 방법이 있습니다 (링크). 문자.. 2021. 9. 6. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음
