전체 글 (125) 썸네일형 리스트형 9935 문자열 폭발 단순하게 생각해보면 문자열을 비교하는 함수를 사용하여 쉽게 풀 수 있을 것 같지만, 함정이 숨어있다. 입력 문자열 길이가 1,000,000이다. 즉, 비교 함수로 하나씩 비교하면, 시간초과가 난다.. 때문에 다른 방법으로 접근해야 한다. 코드를 참고해보니 핵심은 폭발 문자열의 마지막 문자와 입력 문자열의 마지막 문자를 비교하고 일치한다면, 나머지까지 비교하는 것이다. 결과 문자열에 입력 문자열을 하나씩 저장해가면서 다음과 같은 룰을 따른다. 폭발 문자열의 마지막 문자를 입력 문자열과 비교한다. 같다면 폭발 문자열의 나머지 문자와 비교한다. 다르면 결과 문자열에 그대로 저장한다. 1번에서 폭발 문자열의 나머지 문자들과 모두 일치한다면, 폭발 문자열의 길이만큼 결과 문자열의 인덱스에서 뺀다. 다른 사람의 코.. 14503 로봇청소기 단순한 구현문제이지만 구현 시간에 집중해야 하면 좋은 문제이다. 내가 생각한 구현 방법은 다음과 같다. 로봇청소기의 방향과 위치 로봇 청소기의 위치와 방향을 구조체로 묶어 한 번에 관리하여 편리하게끔 하였다. 로봇 청소기의 동작 순서 문제에 나와있는 로봇청소기의 동작 순서만 보면 A, B, C, D 순서대로 구현해야할 것 같지만, 사실 종료 조건이 포함되어 있기 때문에 유의하여 구현해야 한다. A조건 : 위치와 방향을 수정하며, 맨 마지막 순위로 둔다. B조건 : 위치만 수정하며, A조건 보다 먼저 확인한다. C조건 : 위치만 수정하며, B조건 보다 먼저 확인한다. D조건 : 이 조건을 만족할 때까지 반복문을 수행하며, 가장 먼저 확인한다. 정답코드 더보기 #include using namespace s.. 1202 보석 도둑 greedy 방식으로 접근하려 했으나, 부분 최적해를 구하는 방식이 특이한 문제이다. 내가 시도했던 접근은 bottom-up 방식이 greedy 였으며, 메모리 제한때문에 테이블 구성에 제약이 생기는 것과 local optimal을 구하는 과정이 매끄럽지 못했다. 그래서 찾아본 방법으로 js1jj2sk3.tistory.com/14를 참고했는데, 방법은 다음과 같다. Greedy 방식의 정당성 증명 : 무게 제한 순으로 A1, A2, ...의 가방들은 A1이 담을 수 있는 보석은 A2도 담을 수 있으므로, 배낭의 수용량이 높을수록 더 비싼 보석을 넣는게 최적해이다. 구현 방법은 우선순위 큐가 핵심인데, 배낭의 무게와 보석의 가치를 정렬하고 i번째 배낭이 담을 수 있는 보석들의 가치 중에서 최대 가치를 뽑아.. 이전 1 ··· 29 30 31 32 33 34 35 ··· 42 다음