코딩테스트 썸네일형 리스트형 [백준(Baekjoon) 13904번](Python) 과제 주어진 과제들의 남은 일 수가 가장 큰 것부터 하나씩 줄여가면서 해당 일수 이상 남은 과제들 중 max값을 지운다. 하루에 과제는 1개씩만 할 수 있으므로 하나씩 줄여가면(리스트에서 빼주면) 리스트에 남은 과제들을 제외한 모든 과제를 수행할떄, 최댓값을 가지게 된다. 처음에는 이문제를 기한이 적게 남은 순으로 정렬해서, 가장 기한이 적게 남은 문제와 다른 문제들을 비교하며 하나씩 리스트에서 제거해주려고 했는데 신경쓸 변수도 많아지고 비효율적으로 문제들을 찾아서 삭제해야 되기 때문에, 역으로 풀었다.(어차피 하루에 하나씩 해결할 수 있으므로, 정확하게 남은 기한을 줄여가며 문제를 해결할 필요가 없다.) 더보기 [백준(Baekjoon) 1520번](Python) 내리막길 경로를 찾기위하여 dfs를 수행하되, 좌표마다 해당 좌표에서 도착지점까지 갈수 있는 경로수를 갱신하면서(dp) 비용을 줄인다. 재귀문이 끝나면 dfs를 호출한 지점에서의 dp값은 도착지점까지 갈 수 있는 모든 경로의 수가 된다. 처음에 bfs와 dfs로 풀었을때 시간초과가 나서 구글링을 해본 결과 dynamic programming을 섞어서 풀어야 한다는 사실을 배웠다. 생각하기 어려웠던 문제다. 추가적으로 파이썬에는 시스템의 안전성을 위해서 재귀깊이가 기본값으로 설정이 되어있는데, 이를 더 늘려야 한다는 사실을 깨달았다. 더보기 [백준(Baekjoon) 1449번](Python) 수리공 항승 테이프의 현재 위치와 이전 위치의 차이를 뺀 수들을 합해가며 테이프 길이 내에 있는 지 확인하고, 만약 테이프가 모자라는 위치에서 물이 새면 테이프 갯수를 늘려준다. 수리된 위치는 리스트에서 빼주면서 해당 리스트의 길이가 0보다 클때 까지 계속 반복하면 정답이 나오게 된다. 입력이 여유롭게 주어져서 굳이 깔끔하고 효율적인 알고리즘을 생각해보지 않고 풀었다. 나중에 구글링 해보니까 물이세는 시작 위치를 기준으로 테이프를 붙여놓고 테이프 범위내에 몇군데나 물이세는 곳이 있는지를 세어보는 간단한 방법도 있었다. 더보기 [백준(Baekjoon) 9663번](Python) N-Queen 레벨(깊이)을 하나씩 늘려나가면서 재귀적으로 가능한 배치에 대해서 탐색한다. 즉, 어떤 레벨에서 퀸의 위치를 x라고 하면, 해당 레벨 전까지 퀸의 위치가 x인 점이있는지 체크하고, 해당 레벨 전까지 퀸의 위치가 해당 레벨의 퀸의위치의 대각선 상에 위치 한 점이 있는지를 체크해서 이 두가지 모드 아닐 경우에만 해당 레벨에서 퀸의 위치는 x가 되므로 그 위치 x와 그앞전의 지점들의 좌표를 유지한 채로 반복문을 돈다. 즉 ans가 +되는 경우는 모든 말들이 서로서로 영향을 받지 못하는 위치에 있다는 말이 된다. 재귀를 이용한 dfs와 backtracking에 대하여 더 공부할 수 있는 좋은 문제였다. 더보기 [백준(Baekjoon) 1987번](Python) 알파벳 큐를 set으로 놓고 큐에는 x,y좌표와 지나온 칸의 문자열을 append하면서 bfs로 현재 좌표에서 갈수 있는 네 방향을 탐색한다. 좌표가 주어진 범위안에 있고, 좌표가 이미 지나온 칸들의 문자를 합친 문자열안에 포함되어있지 않으면 큐에 append해주며, max값을 문자열의길이와 이전 max값 중 큰 값으로 초기화시켜준다. 결국 max안에는 갈수있는 최대칸 수 가 담기게 된다. bfs에 대하여 공부할 수 있는 문제였다. 더보기 [백준(Baekjoon) 1261번](Python) 알고스팟 현재 좌표로부터 갈수있는방향의 좌표를 탐색하며 해당 좌표의 check를 확인하는데, 방문하지 않은 좌표(check의 값이 -1이 아닐 경우) 이며 동시에 해당 좌표의 값이 주어진 N,M범위에 있는지 체크하고 빈 방일 경우 appendleft를 통해서 큐의 앞쪽에 append해주면서, 빈방을 최대한 먼저 확인 해주고 더이상 빈방이 없을경우 벽을 한칸 뚫어주고, 또 그다음 빈방을 최대한 갈수있는 곳까지 확인 해주는 식으로 최소한의 벽을 깨고 목적지까지 도달한다. check리스트의 마지막 원소 값이 정답이 된다. 최적의 경로탐색을 가능하게해주는 다익스트라 알고리즘에 대하여 공부할 수 있었다(check리스트를 최선의 값으로 바꾸면서 진행) 더보기 [백준(Baekjoon) 1874번](Python) 스택 수열 숫자를 입력받을때, 원래 있던 오름차순의 1~N까지 숫자를 담은 배열에서 그 숫자 보다 작은 숫자는 push(+) 해주면서 cnt값을 증가시켜주고(리스트의 원소를 직접 옮겨도 되지만 시간초과가 난다.), 해당 숫자까지 cnt가 올라가면 stack의 마지막원소와 같은지를 확인하고 같으면 꺼내즈고 pop(-) 해주는 작업을 계속해서 반복해주면 정답이 나오게 된다. 처음에는 1~N까지 1씩 커지는 숫자를 담은 배열 이라는 조건을 무시하고 그냥 숫자 하나가 나올때 마다, 푸쉬,팝 연산을 직접 수행하였다. 그러니까 상당히 많은 시간이 소요되었다. 리스트 원소를 옮겨 주지 않고, 단순히 변수에 값을 하나씩 늘려가며 해당 숫자가 될 때까지 푸쉬 해주고 밑에 조건문을 둬서 해당 숫자가 스택에서 맨 마지막에 나오는 숫자.. 더보기 [백준(Baekjoon) 2805번](Python) 나무 자르기 이분법을 이용하여 첫,끝 점을 잡고 중간값을 기준으로 나무들을 잘랐을때 잘라진 나무 길이 값이 주어진 M보다 크면 시작점을 중간값 보다 하나 증가시켜주고 위와 같은 방식으로 반복, 작으면 중간값보다 하나 작은값으로 끝값을 두고반복하다 보면 원하는 값이 나오게 된다. 첫번째로 맨 위의 코드로 풀었는데 길이순으로 나무를 정렬 한 뒤, 나무들의 길이에 따라 잘라 사잇값에서 찾게끔 하였다(ex).(두번째나무길이 - 세번째 나무길이)+(첫번째 나무길이- 세번째 길이 나무)한 값이 M보다 크면 두번째 나무 길이와 세번쨰 나무길이 사이에서만 찾으면 되는 알고리즘을 구상하였다. 하지만 나무의 길이은 어떻게 치중되어 있을지 모르는 상황이기 때문에 내가 구상한 알고리즘보다 이분법을 사용하는게 훨씬 좋은 방법인 것 같다. 더보기 이전 1 2 3 4 ··· 7 다음
