[Algorithm]5 [Algorithm] 1202. 보석도둑 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 우선순위 큐 + 그리디 보석을 무게기준으로 정렬한다.(오름차순) 가방 정렬(오름차순) 가방 수 만큼 반복하면서 보석을 우선순위 큐에 담는다. (value값 내림차순 정렬) 보석무게가 가방제한보다 커지면 가방 인덱스 증가. 다음 가방시행 전에 우선순위 큐에서 하나 뽑아서 value 누적 import java.io.BufferedReader; import.. 2021. 5. 8. [Algorithm] 백준.17298 오 큰수 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 얼마전 라인 AD-platform 코딩테스트에서 나온 문제와 비슷한 유형의 문제. 100,000,000 이라는 범위때문에 여러 번 탐색하는 순간 시간초과가 발생한다는 것을 유의해서 접근했어야 했는데... 코딩테스트 문제는 오른쪽뿐 아니라 양쪽중에 가장 가까운 수를 출력하는게 목표였던 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io... 2021. 5. 8. [Algorithm] 백준. 1949 우수마을 www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리 & 다이나믹 프로그래밍 껄끄러운 두 가지 방식이 합쳐진 문제. 양방향 그래프이므로, DFS방식으로 탐색하면서 visit 체크를 해서 이후에 되돌아 오는 일이 없도록 했다. 리프노드까지 도착한 후에 올라오면서 선택 시 최대 인원, 비선택 시 최대 인원을 저장하는 방식으로 구현하였다. 조건을 만족하려면, 현재 마을인원을 추가하는 경우엔 이웃한 마을의 인원은 추가되면 안되기 때문에, 이웃한 마을들의 비.. 2021. 4. 23. [Algorithm] 백준. 20056 마법사 상어와 파이어볼 2020년 하반기 삼성 코딩테스트 기출문제인 마법사 상어와 파이어볼. www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 당시 코딩테스트를 응시했을때 10개의 테스트 케이스 중 2~3개가 맞지않아서 풀지 못한채로 마무리해서 아쉬웠던 기억이 난다. 다시 문제를 풀어보니 파이어볼 여러개가 합쳐지고, 나누어지는 과정에서 제자리에서 나눠지도록 구현했어야 했는데, 나눠진 파이어볼을 처음부터 속도만큼 이동하도록 구현한 것이 화근이였던.. 2020. 12. 5. [Algorithm] SWEA. 10570 제곱 팰린드롬 수 ( D3 ) [SWEA] 10570. 제곱 팰린드롬 수 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXO72aaqPrcDFAXS&categoryId=AXO72aaqPrcDFAXS&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 팰린드롬이란? 거꾸로 읽어도 동일한 문자(숫자)를 말한다. 보통 문자열의 절반까지 반복문 돌려 n번째 문자와 문자길이 - n 번째 문자를 비교하는 방식으로 검증한다. [ 접근방식 ] 값의 범위가 1~1000이므로 31의 제곱수 까지 확인하면 모두 체크가 가능하다고 생각하여 테스트 케이스 마.. 2020. 12. 3. 이전 1 다음 728x90
