Computer Science/Algorithm

(C++) 백준 1012번 [유기농 배추]

바로 지난번에 풀었던 문제가 DFS와 BFS 문제였는데, 이번에 바로 BFS개념을 활용할 수 있는 문제를 골라보았다. 1. 문제 해결방법 구상 위의 문제 설명을 풀어보면, 결국은 1로 이루어진 덩어리의 개수가 몇 개인지 파악하는 문제이다. 덩어리에는 배추가 하나가 있을 수도, 두 개, 혹은 여러 개가 있을 수도 있다. 덩어리를 파악하기 위해서는 BFS를 사용하는 것이 가장 효율적이므로 BFS를 선택했다. 배추밭의 첫 모퉁이부터 끝 모퉁이까지 훑어가면서 BFS를 시행할 수 있는 조건이면 BFS를 시행하고 아닌 경우 넘어간다. BFS를 시행할 수 있는 조건이라면 (1) 해당 배추밭 영역을 방문하지도 않았어야 하고 (2) 해당 영역에 배추가 있어야 한다. (배추가 없으면 덩어리를 파악할 이유도 없으므로) 2...

(C++) 백준 1260번 [DFS와 BFS]

오랜만에 그래프 문제를 풀었다. 그래서 그런지 조금 낯설었지만 기본적인 문제라 나름 괜찮았다. 아주 전형적이고 기본적인 DFS, BFS문제라 가볍게 풀어보기 좋은 것 같다. 1. 문제 해결방법 구상 - DFS는 스택을 이용, BFS는 큐를 이용. (DFS에서 굳이 스택을 이용하지 않고 재귀를 이용해도 됨, 근데 한번 스택으로 구현해보았다.) - DFS와 BFS의 관건은 언제 노드 방문 처리를 하고, 컨테이너에서 노드를 pop하는 지를 잘 고민해야함. - DFS에서 스택을 이용해서 구현을 한다면, 더 이상 깊은 depth로 갈 수 없을 때( 더이상 edge가 없는 node에 이르렀을 때)를 어떻게 처리해주느냐가 중요. - 뿐만 아니라 부모 노드로 다시 돌아갔을 때, 갈 수 있는 또 다른 node가 있는 지..

(C++) 백준 3613번 [Java vs C++]

오랜만에 알고리즘 포스팅이다. 생각보다 여러 케이스들을 생각하면서 일일이 반례를 찾아주어야 하는 문제라 꽤나 까다로웠던 것 같다. 1. 문제 해결 방법 구상 1. 일단 어떻게 입력이 들어올지 모른다. Java 형식으로 들어올 수도, C++ 형식으로 들어올 수도, 이도저도 아닌 형식으로 들어올 수도 있다. 2. 이도저도 아닌 케이스를 찾아내는 것이 관건이다. - 일일이 다 찾아서 if문으로 걸러내야한다. (1) 첫번째 글자가 _나 대문자로 시작하는 경우 (ex. _asd, Asd) (2) 마지막 글자가 _로 끝나는 경우 (ex. asd_) (3) C++의 경우 _바로 뒤에 대문자가 오는 경우 (ex. asd_Asd) (4) (3)의 경우랑 비슷하긴 하나 _바로 뒤가 아니라 중간 글자가 대문자인 경우 (ex..

(C++) 백준 1915번 [가장 큰 정사각형]

백준 1915번 문제 [가장 큰 정사각형] 알고리즘 포스팅을 시작해보겠습니다. 다이나믹 프로그래밍 문제인데, 처음에 다른 방식으로 풀었다가 시간초과가 나서 그제서야 DP로 방향을 잡고 풀었으나, 추상화와 해결방법을 쉽게 찾지 못하다가 겨우 푼 문제입니다. 1. 문제 해결 방법 구상하기 - 입력값부터 받는 데 문제가 생깁니다. 그냥 cin 으로 해서 int값으로 입력받을 수는 없습니다. - 그렇다면 scanf를 이용하여 %1d 로 받을 수도 있고, 문자열 형태로 입력을 받은 후, -'0'을 해주어 int 값으로 다시 변환해줄 수도 있습니다. - 입력받은 후에 문제 해결은 어떻게 해야 할까요? - 다이내믹 프로그래밍이란 추상화, 즉 점화식이 굉장히 중요합니다. 위의 그림에서 가장 중앙에 있는 정사각형을 기준..

(C++) 백준 2468번 [안전 영역]

안녕하세요 평범한 컴공생입니다! 백준 2468번 문제 [안전 영역] 알고리즘 포스팅을 시작해보겠습니다. BFS 문제라서 풀어보려 했던 것이었는데 DFS로 해결을 했습니다. 아직 자료구조들의 명확한 차이와 정확한 이해는 쉽지 않은 것 같습니다. 1. 문제 해결 방법 구상하기 - 비의 높이는 아예 비가 안오는 경우부터 비로 인해 모든 영역이 다 잠기는 경우까지 사이에 있는 값들이 될 수 있습니다. - 그 경우들을 하나 하나 해보면서 가장 안전한 영역이 많을 때를 갱신해줍니다. - height 이차원 배열의 어느 한 지점으로부터 동서남북 네 가지 방향 중 하나를 탐색해주기 위하여 dr, dc의 배열을 선언해줍니다. - 그 다음 탐색 지점이 필드 안의 값이 아니라면(0보다 작거나 N-1 보다 크면) 다음 명령문..

(C++) 백준 1149번 [RGB거리]

안녕하세요 평범한 컴공생입니다! 백준 1149번 문제 [RGB거리] 알고리즘 포스팅을 시작해보겠습니다. 전형적인 DP 문제인데, 처음에 DFS로 접근을 하려했다가 시간초과가 나서 DP로 방법을 바꾸니 해결할 수 있었습니다. 1. 문제 해결 방법 구상하기 - 빨간색으로 집을 칠하면 그 다음집은 파란색 또는 초록색으로밖에 칠할 수 없다. - 초록, 파랑의 경우도 마찬가지이다. - 두 번째 집에서 예를 들어 RED로 칠한다고 하면 첫 번째 집에서의 GREEN, BLUE를 선택한 값 중 더 작은 값에 RED를 칠했을 때의 값을 더한 것이다. - 세 번째 집에서 예를 들어 RED로 칠한다고 하면 두 번째 집을 BLUE로 했을 때 소요되는 최솟값과 GREEN로 했을 때의 최솟값 중에 더 작은 값에 RED로 칠했을 ..