전체 글

문제 출처 : 코드트리_방화벽 설치하기 티어 : 골드4 유형 : 백트래킹, BFS 출제 : 2017년 상반기 오후 2번 주의사항 : 백트래킹같은 재귀함수 문제는 디버깅이 어려우므로 주의할 것. 첫 번째 문제와 비슷한 난이도로 출제된 두 번째 문제입니다. 첫 문제는 BFS, 두 번째 문제는 BFS가 섞인 재귀 문제를 내니 이때부터 그래프 문제를 본격적으로 내기 시작했다는 것을 알 수 있겠습니다. 현재에도 반드시 한 문제는 포함하고 있으므로, 그래프의 마스터가 되는 것을 목표로 공부해봅시다! 생각의 흐름 놓을 수 있는 벽이 최대 3개이므로, 빈 칸들 중에서 벽을 놓을 곳 3개를 고르는 조합 문제라고 생각을 했습니다. 따라서 벽을 놓을 수 있는 후보들을 wall cand list에 담고, 반복문을 이용하여 w..

문제 출처 : 코드트리_자율주행 자동차 티어 : 골드5 유형 : 시뮬레이션 출제 : 2017년 상반기 오후 1번 주의사항 : 분기를 나누는 기준을 명확히 할 것. 설명이 정말 친절하죠? 혹시 이해를 못할까봐 영상자료까지 준비해주다니요. 실제 시험에서도 그래주면 좋으련만 독해력도 문제의 일부라고 주장을 하니, 백준의 로봇 청소기 문제에 대한 설명을 읽고도 이해할 수 있도록 감을 익히도록 합시다. 생각의 흐름 visited 배열을 따로 관리하기보다는 graph의 값을 도로도 인도도 아닌 값으로 바꿈으로서 구분하자고 계획했습니다. 그래프의 바깥이 모두 인도라고 가정되었으므로 범위를 고려하지 않고, 벽의 여부만 체크해도 되겠다고 생각했습니다. 4방향을 순차적으로 탐색하며, 모든 방향이 특정 조건을 만족했을 때 ..

문제 출처 : 코드트리_외주 수익 최대화하기 티어 : 실버3 유형 : 백트래킹 출제 : 2017년 상반기 오전 2번 주의사항 : 없습니다. 골드가 두 문제 배치된 오후와 다르게 실버문제가 출제되었습니다. 이런걸 보면 운이 참 중요하기도 하다는 것을 느낍니다. 이번 문제도 푸는 방법이 크게 두 가지로 나뉘는데요, 하나는 백트래킹, 나머지 하나는 dp입니다. 후술하겠지만 최대 휴가일이 몇 천일, 몇 만일이 아니라 15일 뿐이므로(ㅠㅠ) 여기서는 백트래킹으로 풀이하겠습니다. 생각의 흐름 문제를 딱 보자마자, 각 날짜별로 최대화된 수익을 기록하는 dp문제구나, 라는 생각이 들었습니다. 하지만 휴가일의 최대가 15일인점으로 미루어보아 백트래킹으로 더 쉽게 구현할 수 있겠다고 생각하여 백트래킹을 이용하기로 했습니다..