Computer Science

(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..

(C++) 백준 15686번 [치킨 배달]

안녕하세요 평범한 컴공생입니다. 오늘은 백준 15686번 [치킨 배달] 문제 알고리즘입니다. 삼성 SW역량테스트 기출문제입니다. 처음 문제를 맞닥뜨리고 집합에서의 조합을 어떻게 컴퓨터 언어로 풀어낼 수 있을까 많이 고민해 보았습니다. 사실 이 문제를 저의 능력으로 푼 것이 아니라 다른 분의 알고리즘을 보고 참고하여 푼 것이라 아직 실력이 정말 많이 ㅈ부족하다는 것을 느낄 수 있었던 문제였습니다. 이 풀이가 아니라 구글링을 통해 보았던 다른 분들의 풀이를 보면 C++의 vector를 많이 활용한 것을 알 수 있었는데 아직 vector 의 개념을 학습하지 않아 vector 개념을 조만간 학습한 후에 다시 이 문제를 접근해 보려고 합니다. 1. 문제 해결 방법 구상하기 - 크기가 N*N인 도시의 정보와 남겨놓..