본문 바로가기

전체 글

(129)
[C++/14499] 주사위 굴리기 - using simulation 14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 solution 주사위를 굴리는 방향에 따라 달라질 수 있는 맨 위의 숫자를 출력하는 시뮬레이션/구현 문제이다. 이때 주사위 전개도에 따라서 다음과 같이 크게 2개의 배열로 구분 가능하다. 1. 세로 배열 2. 가로 배열 주사위를 굴리는 방향에 따라서 특정 배열만 회전해주면 된다. 입력이 1, 2 인 경우: 동쪽과 서쪽으로 움직이는 것이기 때문에 가로 배열 회전 입력이 3, 4인 경우: 북쪽과 남쪽으로 움직이는 것이기 때문에 세로 배열 회전 이때 중요한 점은 가로 배열과 세로 배열은 값이 공통인 부분이 존재한다는 것이다. (위쪽과 아래쪽) 따라서 이 부분은 특정 배열을 회전할 때마다 다른 하나의 배열에 값을 복사..
[C++/11559] puyo puyo - using simulation 11559 puyo puyo https://www.acmicpc.net/problem/11559 solution 전형적인 시뮬레이션 문제이다. 여기서 포인트는 어떻게 "아래로 떨어짐"을 구현하는가 이다. 아래로 떨어지는 걸 구현하기 위해서는 가장 밑에 있는 뿌요가 없애야 하는 것인지 아닌지에 따라 다르다. 만약 가장 밑에 있는 뿌요가 없어져야 한다면 위에서부터 한칸씩 내려오면서 값을 덮어씌우고 마지막에 맨 첫 줄의 뿌요 값을 . 으로 교체해주면 된다. 알고리즘은 다음과 같다. 1. 현재 필드 값을 보고 BFS를 돌려 인접한 색의 개수가 4개인 그룹을 찾는다. 2. 이 그룹의 값들은 없어져야 하기 때문에 이를 표시하기 위해 좌표를 저장했다가 * 으로 바꾼다. 3. 없어져야 하는 값들에 대해서 for문을 돌..
[C++] Heap 모음 (Priority Queue) 42626 더 맵게 https://school.programmers.co.kr/learn/courses/30/lessons/42626 solution 1. priority_queue 에 오름차순으로 scoville 배열의 원소들을 push 한다. 1-1. 내림차순으로 push 하기 위해서 priority_queue 를 사용하거나 원소에 -1을 곱해서 추가한다. 2. top -> pop -> top -> pop 를 통해서 낮은 원소 2개를 공식에 따라 섞고 push(first + second * -1) 를 한다. 2-1. 이때 맨 처음 top -> pop 과정을 거치고 pq가 empty가 되었는데도 first의 값이 K보다 작으면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없으므로 -1을 return..
[MySQL] SQL 문제 모음 131528 나이 정보가 없는 회원 수 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/131528 SELECT count(*) FROM USER_INFO WHERE AGE IS NULL 59407 이름이 있는 동물의 아이디 https://school.programmers.co.kr/learn/courses/30/lessons/59407 SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NOT NULL ORDER BY ANIMAL_ID 131120 select where https://school.programmers.co.kr/learn/courses/30/lessons/131120 SELECT MEMBER..
[C++] 정렬 모음 42747 H-Index [문제 바로가기] solution 1. 내림차순으로 citations 배열을 정렬한다. 2. citations의 크기에서부터 0까지 i를 감소시키면서 for문을 돈다. 2-1. 가능한 h의 최대는 citations의 크기이다. (ex. [2, 2]) 3. 이때의 i값이 가능한 h값인지 탐색한다. 3-1. citations의 값이 i보다 크거나 같으면 정렬이 안되어 있으므로 탐색 인덱스를 증가시킨다. 3-2. 이때 같은 경우에도 증가시키는 이유는 문제 조건이 "이상" 이기 때문에 값에 포함되기 때문이다. 3-3. citations 값이 맨 처음으로 i보다 크거나 같아지는 순간이 정답이다. #include #include #include using namespace std; int ..
[C++] DFS/BFS 모음 43165 타겟 넘버 [문제 바로가기] solution 1. 배열을 돌면서 배열의 원소를 더하거나 빼거나 두 가지 경우에 대해서 재귀를 실행한다. 2. 모든 배열을 탐색했을 때 만든 숫자가 target과 같다면 결과 +1 을 한다. #include #include using namespace std; int result; void dfs(int n, int target, vector numbers, int idx) { if (idx == numbers.size() && n == target) { result++; return; } if (idx >= numbers.size()) return; dfs(n + numbers[idx], target, numbers, idx + 1); dfs(n - number..
[C++] Hash 모음 1845 폰켓몬 [문제 바로가기] solution 1. nums 배열을 돌면서 nums[i] 포켓몬의 번호에 해당하는 배열의 값을 + 1 해준다. 2. 모든 번호를 돌면서 해당 포켓몬의 수가 0 이상이면 가져갈 수 있기 때문에 결과를 +1 하고, 남은 선택해야 하는 수는 -1 한다. #include #include using namespace std; int solution(vector nums) { int answer = 0; int n = nums.size(); int hash[200001] = {0}; for(int i = 0;i 0..
[C++] 완전 탐색 모음 42839 소수 찾기 [문제 바로가기] solution 1. numbers로 만들 수 있는 모든 경우의 수에 대한 숫자를 구한다. 2. 중복을 제거한다. 3. 숫자에 대해서 소수인지 판별한다. 이때 중복을 제거하기 위해 unique() 함수를 사용한다. 주의할 점은 정렬이 되어 있어야 한다는 것이다. unique 함수는 중복되지 않은 수를 앞에서부터 정렬하고 중복이 시작되는 배열 주소를 반환한다. 따라서 반환된 주소부터 끝까지 삭제하여 중복을 제거한 배열을 생성할 수 있다. #include #include #include #include using namespace std; bool is_prime(int n) { if (n < 2) return false; for(int i = 2;i 5) return..