모든 경험을 소중하게

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14002번 문제 '가장 긴 증가하는 부분 수열 4' 이다. 이 문제는 LIS 로 알려진 유명한 문제이다. 이 문제를 풀기 위해 이용한 알고리즘은 DP 이다. 물론, 2중 for 문을 이용해서 전체를 계속 순회해도 문제를 풀 수 있다. 특히 이 문제에서는 크기가 1000 이므로, O(n^2) 이다. 따라서 충분히 시간 내에 풀 수 있다. 하지만 DP 를 이용한다면, O(n) 으로 계산 할 수 있다. DP 문제는 다들 많이 풀어보는 유형이라 방법은 알고 있겠지만, 모르는 분들에게 도움이 되고자 설명한다. dp 배열을 수열 길이만큼 잡은 후, 0 으로 초기화 해준다. 여기서 C 언어를 사용하고 있다면, 전역변수로 선언하면 0..

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14502번 문제 연구소 이다. 우선 시간 제한이 2초이므로, 그렇게 빡빡하지는 않다고 생각할 수 있었다. 문제를 마저 더 읽어보자. 새로 세울 수 있는 벽은 꼭 3개이다. 벽이 세워질 수 있는 곳은 0 값을 가지고 있는 좌표들뿐이다. 그렇다면, 어떻게 3개를 선택해야 가장 많은 0 을 남길 수 있을까? 문제를 마저 더 읽어보자. 우선, 벽을 세운 후, 2인 점들을 queue 에 넣은 후, BFS 를 돌아야 안전 영역 ( 0 ) 의 크기가 몇일지 알 수 있는 것 같다. 따라서, 모든 벽 3개를 다 세워봐야만 안전 영역의 크기를 알 수 있다고 판단이 든다. 그렇다면, 0 을 가진 좌표 중 3개를 선택해야 하므로, 0의 갯수..

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 13335번 문제 트럭을 풀어볼 예정이다. 밑에 글을 읽기에 앞서, 문제를 풀 때, 트럭 대신 버스라는 변수를 사용했다. 밑의 설명 또한 그렇게 진행하고자 한다. 오해 없길 바랍니다. 문제 레벨과 대충 훑어본 느낌으로는 매우 쉬운 문제였다. 문제를 보자마자 생각난 방법은 하나 있다. 1. 버스 라는 구조체를 만든다. 2. 그 구조체에서 다리를 구간별로 나눠서, 현재 버스가 다리 위에 어느 위치인지 기억하는 변수를 저장한다. 하지만, 이렇게 한다면, 매 초마다 각 버스의 위치를 1씩 증가 시켜줘야 한다. 즉, 시간 복잡도 면에서 n^2 이므로, 비효율적이다. 다른 방법을 생각해야만 했다. 우선, 아래의 입력과 출력 예제를 ..

오늘 풀어본 문제는 Beakjoon online judge 사이트에 있는 16918번 문제 봄버맨을 풀어보았다. 일단 손으로 직접 테스트 케이스를 가지고 진행해보았다. 주어진 테스트 케이스는 다음과 같다. 6 7 3 . . . . . . . . . . O . . . . . . . O . . . . . . . . . O O . . . . . O O . . . . . 앞으로는 ' . ' 을 쓰면 보기 어려워서 'X' 를 쓰도록 하겠다. time(N) 1 2 3 4 5 map[][] XXXXXXX XXXOXXX XXXXOXX XXXXXXX OOXXXXX OOXXXXX OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOXOOO OOXXXOO OOOXXXO XXOOXOO ..