목록분류 전체보기 (104)
개발자 김수진
[문제] programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr [풀이] next_permutation 함수를 사용해 완전탐색으로 풀었다. 먼저 vector에 숫자와 연산자를 구분해서 담아줬다. 그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다. 우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식..
[문제] programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr [풀이] 1,4,7을 누를경우 왼손 3,6,9를 누를 경우 오른손 나머지는 현재 왼손, 오른손의 위치를 기준으로 가까운 손으로 누르도록 구현 만약 거리가 같다면 왼손잡이,오른손잡이인지 확인하고 이에 맞게 누르도록 [코드] #include #include us..
[문제] www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net [풀이] 보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제 무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해 ..
[문제] www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net [풀이] 각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다. 단 공의 색깔이 같거나 공의 크기가 같다면 잡을 수 없다. 처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다. 하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다. 따라서 다른 방법을 생각했다. 먼저 공의 크기를 ..
[문제] www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다. 숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다. BFS를 사용해서 풀었다. 원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다. 하지만 이 문제에서는 순간이동이 있으므로 이미 방..
[문제] www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net [풀이] 추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다. 아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다. 풀이는 그리디 알고리즘으로 구현했다. 주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때, 더하려는 추의 무게가 sum+2보다 크거나 같다면 sum+1의 무게는 측정할 수 없다. 풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 ..
[문제] www.acmicpc.net/problem/5624 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net [풀이] N개의 수열이 입력으로 주어지고, 하나의 숫자가 앞의 3개의 숫자를 더해서 나타낼 수 있을 때 좋은 수라고 한다. 이 때 입력에서 좋은 수의 갯수를 구해서 출력하면 된다. 좋은 수인지 판단하려는 숫자고 D라고 하면 A+B+C=D를 만족하는 수를 찾으면 된다. 좀더 다르게 생각하면 A+B=D-C 를 만족하는 D를 찾으면 된다. 따라서 D 이전의 숫자들 중에서 A+B의 값을 negativ..
[문제] www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net [풀이] 입력으로 주어진 알파벳을 숫자로 바꿔서 알파벳 합의 최댓값을 구하는 문제이다. 먼저 해당 알파벳이 몇번째 숫자로 얼마나 나왔는지에 따라 알파벳에 대한 숫자를 지정했다. 예를 들어 ABCD라면, A->9, B->8, C->7, D->6 이렇게 큰 자릿수가 큰 숫자를 가지도록 해야 최댓값을 구할 수 있다. 따라서 visited 배열에 해당 알파벳의 자릿수를 저장하였다. 위의 예시로는 visi..