본문 바로가기

알고리즘/SWEA4

[SWEA 8934] 팰린드롬 공포증 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW5jJcZ68LsDFATQ 문제에 대한 자세한 설명은 링크 참조 1. 앞뒤로 뒤집어도 똑같은 문자열을 팰린드롬이라고 한다. 2. 예를 들어, “o_o”, “404”, “appa” 는 팰린드롬 이지만, “umma”, “koosaga”, “kriii”는 팰린드롬이 아니다. 3. a,b,c로 이루어진 주어진 문자열 내 길이가 2이상인 팰린드롬을 없애고자 한다. 4. 여기서 주어진 문자열내 문자들은 각각 바꿀 수 있으며 해당 주어진 문자열의 서브스트링이 팰린드롬이어도 팰린드롬이다. 5. 문제에서 각 문자열이 주어질 때, 해당 문자열을 수정하여 팰린드롬이 아닌.. 2020. 7. 7.
[SWEA 9088] 다이아몬드 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Oktj6WMQDFAWY 문제에 대한 자세한 설명은 링크 참조 1. 각각 크기가 다른 N개의 다이아몬드가 존재 2. 이 중 몇개를 골라 선물을 하려고 한다. 3. 다이아몬드 묶음은 K개의 크기차이 이하인 것들이어야 함 4. 묶음 중 최대로 줄 수 있는 다이아몬드의 수를 구하라 B. 접근법 정렬 + Sliding Window 먼저 N개의 다이아몬드를 오름차순으로 정렬한다. 그 다음 head와 tail을 옮겨가며 Sliding Window를 이동하여 K개 이하의 차를 가지는 다이아몬드 묶음 윈도우를 만들어 정렬된 배열을 탐사. tail을 뒤로 옮길때마다.. 2020. 6. 2.
[SWEA 9659] 다항식 계산 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXCjsn0KJzcDFAX0 문제에 대한 자세한 설명은 링크 참조 1. 위와 같은 다항식이 존재 2. f0~fN에 대한 정의가 각각 주어지고, 이를 정의하는 ti, ai, bi가 주어질 때 fi(x)를 구할 것 ti =1이면 fi(x) = fai(x) + fbi(x) ti =2이면 fi(x) = ai × fbi(x) ti= 3이면 fi(x)= fai(x) × fbi(x) 3. M개의 수 x1,x2, ⋯, xM이 주어질 때,fN(x1), fN(x2), ⋯, fN(xM)을 계산하라 B. 접근법 다이나믹 프로그래밍 우선 문제에 대한 구현을 시작하기 이전에 해.. 2020. 6. 1.
[SWEA 2383] 점심 식사시간 (C++) A. 문제설명 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. P로 표시된 각 좌표에 사람들이 위치하고, S로 표시된 위치에 계단이 존재 3. 계단에는 한번에 3명의 사람들만 들어갈 수 있고, 계단의 길이는 입력으로 주어지며 그 길이만큼 내려가는 시간이 소요 4. 모든 사람들을 각 계단에 배치하여 내려가게 할 때, 마지막 사람까지 모두 계단을 내려가는 최소의 시간을 구하라 B. 접근법 DFS + 시뮬레이션 우선 계단1/2에 대한 사람들의 선택에 대한 조합을 먼저 DFS로 구한다. 그 후, 각 계단을 선택한 사람.. 2020. 6. 1.

티스토리툴바