SW Expert Academy

등산로를 만드는 규칙에 따라 만들 수 있는 가장 긴 등산로를 찾는 문제이다. 등산로를 만드는 규칙① 등산로는 가장 높은 봉우리에서 시작해야 한다.② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다. 즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다. ③ 긴 등산로를 ...

김프로가 1년 동안 각 달의 이용 계획을 수립하고,가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾는 문제이다.(1일 이용권/1달 이용권/3달 이용권/1년 이용권이 있다.) DFS를 통해 이용권을 쓰는 모든 경우에 대해 탐색하고, 각 경우마다 이용권 가격의 합을 계산하면 된다. 테스트 케이스 49/50 에서 잠깐 헤맸는데, 3달 이용권보다 1달 이용권...

보자마자 BFS 느낌이 나서 바로 탐색을 했는데, 터널 구조물에 따라 통과가 안되는 경우가 발생했다. 이걸 효율적으로 처리해주는 방법이 생각이 안나서 if문을 남발했는데 일단 pass는 받아냈다. 근데 더 효율적인 방법이 있을 것으로 보인다. +) 다른 블로그를 참고하니, DFS로 푸는게 더 깔끔하게 보이는 듯 하다.

나중에 다시 푼다!

DFS와 시뮬레이션을 활용하는 문제이다. 보자마자 어떻게 풀 지 생각이 나서 쉽게 풀 줄 알았는데생각보다 너ㅓㅓ무나도 오래 걸렸다. DFS로 계단을 고르는 모든 경우의 수를 골라주고, 각 경우마다 모두 식당으로 내려오는 시간을 계산했다.

개인적으로 극한의 시뮬레이션 경험이었다. 사실 주어진 조건대로 차근차근 따라가다보면 풀 수 있는 문제이기도 하지만, 구현력이 부족한 내가 풀기엔 조금 부족했다. 다른 분의 블로그를 참고해서 해결했더니 찜찜하다. 나중에 다시 풀어야지.

DFS를 활용하여 약품을 넣는 모든 경우에 대해 탐색하고,백트래킹으로 계산하는 값이 현재의 최솟값을 넘을 경우 가지치기를 했다. 성능검사를 하는 부분을 비효율적으로 짜니까 자꾸 시간초과가 떠서 결국 다른 블로그를 참고했다.

가장 많이 선택된 집이 집의 갯수 이상은 안됨!이거는 당연한 사실. 이거랑은 상관 X. 그렇다면 K의 값은, N이 10이라면 0,0 기준으로 10까지 가능?? 모르겠는데?? 이것이 나의 처음 생각이었다. K값의 범위를 정하는 것이 이해하기 어려었다. 조금 찾아보니 K값이 커짐에 따라 N*N 배열을 모두 선택할 수 있기만 하면 되고, 그러한 K값이 N+1이다...

재귀를 사용한 백트래킹을 활용하는 문제

두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대, 그 때의 최대 수익을 출력하라.재귀를 이용한 백트래킹 문제, 다른 방법으로 벌꿀의 최댓값을 모두 구하는 메모제이션을 활용할 수 있다. A를 먼저 고르고, 다음은 B를 고른다백트래킹으로도 가능하고, 메모제이션을 활용할 수 있다.

코드만 저장.

토요일 A형 시험을 앞두고 패기롭게 후딱 풀려고 시도한 문제이다.(실패) 간단해보였는데 머릿 속 생각이 정리가 안되니까 끝도 없이 꼬인다. 사고의 과정1. 두 음식간의 맛의 차이가 최소가 되는 경우의최솟값을 출력하라 -> 완탐사용(DFS)2. A, B가 N을 나눠가지는 경우의 수는 nC(n/2)3. A, B의 맛을 계산하여 맛 차이의 최솟값 갱신 생각...