전체 글

(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로 칠했을 ..

(C++) 참조 변수

참조 변수 포인터를 선언할 때 * 기호를 이용하는 것은 낯설지가 않다. 참조 변수를 선언할 때는 &기호를 이용하여 선언을 해준다. #include int main() { using namespace std; int value = 3; int *ptr = &value; int &ref = value; cout

(C++) 백준 14500번 [테트로미노]

안녕하세요 평범한 컴공생입니다. 백준 14500번 [테트로미노] 문제 알고리즘 포스팅을 해보겠습니다.쉽지 않은 문제였지만 그렇다고 도전하기도 전에 겁을 먹을 문제는 아니었습니다. SW역량테스트 문제입니다. 도전해 볼 가치가 있습니다. 1. 문제 해결 방법 구상하기 - 4개의 블럭으로 이어진 조각이다? --> 하나의 시작블럭을 잡고 4개의 블럭을 탐색해가면서 더해주자! - 이전에 탐색을 하였던 블록이거나, 주어진 격자의 범위를 넘어서는 경우처럼 여러 조건을 걸어주어야 한다. - 이 방법대로 한다면 ㅗ 모양과 같은 경우에는 예외의 경우이므로 따로 함수를 만들어 예외처리를 해주어야한다. 케이스 1~4경우로 만들어 ㅜ, ㅓ, ㅏ, ㅗ 의 CASE를 다 탐색해준다. - DFS 형식으로 깊이(CNT) 값을 주어 탐..

(C++) 백준 10971번 [외판원 순회2]

안녕하세요 평범한 컴공생입니다. 오늘은 유명한 문제중 하나인 TSP(Traveling Salesman Problem) 알고리즘 포스팅을 해보겠습니다.DFS(Depth First Search)의 대표적인 유형 중 하나인데 저는 c++ 의 STL을 사용하여 문제를 해결하였습니다. 1. 문제 해결 방법 구상하기 - 들렸던 도시를 다시 방문할 수는 없다. - 하지만 모든 도시를 방문해야 한다. - 순서가 정해져있다. - 그렇다면 순열과 같다. - STL 에서 순열함수를 이용하면 된다. - 여러 조건을 추가해주어서 조건에 맞는 경우만 최솟값과 비교해준다. 2. 구상한 아이디어를 바탕으로 코딩하기 #include #include #define MAX 10 using namespace std; int W[MAX][M..

(C++) 백준 11729번 [하노이 탑 이동 순서]

안녕하세요 평범한 컴공생입니다. 백준 11729번 [하노이 탑 이동 순서] 문제 알고리즘 포스팅을 해보겠습니다. 사실 학교에서 전공 공부를 하면서 하노이 탑 이동 순서와 관련한 문제를 접한 적이 있었는데 그때는 그냥 혼자 해결하기 위해 고민하는 시간 없이 구글링으로 과제를 했던 기억이 나 이번엔 반드시 내 힘으로 풀겠다!는 마음가짐으로 문제를 풀었습니다..! 전형적인 재귀함수입니다. 재귀함수를 사용하려면 어떠한 함수가 다음 항의 함수값에 영향을 주는 규칙적인 형태를 띌 때 사용하기에 적절합니다. 하노이 탑이 그러합니다. 1. 문제 해결 방법 구상하기 - 하노이 탑이 1층이면 그냥 그거 하나만 3번 기둥으로 옮기면 된다. >> 2층이면? 위의 원판을 2번째로 옮기고, 밑의 원판을 3번 기둥으로 옮긴 후 2..