본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/Greedy14

[그리디, 난이도 중하] 프로그래머즈, 체육복 체육복 여벌이 있는 학생들이 옆에 있는 학생에게 체육복을 빌려주었다고 했을 때 체육복을 가지고 있는 최대 학생 수를 구하면 되는 문제이다. 나의 풀이는 이렇다. boolean 배열 2개를 생성하고 다음 조건에 맞게 true/false를 부여해야 한다. phy[ ] : 체육복을 1벌 이상 가지고 있는지 여부를 판단 phy_reserve[ ] : 체육복을 2벌 가지고 있는지 여부를 판단 (여벌) 초기 bool phy[ ]는 true로 초기화 해두었다. reserve벡터를 참조하여, 체육복을 2벌 가지고 있는 학생은 phy_reserve 배열값을 true로 만든다. 그리고 lost벡터를 참조하여 2가지 경우에 대해 처리해준다. 여벌을 가지던 학생이 도난 당하면 1벌 남으므로 phy_reserve 배열 값을 f.. 2020. 9. 12.
[그리디, 난이도 중] 프로그래머즈, 단속카메라 이 문제 같은 경우에는 차량들의 진출 지점을 기준으로 오름차순으로 정렬해야 한다. 그리고 최근에 설치한 카메라의 지점을 기록하는 변수(recent_camera) 가 필요하다. 입출력 예 정렬 전 정렬 후 첫 차량(정렬 후)의 진출 지점에 카메라를 설치한다. (recent_camera=-13, answer=1) 두 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-13) 세 번째 차량의 진입 지점은 recent_camera의 이후이므로 진출 지점에 카메라를 설치한다. (recent_camera=-3) 네 번째 차량의 진입 지점은 recent_camera의 이전이므로 카메라를 설치할 필요가 없다. (recent_camera=-3) 이렇게.. 2020. 9. 10.
[그리디, 난이도 중하] 백준 2217번 루프 n개의 연결된 루프에 매댈 수 있는 최대 무게를 구할 수 있어야 한다. 이 문제의 예제는 부실하므로 버틸 수 있는 최대 중량이 각각 7, 15, 30, 11, 5인 루프 5개를 준비하였다. 일단 이 루프를 내림차순으로 정렬했다. 30, 15, 11, 5, 7 먼저 최대 중량이 30인 밧줄은 당연히 중량이 30인 물체까지 버틸 수 있다. 그렇다면 1,2번째로 최대 중량이 높은 밧줄인 30, 15를 묶으면 어디까지 버틸 수 있을까? k개의 루프가 묶인다면 중량은 k분의 1로 나뉘게 된다고 했다. 2번째로 최대 중량이 높은 15에 2를 곱한 30이 최대가 된다. 중량이 30인 물체는 저 밧줄들에 각각 15, 15씩 분배가 되므로 30이 최대가 된다는 것을 검산했다. 그렇다면 1,2,3번째로 최대 중량이 높은 .. 2020. 8. 22.
[그리디, 난이도 중] 백준 1543번 문서 검색 문자열 매칭 알고리즘들중 라빈카프를 이용했다. 라빈카프 알고리즘은 문자열의 특정 해쉬값을 계산한 후 두 해쉬값이 일치할 경우, 문자열 매칭에 성공했다고 판단하는 알고리즘이다. 여기서 2차적으로 동일한 해쉬값을 가진 문자열에 대해서 확인차로 한번더 문자열 그 자체를 검사할 수도있다. 문자열의 해쉬값을 정하는 방법은 많지만 이 소스코드에서 해쉬값은 이렇게 정했다. 문자열 a의 size를 size라고 가정하면 문자열의 해쉬값 = a[0]*2^(size-1) + a[1]*2^(size-2) +a[2]*2^(size-3) + ... a[size-1]*2^0 https://www.youtube.com/watch?v=kJJQJDsjXc8 문자열 매칭 알고리즘은 동빈나 님의 강의로 배웠는데 여기서 동빈나님이 이용하신 .. 2020. 8. 17.
[그리디, 난이도 중] 백준 1931번 회의실배정 첫 그리디 문제풀이 포스팅이다. 다이나믹(동적계획법) 알고리즘과 그리디(탐욕) 알고리즘의 차이는 이 포스팅에서 다루었다. https://kimcoder.tistory.com/32 [동적계획법, 난이도 중] 백준 1463번 1로 만들기 첫 번째 동적계획법 문제풀이 포스팅이니, 동적계획법이 뭐하는 알고리즘인지 설명이 필요할 것이다. 동적계획법은 간단하게 말하면 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활 kimcoder.tistory.com 여러 회의들의 시작 시간, 끝 시간을 알아내어 최대한 많은 회의를 하는 경우를 계산해야 하는 문제이다. 회의가 끝나는 시각이 이른 순으로 정렬하고, 끝나는 시각이 같다면 시작 시각이 늦은 순으로 추가 정렬을 해준다. 이 문제의 정답률이 28%인 이유는 아마.. 2020. 8. 14.

티스토리툴바