Computer Science/Algorithm
(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인 도시의 정보와 남겨놓..
(C++) 백준 2960번 [에라토스테네스의 체]
안녕하세요 평범한 컴공생입니다. 오늘은 백준 2960번 에라토스테네스의 체 문제 알고리즘 포스팅을 해보겠습니다. 1. 문제 해결 방법 구상하기 - N과 K의 값을 먼저 입력받는다. - 2부터 시작해서 3, 4, 5 ... 와 같이 1씩 값을 올려주며 그 수의 배수인 값을 지워주어야한다. - 단, 2, 4, 6, ... 과 같이 2의 배수를 지웠는데 3, 6, 9 ,... 처럼 6이 중복이 된다면 6을 또 지워줄 수 없다. - 그러므로 그 수를 지우기 전에 앞에서 지웠는지 확인을 해주어야 한다. - 확인했는데 앞에 그 수가 없다면 지워준다. 2. 구상한 아이디어를 바탕으로 코딩하기 #include int main() { using namespace std; int num[1000] = { 0, }; // ..
(C++) 백준 2231번 [분해합]
안녕하세요 평범한 컴공생입니다. 오늘은 백준 2231번 문제 [분해합] 알고리즘 포스팅을 해보도록 하겠습니다. 브루트포스 문제이며 쉬운 난이도에 속합니다. 1. 문제 해결 방법 구상하기 - 먼저 N의 값을 입력받는다. - 메모리 제한이 넉넉하므로 완전탐색을 하면 될 듯하다. - 1부터 N-1 까지의 모든 수를 분해합하여 N과 같은가 비교하면 될듯하다. - 가장 작은 생성자를 구하면 되므로 반복문을 돌리다 생성자를 찾았을 경우 반복문을 탈출하여주면 최솟값만 구할 수 있다. - cout해줄 변수의 값에 0을 초기화해주고 값이 나올 경우 변수의 값에 대입을 해주면 될 듯하다. 못 찾았을 경우 그대로 0이 출력되기 때문이다. 2. 구상한 아이디어를 바탕으로 코딩하기 #include int main() { usi..