본문 바로가기

Algorithm/programmers42

2019 Kakao blind 42894 - 블록게임(배열, 구현) c++ 풀이 - 6번 매칭점수 문제보다 더 쉬운 문제 같다. 맵의 모든 범위를 블록 사이즈인 2*3, 3*2 범위로 탐색하면서 위에서 블록을 떨궜을 때 직사각형을 만들 수 있는지를 계속 체크해나가는 식으로 문제를 풀었다. 블록 모양이 정해져있어서 추가된 블록 갯수가 2개여야만 직사각형이 만들어지는 조건을 이용해서 쉽게 풀 수 있다. #include #include using namespace std; vector Board; bool canFill(int r, int c) { // 행 검사 for(int i = 0; i < r; ++i) { if(Board[i][c] != 0) return false; // 위에 모두 빈칸이여야 } return true; } bool find(int sr, int sc, int h,.. 2021. 9. 6.
2019 Kakao blind 42892 - 길 찾기 게임(이진 트리 순회) c++ 풀이 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr - 뭔가 교과서적인 문제였다. 그동안 백준에서 트리그래프 알고리즘 문제를 풀 때 부모노드 idx만 담는 int 배열로 트리를 구현하곤 했는데, 이렇게 자식정보를 담는 노드를 구현해야되는 문제를 오랜만에 풀어봐서 간만에 알고리즘 전공서를 펴서 트리 순회하는 파트를 복습하는 계기가 됬다. inorder, preorder, postorder 구현보다 트리를 구현하는게 .. 2021. 9. 6.
2019 Kakao blind 42891 - 무지의 먹방 라이브(배열 순회, 우선순위큐) c++ 풀이 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr - 일단 효율성 테스트 조건이 굉장히 빡세므로(k가 20조) 복잡도를 낮추기 위한 logN 알고리즘을 사용할 것을 가정에 두고 문제를 읽어내려갔다. - 주어진 food_times 벡터에서 가장 작은 소요시간을 가진 음식을 소거시켜나가는 사이클을 돌리는 식으로 문제를 풀었다. 여기서 가장 작은 소요시간을 가진 음식을 남은 시간 k보다 남은 음식을 가지고 사이클 한바퀴를 도는 시간이 길어서 k초 전에 사이클이 끝나는 경우가 나올 때까지 다 먹은 음식을 소거시켜 나가야된다. 그래서 빠르게 최소소요시간을 찾을 수 있게 최소힙을 이용하였다. .. 2021. 9. 6.
2019 Kakao blind 42890 - 후보키(완전탐색, 비트마스킹) c++ 풀이 https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr - 일단 후보키 개념이 문제에서 설명되어 있지만 이 개념을 미리 알고 있어야 더 쉽게 접근해볼만한 문제였다. 후보키 개념이 잘 이해가 안 가서 데이터베이스 대학강의를 다시 들어보았다. 알고리즘 과목 외의 CS개념이 있어야 이해가 가능한 문제.. 2021. 9. 6.

티스토리툴바