백트래킹 중복된 값을 없애보자
중복된 값을 찾을 때 이렇게?temp로 값을 저장하고 백트래킹으로 돌아왔을 떄 그 temp값과 비교하는 방식
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
int arr[10]; //결과 index가 들어갈 배열
int value[10]; // 배열에 넣을 value값이 들어갈 예정
int isused[10];// 본인제외 배열
int n, m;
void func(int k ){
if(k==m) {
for(int i=0; i<m; i++)cout << value[arr[i]]<< " ";
cout<< "\n";
return;
}
int temp=0;
for(int i=0; i<n; i++) {// index의 순서를 넣는 방법
if(temp !=value[i]){
arr[k] = i;
temp = value[arr[k]];
func(k+1);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >>n >> m;
for(int i=0; i<n; i++) {
cin >> value[i];
}
sort(value, value+n);
func(0);
}
REVIEW
풀었었는데 까먹어버린문제 ㅎㅎㅎㅎ... 복습은 중요하다. 정확히 한 달 지나니까 까먹어버린 개념
그래프 돌리기
그래프 문제를 보면 열과 행이 바뀌는 경우가 종종 존재한다.
바로
일루미네이션요런 문제류? 받을 때 행과 열이 뒤바뀌는 경우가 있다.
이런 느낌? 하지만 사실 직접 구현해보면서 부딪히는게 제일 낫지 않나 싶은 생각이 든다.
보통 이런 경우 맵을 90도로 돌려버리면 왼쪽의 형식처럼 쓸 수 있다. 하지만 이 경우는 처음에 map받을 때 고민해야하는 부분이라서 잘 생각해보면 좋을 것 같다.
오늘의 코테 문제
일루미네이션
페어 프로그래밍을 해보고 피드백을 받아보면서 이 문제에 총 3가지 로직을 알아낼 수 있어서 재밌었던 시간!
- 3차원,오각형, 육각형 모두 인접한 거리를 구하는 로직을 알아낼 수 있다면 한 계단 올라갈 수 있던 문제! (그리고 애초에 일정한 그런... 느낌이 있었음)
외벽, 내벽을 BFS로 카운트해서 외벽과 내벽이 만나는 구간을 카운트하기
외벽과 내벽이 만났을 때 테두리의 값이 된다. 그래서 외벽만을 카운트 하는 외벽 bfs따로(건물에 둘러쌓인 내벽은 검사하지 않기위해 가장자리부터 검사를 수행하게 된다.)
내벽을 카운트하는 bfs따로 그리고 bfs로직을 수행하면서 외벽과 만나는 곳이면 count를 해준다. 이 값이 정답이 되는 것
외벽을 한 겹 둘러서 바깥 부분만 BFS수행하기
외벽을 한 겹 둘러서 바같 부분만 bfs를 수행하게 되면 내부에 빵꾸뚫려있는 부분?(건물에 둘러쌓인 외벽부분)을 무시할 수 있게 된다!
테두리를 카운트하는 부분
클럽장님의 방법
벽 하나는 여섯개의 테두리를 가진다. 그럼 내벽과 내벽이 맞닿아 있으면? 6개의 맞닿은 수 많은 줄이면 된다.
이런 형식으로 맞닿아 있는 친구들을 세서 6개에서 빼버리면 되는 것! 미처 생각해보지 못한 방법이었다!
REVIEW
오늘 새로운 방법? 한 가지 문제에 대해 여러생각이 나오게 돼서 좀 신기했당. 그리고 풀이 방식을 조금 넓혀가게 된 느낌? 이제는 다른 사람이 설명해주는걸 이해할 수 있게 되었다 ㅋ(물론 이해하기 위해서 내가 문제를 완벽하게 이해하려는 것도 있다. ~~잘 안되지만 ~~)
다른 레벨의 문제도 다양하게 풀어보는 방법을 생각해봐야할 것 같다.
그리고 지금 듣고있는 알고리즘도 그냥 음... 코테 스터디에 좀 더 집중하고 스터디하다가 모르는 문제가 나왔을 때 그걸 복습하는 느낌? 처음부터 다지는 느낌으로 시작해야할 것 같다. 더 다양하게 풀어보는것도 중요하지만 하루에 공부할 수 있는 양의 한계가 있다 ㅠ
