WOONY's 인사이트

드디어 4주 간의 알고리즘 커리큘럼이 끝나는 날. 시원섭섭하다. 드디어 끝나서 후련한 마음 반, 지금부터 본격적으로 빡센 일정인 C언어 기반 커리큘럼이 다가왔다는 사실에 두려움 반. 하지만 그 알고리즘마저 해낸 마당에, 앞으로도 지금처럼 꾸역꾸역 하면 어떻게든 하겠지. 알고리즘 커리는 오늘로 끝이지만 앞으로 매일 한 문제씩 꼬박꼬박 풀 예정. 꾸준히 리뷰해야겠다. 이제 알고리즘 풀이 리뷰는 따로 카테고리를 만들어서 올릴 예정. 1. 계단 오르기(#2579) 마침 어제 풀었던 문제가 시험에 나와서 아주 기분 좋게 풀었더랬다. dp를 처음 계단을 오를 때 기점으로 생각하는 게 아니라 n번째 계단에 도착했을 때를 기점으로 거꾸로 생각하면 훨씬 간단하게 풀 수 있다. 아래 그림을 보자. n번째 계단에 도착하는 ..

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..

문제 링크 링크 풀이 이제 어느 정도 bfs를 풀다보니 이런 구현 기반 bfs 문제에 대한 감이 잡힌다. 지도 위에서 인접한 곳에 뭔가를 찾는다거나 바꾼다거나 할 때 흐름을 보면 1. dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]과 같이 x, y를 기준으로 위/아래/양옆으로 갈 수 있는 방향을 설정한다. 2. 문제에서 주어지는 지도를 MAP이라 하고 해당 위치를 방문했는지 체크하는 지도를 visited로 새로 생성한다. (아직 어디도 방문하지 않았으니 전부 방문 X로 체크. False로 만들어도 되고 0으로 만들어도 되는데 지금 문제와 같이 각 구역마다 새로운 번호를 매길 때는 0으로 만들어놓고 서로 다른 구역에 대해 다른 번호를 매기는 식으로 해도 괜찮을듯.) 3. 이중 for문을..

오늘 2주차 시험에서는 1시간 반 동안 겨우 1문제 풀었다. 공부할 때도 엄청 빡셌지만 어찌어찌 익혔다는 느낌이 없잖았는데 결과가 이러니 참담하다 싶지만..! 그래도 한 문제 푼 게 어딘가! 아자자! 잘했다! 한 걸음씩 가는 거지! 1. MOO 게임(#5904) 문제 링크는 여기. 도저히 어떻게 접근해야 좋을지 몰라, 맨 처음에는 아예 수열 자체를 구해버리려고 했다. 10^9를 넘는 가장 작은 수열을 뽑으려고 해봤는데 대략 n이 10~20 사이에서 될 것 같더라! 문제는 n=12를 넣을 때부터 연산이 뻗는다는 느낌이 들기 시작하더니 n=15쯤 가니 허송세월하고 있더라. 이렇게는 도저히 못 풀겠다 확신만 하고 끝남..^_^ 지훈이의 풀이를 공부한 내용을 정리하자면, 이 문제는 재귀로 이루어진 점화식을 길이..

1. 이진 탐색(Binary Search) 보통 우리가 탐색을 시도할 때는 순차적으로 탐색하는 방법을 이용한다. 기존의 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 데이터를 확인하는 방법이다. 리스트에서 특정 데이터를 찾기 위해 검사할 때, 별 다른 조건이 없으면 순차적으로 탐색을 시도한다. 이와 달리 이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 여기서 전제는 탐색하려는 리스트가 정렬되어 있어야 한다는 점이다! 이진 탐색을 하기 위해서는 탐색 범위를 설정해줘야 하는데, 총 세 가지 포인트가 있다. 시작점 (start) 끝점 (end) 중간점 (mid = (start+end)//2) 이 셋을 이용해 탐색한다. 순서는 아래와 같..

오늘은 1주차 알고리즘 시험날. 문제는 #1924, #2503, #6603이 나왔고 1시간 반 동안 푼 문제는 #1924와 #6603으로 3문제 중 2문제. 오늘 시험 목표가 2문제 이상 맞추기였으니 선방은 했는데, 생각보다 1924와 6603을 쉽게 풀어 2503까지 풀지 못한 건 좀 아쉽긴 하다. 시험이 끝나고 바로 2주차 문제가 주어졌으나, 오늘은 푼 문제를 리뷰하면서 시간을 보냈다. 오후에는 #2503을 푸는데 시간을 썼다. 어렵다고 생각했지만 조금 해보니 어느 정도 감이 잡히더라. 스트라이크와 볼을 if문 두 번으로 처리하는 개념만 잘 생각하면 괜찮다. 오히려 쉽게 풀었던 #6603에서 시간을 많이 썼는데, 재귀를 이용한 다른 풀이를 익히느라 고생했다. 시험에서는 조합을 이용해 쉽게 풀었으나 원..