Algorithm
-
백준 2839 설탕 배달Algorithm/DP 2021. 11. 13. 04:54
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net - 2가지의 풀이법이 있다. Greedy, DP - Greedy 풀이법을 보면, 주어진 N에 3을 빼주면서, 뺄 때마다 해당 수가 5의 배수인지를 확인한다. 5의 배수가 되는 순간 남은 모든 무게를 5kg 봉지로 해결하면 되므로 그것이 해답이다. #include using namespace std; int N; int main() { cin >> N; int ans = 0; while (N >= 0) { i..
-
백준 14502 연구소Algorithm/그래프 2021. 11. 12. 20:14
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - N과 M이 최대 2^3이므로, 많은 for문을 중첩시킬 수 있다. (NM = n || ny >= m) continue; if (virus[nx][ny] == 0) { virus[nx][ny] = 2; visited[nx][ny] = true; q.push({ nx,ny }); } } } // 안전구역 검사 후, answer 최신화 int cnt = 0; for (int i = 0; i < n; i++) {..
-
백준 14501 퇴사Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 11. 12:32
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net - 재귀의 깊이를 보면, 백트래킹으로 풀 수 있는 각이 나온다. 특정 일에 상담을 하는 경우, 하지 않는 경우 2가지의 경우의 수가 있고, N이 15이하이므로 최대 2^15 의 경우의 수가 가능하다. 즉, 시간초과를 걱정 할 필요가 없다. - 첫 호출은 1일차, profit은 0로 한다. 여기서 1일차에 상담을 하기로 결정했다면 1일차의 profit을 현재 profit에 더하고, 상담에 걸리는 시간을 추가해서 호출을 한다. - 백트래킹의 종결조건으로는 1. day가 n+1보다 많은 경우, 즉 퇴사일을 넘기는 경우는 상담을 못 하는 것..
-
백준 14500 테트로미노Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 9. 12:51
- 브루트포스 문제인데 정말 무식한 문제이다.. 다시는 풀기 싫은 문제 - 시간복잡도는 O(NM)이다. - 모든 가능한 블럭의 경우의 수를 먼저 생각하고, 이들이 주어진 범위에 어떻게 들어갈 수 있는지를 생각하면 된다. 꼼꼼하게 오류 없이 푸는게 중요한 것 같다. /* 모든 경우의 수를 다 고려한다 */ #include using namespace std; int a[500][500]; int main() { int n, m; cin >> n >> m; for (int i = 0; i a[i][j]; } } int ans = 0; for (int i = 0; i= 0 && j + 2 < m) { // ㄴ 좌우 대칭해서 가로로 긴 것 int temp = a[i][j] + a[i][j + 1] + a[i][..
-
백준 14499 주사위 굴리기Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 9. 12:14
- 삼성 SW 기출문제에서도 쉬운 편에 속하는 문제이다. 꼭 맞추고 들어가야 하는 문제라 생각. - 핵심적인 부분은, 주사위가 다음 칸으로 이동할 때 이동 가능한 범위인지를 체크하는 것과, 주사위의 각 면들의 값을 하나의 배열로 관리하고 동,서,남,북으로 이동시 각 면의 값이 어떻게 변하는 지를 잘 반영하면 된다. #include int square[7]; int map[20][20]; using namespace std; int dx[] = {0,0,-1,1}; int dy[] = {1,-1,0,0}; int main() { int N, M,x,y,k; cin >> N >> M >> x >> y >> k; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j..
-
백준 13458 시험 감독Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 5. 17:06
- 문제의 풀이법 자체는 쉽지만, 오답률이 높은 이유는 result에 int를 사용해서 일 것이다. - 시험장이 1,000,000이고 응시생도 1,000,000 이고, 감독가능한 인원이 1,2 와 같은 소수일 경우 필요한 감독관 수는 어마어마하게 많아진다. 따라서 result의 자료형은 8byte 정수 자료형인 long long을 사용한다. int가 양수 21억까지 표현 가능하니 21억 x 2^16 하면 경 단위까지 표현이 가능해서 충분하다. - 총 감독관이 감독할 수 있는만큼 각 시험장의 인원을 빼주고, 다시 순회하면서 부감독관들이 관찰 가능한 인원들을 활용하여 구해준다. 여기서, 이미 총 감독관 하나로 모든 인원이 감독 가능할 시, arr[i]값이 음수가 될 수 있으므로 예외처리를 해 준다. 시간복잡..
-
백준 3190 뱀Algorithm/구현(Brute force, Back tracking, etc.) 2021. 11. 4. 17:56
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net - 초기 설계를 잘 해야하는 시뮬레이션 문제이다. - 일단 방문 여부를 체크하기위한 d 배열을 둔다. d에는 가장 최근에 방문한 시간이 들어간다. - 만약 d가 -1이 아니면, 이전에 방문한 적이 있는 것이고 그와 동시에 해당 격자판에 현재 몸통이 존재하는지 를 체크해준다. 이는 now와 몸 길이 len으로 체크한다. - now에 1을 더해주고, x,y와 격자판 범위를 넘어가는 지를 체크한다. 다음으로,..
-
[프로그래머스] 오픈채팅방Algorithm/자료구조 2021. 10. 1. 12:55
문제 : https://programmers.co.kr/learn/courses/30/lessons/42888?language=javascript 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr - record의 길이는 100,000이기 때문에, O(NlogN)이하의 알고리즘을 구현해야 한다. - hash를 이용하면 쉽게 풀 수 있는 문제이다. (설명이 길어서 살짝 쫄았다..) - 자바스크립트는 Map 생성자를 통해 hash를 구현할 수 있다. function solution(record) { var answ..