SWEA (7) 썸네일형 리스트형 SWEA - 창용 마을의 개수 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 기본적인 유니온 파인드 기본 문제이다. 유니온 파인드는 이름부터 유니온과 파인드 함수로 나뉜다. 유니온은 함께 묶기, 파인드는 부모를 찾는 것이다. 그리고 기본적으로 유니온 파인드는 사이클을 찾기 위해서 사용되기도 하는데, 무방향 그래프는 DFS와 유니온 파인드로. 방향 그래프는 DFS로 알 수 있다. #include #include using namespace std;int people[101];in.. SWEA - 백만 장자 프로젝트 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 그리디 문제로 보인다. N이 백만이지만 제한 시간을 30초나 주기 때문에 엄청나게 빡빡하진 않다고 본다. 먼저 예제에 없는 유형을 보자 1 7 2 10 이 때 최상의 경우는 1 7 2에서 모두 사고 10에서 파는 것이다. 즉, 올라가다가 내려간다고 팔면 최적이라 볼 수 없다. 그래서 계속 이후 앞에 최대값이 얼마나 있을지 생각해야한다. 난 그래서 처음 최대값을 설정하고 최대값을 만났을 때 팔고 이후 반복문을 돌리며 남은 숫자 중 최댓값을 찾는 식으로 작성하.. SWEA - 증가하는 사탕 수열 (C++) 처음엔 이분탐색을 통해 풀이하려 했는데 쉬운 그리디 or 구현 문제이다. 경우를 나누어 볼 수 있다. 1. 처음부터 사탕 주머니가 오름차2. 둘 중 하나라도 3번째 주머니보다 많이 차있음 만약 4 7 4 순서로 되어있다면 -> 2 3 4 순서로 만들어야한다. 즉, 최댓값이 정해져있다. 첫번째 값은 candy[2] - 2두번째 값은 candy[2] - 1 그러므로 만약 지금 사탕의 값이 위 임계값보다 크다면 임계값으로 바꿔주고 먹은 사탕을 샌다.단 1 1 7 의 경우처럼 임계값에 걸리지 않지만 오름차가 아닌 경우가 있으므로 오름차가 맞는지 확인하는 로직까지 추가해주면 쉽게 답을 맞출 수 있다. #include using namespace std;int main(){ int T; cin >> T; .. SWEA - 공평한 분배2 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AY6cg0MKeVkDFAXt&categoryId=AY6cg0MKeVkDFAXt&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 가장 먼저 정렬하고 싶단 생각이 드는 문제이다. 그리고 모든 경우의 수를 구해야하는데 조합으로 구하면 N이 50이기 때문에 불가능하다. 본인은 처음에 이분.. SWEA - 영어 공부(C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 자체는 어렵지 않다. 만약 답을 구할 수 있도록 러프하게 구해보면 1 3 4 5 라고 들어온다고 가정할 때 1에서 시작해서 N 모두 보기 , 2에서 시작해서 모두보기 해서 총 N * N의 시간이 걸리도록 하는 것은 쉽다. 그러나 20만 * 20만 = 4천억으로 어림도없다. 그래서 처음 생각해낸 것은 1 3 4 5에서 1에서 최고수를 구하고 3에서 최고수를 구하는 것을 이분탐색으로 찾아내는.. SWEA - 10806번 수 만들기 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com A수 -> B수 이동 최소거리는 유서깊을 정도로 흔한 레파토리이다. 그래서 처음 생각한 풀이는 다익스트라였다. 왜냐하면 K = 1억이고 방문체크만해준다면 O(N)으로 풀이할 수 있기 때문이다. 그러나 이 방법을 사용하려면 최악의 경우 1억개 모두 dist 배열에 + 한 갯수를 저장해야하는데 이러면 int 배열을 사용하면 4억 바이트 = 4000KB = 약 400MB를 사용해야해서 불가능하다. 그래서.. SWEA - 햄버거 다이어트 (C++) https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N이 20밖에 안되기 때문에 재귀 방식으로 풀어낼 수도 있다. 처음 부터 요소를 살펴보면 두가지 행동이 가능할 것이다. 아직 제한 칼로리를 넘지 않았음을 깔아두고 1. 이번 재료를 소모하고 지나간다. 2. 이번 재료를 쓰지 않고 넘어간다. 그렇다면 함수는 아주 간단하다. void dfs(int idx, int sum_socre, int sum_cal){ answer = max(answer, sum_socre); //cout value >> weight;.. 이전 1 다음
