공부혜옹

정답코드는 맨 하단에 기입해놓았다. 오랜만에 효율성에서 애먹은 문제를 만나 나중에 까먹지 않으려고 포스팅한다. 먼저 stones의 배열 크기와 원소 크기를 보고 그냥 구현하면 시간초과 나겠거니 해서 이분탐색으로 풀었다. 범위가 많고 배열을 순회하며 값을 찾아야할땐 이분탐색이 적절한 케이스가 많은것 같다. 문제 코딩테스트 연습 - 징검다리 건너기 문제풀이방식(이분탐색) 스톤의 원소들이 모두 1이라면? 한사람밖에 건널 수 없다 하지만 2억이라면? 2억명의 친구들이 건널 수 있다. 따라서 배열 stones의 최소 원소가 건널 수 있는 친구의 최저(left), 최대원소가 건널 수 있는 친구의 최대(right)인것이다. stones 배열을 copy하고, 중간값(mid)을 구해 배열을 순회하면서 mid를 빼준다. ..

https://hae-ong.tistory.com/89?category=883090 백준 15663 N과 M (9) https://hae-ong.tistory.com/88 백준 15657 N과 M (8) 재귀를 이용해 모든 수의 조합을 구하면 되는 문제였다. 단, 수열의 길이제한이 있으므로 해당 조건은 탈출조건으로 설정한다 #include #include #include #.. hae-ong.tistory.com 15663을 풀었다면 더할나위없이 쉬운 문제이다. 15663을 포스팅할 당시 '중복선택이 안되는 부분은 visited라는 배열로 체크해주었다' 라고했는데 이번 문제는 중복선택이 되고, 중복수열만 제한하면 되는 문제였기 때문에 visited로 검사하는 조건을 삭제했다. #include #inclu..

https://hae-ong.tistory.com/88 백준 15657 N과 M (8) 재귀를 이용해 모든 수의 조합을 구하면 되는 문제였다. 단, 수열의 길이제한이 있으므로 해당 조건은 탈출조건으로 설정한다 #include #include #include #include using namespace std; int n, m; int arr[9]; i.. hae-ong.tistory.com 15657번 문제와 달리 수를 중복 선택해서는 안되는 문제였다. 중복선택도 안되고 중복 수열도 안되기때문에 관련 조건을 2개 넣어주었다. 중복선택이 안되는 부분은 visited라는 배열로 체크해주었고, 중복수열이 안되는 부분은 prev != arr[i]로 바로 전 수열의 맨 끝자리숫자가 현재 들어갈 예정인 숫자와 동일..

재귀를 이용해 모든 수의 조합을 구하면 되는 문제였다. 단, 수열의 길이제한이 있으므로 해당 조건은 탈출조건으로 설정한다 #include #include #include #include using namespace std; int n, m; int arr[9]; int ans[9]; void func(int index, int cnt){ if(cnt == m) { for(int i=0; i m; for(int i=0; i> arr[i]; } sort(arr,arr+n); func(0,0); return 0; }

쉬운 문제였는데 테스트케이스를 몇개 줄건지 말을 안해줘서 while(cin >> n) 부분을 빼먹었더니 틀렸던 문제다..화가 난다 풀이 방법은 각자의 숙련도가 들어올때마다 비트마스킹해서 그 값과 기존의 숙련도 비트 리스트와 비교해 리스트에 동일한 값이 있으면 넘어가고 없으면 리스트에 추가했다. 마지막으로 정답은 해당 리스트의 크기를 출력해주었다 푼사람이 없어서 적절한 풀이인지는 잘 모르겠지만 일단 정답처리는 되었다. 아마 비슷한 맥락내에서 더 효율적으로 구현하는 방법이 있을듯! #include #include #include using namespace std; int n; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); while(cin>>n){ ..

비트마스크 문제중에 쉬운편이었다. 풀이방법은 1. 단어를 비트마스킹해서 비트로 표현한다 2. 비트로 이루어진 온전한 알파벳판을 만든다 ex) a, b 만 있는 판은 -> 00000011 이런식으로 3. 1번케이스와 2번 케이스를 나누어 구현한다 3-1. 1번케이스의 경우 XOR 연산( 둘중 하나만 1일경우 1 )을 이용해 해당 알파벳 비트를 0으로 만든다 3-2. 2번케이스의 경우 OR연산( 둘중 하나라도 1일경우 1 )을 사용해 해당 알파벳 비트를 1로 만든다 4. 이렇게 만들어진 알파벳판과 본래의 단어비트를 &연산 ( 둘 다 1이여야 1 )한 값이 본래의 단어비트와 같은지 확인한다 5. 같을경우 cnt를 증가시켜서 갯수를 세어준다 로 단어를 비트로 바꾸고 비트연산을 할 줄 알면 풀 수 있는 문제였다...

의외로 굉장히 쉬웠던 문제였다. 갔던길을 또다시 갈 수 있으나 두 지점을 점프해서 갈 수는 없다 꼭 한칸씩 이동해야한다는 것이다. 제약사항이 없는 상태에서 한칸씩 이동할 수 있는 상황이고, 이때 모든 n개의 노드를 방문하는 가장 최소의 움직임은 n-1일 수 밖에 없다. #include #include using namespace std; int t, n, m; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while(t--){ cin >> n >> m; for(int i=0; i> a >> b; } cout

처음엔 두가지 노드를 동시에 조상을 거슬러 오려니 어떻게 같은 조상을 찾을 수 있는지 조금 막막했다. 옛날에 비슷한 문제를 풀어봤던것같은데..ㅜㅜ 노드와 함께 깊이를 저장해 거슬러올라올까 하다가 굳이 그렇게 복잡하게 생각할 필요 없이 노드1을 루트 조상까지 먼저 쭉 방문하게 하고 나머지 노드2의 조상을 탐색하다가 노드1이 이미 방문한 노드를 공통조상으로 판별하였다. #include #include #include #include #include using namespace std; int t, n; int node1, node2; void func (int tree[],int check[],int num){ if(tree[num] == 0){ if(check[num]==1){ cout > b; //b의 ..