Coding_Test_C++
BaekJoon 15663번: N과 M (9)
풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) sort() 함수를 이용해서 오름차순으로 초기 배열을 정리해야 한다. 3) 중복에 함정이 존재한다. 이를 주의 해서 코딩해야 하며, 중복의 기준이 무엇인지 알아야 한다. 4) 같은 level의 직전의 함수와 새로운 값이 같으면 출력해서는 안된다. 추가 반례 입력 3 3 1 1 2 출력 1 1 2 1 2 1 2 2 1 #include #include #include using namespace std; int n, m; vector vec; int arr[9]; bool visited[9]; void backtracking(int level) { if (level == m) { for (..
BaekJoon 15655번: N과 M(6)
풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 초기 배열을 오름차순으로 정리한다. 3) 현재 설정된 배열의 마지막 index 값을 라스트로 두어서 이보다 새로운 값이 작을 경우 continue 한다. #include #include #include using namespace std; int n, m; vector vec; int arr[9]; bool visited[10001]; void backtracking(int level, int last) { if (level == m) { for (int i = 0; i > m; for (int i = 0; i < n; i++) { int a; cin..
BaekJoon 15654번: N과 M (5)
간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다. 풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) sort() 함수를 이용해서 오름차순으로 초기 배열을 정리해야 한다. 3) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을 생각해 낸다면 어렵지 않게 풀 수 있는 문제이다. #include #include #include using namespace std; int n, m; vector vec; bool visited[10001]; int arr[9]; void backtracking(int level) { if (level == m)..
BaekJoon 15652번: N과 M(4)
풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 중복이 허가되나 증가하는 순서의 수열을 만들기 위해서는 배열의 마지막 인덱스 값을 가지고 반복을 수행한다. #include #include #include using namespace std; int arr[9]; int n, m; void backtracking(int level, int last) { if (level == m) { for (int i = 0; i < m; i++) { cout m; backtracking(0, 1); } github.com/pearlcrum/CodingTest/tree/main pearlcrum/CodingTest ForPracticingCoding..
BaekJoon 15651번: N과 M (3)
간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다. 풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 방문한 곳을 다시 방문할 수 있기에 반복을 통해 구현하면 된다. #include #include #include using namespace std; int arr[8]; int n, m; void backtracking(int level) { if (level == m) { for (int i = 0; i < m; i++) { cout m; backtracking(0); } github.com/pearlcrum/CodingTest/tree/main pearlcrum/CodingTest ForPr..
BaekJoon 15650번: N과 M(2)
간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다. 풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을 생각해 낸다면 어렵지 않게 풀 수 있는 문제이다. 3) arr배열의 가장 마지막 원소에 들어가 있는 값을 last으로 두고 이 보다 큰 for문을 돌리면 문제에서 요구하는 오름차순 수열을 만들 수 있다. #include #include #include using namespace std; int n, m; int arr[9]; bool check[9]; void backtracking(in..
BaekJoon 15649번: N과 M(1)
간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다. 풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을 생각해 낸다면 어렵지 않게 풀 수 있는 문제이다. #include #include #include using namespace std; int n, m; int arr[9]; bool visited[9]; void dfs(int level) { if (level == m)// 원하는 level에서 출력할 것 { for (int i = 0; i < m; i++) { cout
BaekJoon 5639번: 이진 검색 트리
문제는 그닥 어렵지 않았으나 입력을 처리하는 것이 상당히 어려웠던 문제이다. EOF에 대해서 잘 모르고 있었기에 시간이 걸렸으며 런 타임 에러와 싸우다 겨우 성공해 낸 문제이다. 풀이법 1) 이진 검색 트리의 경우 root 값을 잡은 후 root를 기준으로 큰 지 작은 지 비교하면 쉽게 풀 수 있다. 2) 재귀를 이용해서 구현하면 더욱 쉽게 풀 수 있을 것이다. 3) EOF에 대한 개념은 한번 쯤 봐두는 것이 좋을 듯 싶다. #include #include #include #include #include #include using namespace std; int n; struct node { int left; int right; }; vector vec; node arr[1000001]; int rot..
BaekJoon 1991번: 트리 순회
풀이법 1) 재귀를 통해 전위, 중위, 후위를 순회한 값을 구한다. 2) node의 값을 뽑는 위치의 차이이기에 일종의 공식처럼 알아 두면 좋을 듯 하다. #include #include #include #include #include using namespace std; int n; struct node { char left; char right; }; struct node arr[27]; void pre(char root) { if (root == '.') return; cout > a >> b >> c; arr[a].right = c; arr[a].left = b; } pre('A'); cout
BaekJoon 1967번: 트리의 지름
트리의 지름을 구하는 알고리즘은 앞서 푼 BaekJoon 1167번: 트리의 지름 문제와 같다. pearlcrum.tistory.com/4?category=989437 BaekJoon 1167번: 트리의 지름 트리의 지름을 구하는 알고리즘이다. BFS를 써서 문제를 해결하고자 했으나 마땅한 방법이 생각나지 않아 다른 블로그의 힘을 빌렸다. blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가 pearlcrum.tistory.com 풀이법 1) 아무 노드 a (이 코드의 경우 1)를 이용해서 a에서 가장 먼 점인 x를 구한다. 2) x에서 가장 먼 노드인 y를 구하고 x-y 간의 거리를 구한다. (지름 구하기) 3) BFS를 이용하여 vistied 배열과 dist 배열을 사용하여..