문제 설명 입력에서 무작위로 섞어져있는 3x3 퍼즐을 입력으로 준다. 이 퍼즐을 문제 맨 위에 있는 그림과 같이 초기 상태로 만드는데에 걸리는 최소 횟수를 구하는 문제다.문제 풀이 기본적인 BFS 문제와 같이 visit 처리를 해주면서 초기상태와 같아졌을때에 depth 혹은 count를 출력하면 된다.하지만 보드가 2차원 배열에 해당하기 때문에 이를 unordered_map의 키값으로 visit 처리를 해주기 위해서 2차원 배열의 숫자를 문자열로 바꿔주는 함수를 추가해서 visit 처리와 bfs의 값으로 이용하는 과정에서 사용했다.코드#include #include #include using namespace std;#define FOR(i,N) for(int i=1; i board_map;void pr..

BOJ.1005 ACM CRAFT 문제https://www.acmicpc.net/problem/1005문제 설명문제에서 입력으로 주어지는 건물이 지어지기까지의 최단 시간을 구하는 문제특정 건물을 짓기전에 먼저 지어야하는 건물의 순서가 주어진다먼저 지어야 하는 건물들을 지으면서 입력으로 주어지는 W에 해당하는 건물이 지어지기 까지의 시간을 구하면 된다문제 풀이이 문제와 같이 순서가 주어지고 먼저 해결해야할 작업이 있을때의 경로에 관한 문제는 위상 정렬(Topology Sort)로 해결할 수 있다.위상정렬(Topology Sort)는 가장 먼저 시작할 수 있는 일이 담긴 노드를 큐(Queue)에 넣어주고 시작한다.가장 앞에 있는 노드를 꺼내고 해당 노드와 연결된 간선을 모두 제거한다.간선들을 제거하면서 먼저..

백준 10942번 펠린드롬? (C++)문제 설명주어진 수열에서 펠린드롬을 찾아내는 문제.a,b가 주어지면 a~b의 수열이 펠린드롬인지 판별해야함.풀이펠린드롬을 직접 판별하는 것은 매우 간단하지만, 질문을 1000000번 할 수 있기 때문에 최악의 경우 시간이 너무 오래걸릴 수 있다. 이 문제의 시간 제한은 0.1 초이기 때문에 DP를 생각해야한다.길이가 1인 수열일 경우 항상 펠린드롬.길이가 2인 수열일 경우 두 숫자가 같다면 펠린드롬.길이가 3이상인 수열일 경우 양 끝의 숫자가 같고 그 사이의 수열이 펠린드롬일 경우 펠린드롬.위 3가지 조건을 고려하여 DP로 해결하였다.코드ㅇㄹㅇㄹ#include using namespace std;#define FOR(i,N) for(int i=1; i> N; F..

문제 설명압축 가능한 정사각형 형태의 구역을 탐색하는 문제흑백 영상을 압축하여 표현하는 쿼드트리문제 풀이압축 가능한 영역을 가로 세로 길이가 N인 영역부터 탐색을 시작하여 범위를 줄여간다.압축이 가능한지 판별후 불가능하다면 새로운 범위를 탐색 시작하며 '(' 를 추가하고 특정 구역에 대한 탐색이 끝날때마다 ')' 를 추가한다.분할 정복 알고리즘(Divide and conquer)를 이용하여 탐색 영역을 좁혀가며 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단 순으로 탐색한다.코드#include using namespace std;#define FOR(i,N) for(int i=1; i> N; FOR(i,N) { string s; cin >> s; for(int j=0; j

백준 15591번 MooTube (C++)문제 설명특정 영상과의 유사도가 k 이상인 영상의 개수를 추천하도록 하는 문제.영상 A에서 영상 B까지의 가는 경로 중 가장 유사도가 적은 값을 AB 영상간의 유사도로 결정한다.문제 풀이##예를 들어, 영상 A에서 출발해서 갈 수 있는 모든 경로를 탐색한다.이때 영상 A에서 갈 수 있는 경로들에 대해 해당 경로에서의 유사도중 취소값을 방문 중인 영상과의 유사도로 저장한다.경로 탐색을 위해서 dfs를 사용했다. (모든 경로에 대해 탐색을 해야하기 때문, bfs를 사용해도 무관)코드#include #include using namespace std;#define FOR(i,N) for(int i=1; i graph[5001];int cost[5001][5001];in..

백준 1068번 트리 (C++)문제 설명문제에서는 각각 노드의 부모노드를 알려주는 방식으로 트리를 제공한다. 해당 트리에서 특정 번호의 노드를 제거 했을때 하위의 자식 노드들은 사라지게 되고 이때 leaf node의 개수를 출력해야한다.문제 풀이입력 방식:편의상 각각의 노드 번호에 +1을 하여 1번~N번 노드로 정하고 풀이했다.루트 노드부터 방문해서 내려가기 위해서 루트 노드의 번호는 따로 vector에 저장했다.부모 노드부터 자식 노드까지 탐색하기 위해서 vector 배열을 이용해서 배열 인덱스에는 부모노드 해당 배열의 벡터 인덱스에는 자식 노드를 표시하였다.알고리즘 선택:더 이상 내려갈 수 없는 경우에 리프 노드의 개수를 +1 해주면 되기에 bfs를 사용했다. 루트 노드를 기준으로 dfs 혹은 bfs..

백준 1092번 배(C++)문제 설명:최대로 옮길 수 있는 무게가 제한되어있는 크레인이 주어지고 옮겨야 할 박스의 무게들이 주어진다.각 크레인은 동시에 박스를 하나씩 옮길 수 있고 모든 박스를 옮기는데에 걸리는 시간을 출력해야한다.모든 박스를 옮길 수 없는 경우 -1을 출력한다.문제 풀이:각 크레인은 남겨진 박스들 중에 옮길 수 있는 가장 무거운 박스들을 선택해서 하나씩 선택하고 동시에 옮긴다.크레인과 박스를 벡터에 각각 저장하고 두 벡터를 내림차순 정렬한다.스택(stack)을 이용하여 옮기지 못하는 박스는 다시 우선적으로 옮기도록 한다.모든 박스를 옮길 수 없는 경우가장 힘이 센 크레인이 옮길 수 없는 박스가 존재하는 경우.코드#include #include #include #include using ..