반응형 분류 전체보기580 [구간합] 쿠키 구입 - Summer/Winter Coding(~2018) 문제를 해결한 후에도 다른 풀이법에 대한 호기심이 생겨서 찾아보았다. 내 풀이법도 간단하다고 생각하지만 이 블로그에 설명된 풀이법이 더 간단해보이니 궁금한 분들은 참고하길 바란다. https://hwan-shell.tistory.com/308 이제 내 풀이법을 소개한다. 해결 방법 cookie 벡터에 대한 누적합 배열 cookie_acc을 만들어 놓았기 때문에 구간합 공식을 쉽게 구할 수 있었다. 예를 들어, 구간 [a, b]에 대한 구간합은 cookie_acc[b]-cookie_acc[a-1]이다. 이 문제에서는 a 2022. 5. 1. [시뮬레이션] 스킬트리 - Summer/Winter Coding(~2018) 해결 방법 먼저 스킬트리의 순서를 map에 저장해두고, 뒤에 나와야 할 스킬이 앞에 나왔다면 그 스킬트리는 잘못 됐다고 판단하면 된다. 소스 코드 #include #include using namespace std; map m; int solution(string skill, vector skill_trees) { int answer = 0; for(int i=0;i 2022. 4. 29. [그리디] 기지국 설치 - Summer/Winter Coding(~2018) 해결 방법 아파트의 개수 N의 범위는 2억까지이기 때문에 O(N) 이상의 시간복잡도로 풀면 시간초과가 나올 것이다. 그래서 범위가 1만까지인 stations 벡터를 이용해서 해결하였다. 문제의 접근법은 다음과 같다. Step 1) 전파가 닿지 않는 연속된 아파트의 길이들을 벡터에 저장한다. - 예를 들어, 아래 예제의 경우에는 1~2, 6~9 구역에 전파가 닿지 않으므로 2, 4를 벡터에 저장하면 된다. Step 2) 벡터에 저장된 거리들을 하나씩 꺼내어 각 거리마다 설치할 수 있는 최소 기지국의 수를 합산한다. - 거리 n에 설치할 수 있는 최소 기지국의 수의 공식은 ceil((float)n/(2*w+1)) (ceil()은 올림 함수)가 된다. 소스 코드 #include #include using na.. 2022. 4. 26. [그리디] 숫자 게임 - Summer/Winter Coding(~2018) 해결 방법 A, B 벡터를 각각 오름차순으로 정렬해서 낮은 숫자를 가진 사람들부터 출전시켜가며, A팀에서 숫자가 낮은 사람들은 반드시 매칭이 이루어지도록 하는 식으로 접근하면 쉽게 해결할 수 있다. A의 n번째 팀원을 an이라고 하고, B의 n번째 팀원을 bn이라고 하자. A팀과 B팀의 각 첫 번째 사람인 a1, b1부터 출전시켜서 a1의 숫자가 더 크다면, b1는 A팀의 모든 뒷 사람들을 이길 수 없는 상태임을 알 수 있다. 왜냐하면 A를 오름차순으로 정렬해놓았기 때문이다. 그래서 B팀의 다음 사람(b2)을 출전시켜서 a1와 비교하면 된다. 만약에 b1의 숫자가 더 크다면 B팀의 승점을 1만큼 카운트하고 A팀과 B팀의 다음 사람을 출전시키면 된다. 그리고 매칭에 시도한 B의 팀원은 더 이상 매칭할 일이.. 2022. 4. 24. [수학] 멀쩡한 사각형 - Summer/Winter Coding(2019) 해결 방법 일차 함수의 특성을 이용하여 문제를 해결했다. 입출력 예 #1에서 좌측 하단 꼭짓점을 원점이라고 했을 때, 일차 함수식은 다음과 같다. y=-(h/w)x+h x축으로 좌표를 1씩 옮겨가며 선에 걸치는 사각형들을 제거해주는 방법을 사용하면 문제를 해결할 수 있다. 이제, 좌측에 있는 사각형부터 제거해보자. 먼저 x=0일 때 y=12이고, x=1일 때 y=10.5다. 이 경우에는 y의 좌표가 10~12 사이에 있는 사각형 2개가 제거된다. 그 다음에 x=1일 때 y=10.5이고, x=2일 때 y=9다. 이 경우에는 y의 좌표가 9~11 사이에 있는 사각형 2개가 제거된다. 이런식으로 계속 두 좌표를 비교하여 사각형을 제거해나가면 되는데, 이 때 왼쪽 좌표의 y값은 올림을 하고 오른쪽 좌표의 y값은.. 2022. 4. 22. [SQL] 우유와 요거트 - Summer/Winter Coding(2019) 테이블 문제 설명 해설 : 하나의 장바구니에 같은 제품을 담을 수도 있기 때문에 CART_ID, NAME 쌍이 중복인 튜플을 제거한 서브테이블을 생성한다. 이 서브테이블에 대해서 CART_ID별로 NAME이 Milk 또는 Yogurt인 튜플의 개수를 카운트해서, 카운트가 2인 CART_ID를 최종적으로 출력하면 된다. SELECT CART_ID FROM (SELECT DISTINCT CART_ID, NAME FROM CART_PRODUCTS) AS DT WHERE NAME IN ('Milk', 'Yogurt') GROUP BY CART_ID HAVING COUNT(*)=2 ORDER BY CART_ID; 2022. 4. 15. [BFS] 배달 - Summer/Winter Coding(~2018) 제대로 동작하도록 구현하는건 쉽지만 시간 초과에 막힐 수 있는 문제다. 이 문제는 최대한 효율적으로 구현해야 한다. 해결 방법 필자는 BFS로 해결했다. Step1) 이 문제는 인접한 두 노드를 연결하는 간선이 여러개가 있을 수 있다. 그래서 인접한 두 노드를 연결하는 최소 비용의 간선들을 저장해둬야 한다. Step2) 노드와 간선을 연결한다. Step3) BFS를 수행하면서 1번 노드(마을)로부터의 최소 비용(시간)이 갱신된 노드만 Queue에 넣는다. 참고로, 갱신된 노드의 비용이 K를 넘어가는 경우에는 굳이 Queue에 넣지 않도록 처리하면 처리시간을 단축할 수 있다. Step4) 1번 노드로부터의 최소 비용이 K 이하인 노드를 모두 카운트한다. 단, 1번 노드는 당연히 카운트 해야하고, BFS를 .. 2022. 4. 15. [Spring] Static 멤버 클래스를 Bean으로 등록하기 보통 특정 테스트 클래스에서만 사용되는 클래스를 static 멤버 클래스로 만들곤 한다. Static 멤버 클래스를 Bean으로 등록하는 방법은 약간 특이하다. 내부 staitc 클래스를 감싸는 클래스를 외부 클래스라고 한다면, 아래 예시와 같이 $ 기호를 외부 클래스의 뒤에 붙이고 그 뒤에 static 멤버 클래스를 작성하면 된다. 2022. 4. 14. [동적계획법] 스티커 모으기(2) - Summer/Winter Coding(~2018) 서로 인접한 요소를 선택하지 않으면서 합이 최댓값이 되는 요소들을 선택하는 유형의 문제다. 프로그래머즈의 도둑질 문제와 동일한 유형의 문제다. 물론 점화식도 같다. https://kimcoder.tistory.com/92 [동적계획법, 난이도 중상] 프로그래머즈, 도둑질 Programmers의 문제들은 난이도별로 다섯 레벨로 나뉘는데, 그 중 Level 4에 속하는 난이도 있는 문제이다. 그래도 백준에서 DP를 50문제 넘게 푼 짬이 있어서 그런지 크게 어렵지는 않았다. 집이 일렬 kimcoder.tistory.com 차이점이 있다면, 도둑질 문제는 입력 배열의 크기가 3 이상으로 정해져 있고, 이 문제는 입력 배열의 크기가 1, 2일 수도 있다는 것이다. 그래서 sticker.size() 값이 1 또는.. 2022. 4. 12. 이전 1 ··· 16 17 18 19 20 21 22 ··· 65 다음
