컴굥일지

문제 https://www.acmicpc.net/problem/12919 문제 내용 문자열 s와 t를 입력받아 아래의 연산들을 수행했을 때 s가 t가 될 수 있는지를 구하면 된다. - 문자열의 뒤에 A를 추가한다. - 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. 문제 풀이 이 문제를 s에서 t로 변환 가능한지로 풀이하면 안 된다. s에서 위의 2가지 연산을 했을 때 t가 되는지 판단하는 것은, t의 길이가 50까지 가능하기 때문에 약 2^50가지의 경우를 체크해야 하기 때문이다. (실제로 이렇게 풀었더니 시간 초과가 발생함) 이 문제는 t에서 s로 변환 가능한지 체크해야 한다. 마지막 글자가 A인 경우와, 첫 글자가 B인 경우를 보며 되돌아오면 된다. 코드 t -> s 방식 #include #incl..

문제 https://www.acmicpc.net/problem/17144 문제 내용 R*C 격자 판이 있고, 1열에는 공기청정기가 있다. 매 초마다 미세먼지는 확산하게 되며, 미세먼지 확장 이후에는 공기청정기의 순환에 따라 먼지가 이동한다. 미세먼지 확산 시, 공기청정기가 있는 곳이나 격자 판 밖으로는 확산되지 않는다. (확산되는 미세먼지 양은 사진 참고) 공기청정기는 위의 사진처럼, 윗부분은 반시계 방향, 아랫부분은 시계방향으로 공기를 순환시키며, 공기청정기에서 나가는 바람은 먼지가 없고, 공기청정기로 들어가는 미세먼지는 모두 정화된다. 문제 풀이 문제에 나온 과정대로 함수를 나누어 구현하면 된다. 1. 미세먼지 확산 2. 공기청정기 작동 3. 격자 판의 미세먼지 합 구하기 (1,2번은 매 초마다 반복..

문제 https://www.acmicpc.net/problem/1388 문제 내용 - 와 | 로 이루어진 바닥 장식 모양이 주어진다. 만약 가로로 - 가 이어져있거나, 세로로 | 가 이어져있으면 각각은 하나의 나무 판자이다. 바닥의 배열이 주어지고, 나무 판자의 개수를 구하면 된다. 문제 풀이 dfs로 간단하게 풀이할 수 있다. 현재 칸이 - 이면 무조건 오른쪽 칸이 - 인지 확인하고, 현재 칸이 | 이면 무조건 아래 칸이 | 인지 확인하면 된다. 코드 #include using namespace std; int n, m; char arr[50][50]; int visit[50][50]; void dfs(int cnt, int r, int c) { visit[r][c] = cnt; if (arr[r][c..

문제 https://www.acmicpc.net/problem/1260 문제 내용 그래프에 대한 내용을 입력받고, V번 정점부터 DFS와 BFS를 수행한 결과를 출력하면 된다. 문제 풀이 인접리스트 방식으로 문제를 해결해 보았다. 인접 행렬로도 풀릴 것 같기는 한데, 노드가 1000개까지 될 수 있어 인접 행렬을 arr[1001][1001] 이런 식으로 선언을 하게 되면 메모리 초과가 발생할 수도 있을 것 같다. (ide에 제한이 있을 수도 있어서...) +) 백준에서 다른 사람 제출 내역을 보니, 인접행렬로 해도 문제를 풀 수 있다. 하지만 언젠가 N이 너무 커질 때를 대비해서 인접 리스트 방식도 알아두면 좋을 것이다. 코드 #include #include #include #include using n..

문제 https://www.acmicpc.net/problem/1715 문제 내용 정렬된 두 묶음의 숫자카드가 있다. 각 묶음의 카드의 수가 A, B개일 대, 두 묶음을 하나로 합칠 때 A+B번의 비교가 필요하다. N개의 카드 묶음을 받아, 이들을 두 묶음씩 골라 서로 합쳐나가려고 한다. 최소 몇 번의 비교가 필요한지 구하면 된다. 문제 풀이 문제에 나와있는 대로, 매번 가장 묶음이 작은 것을 2개 골라 합치면 된다. priority_queue를 통해 이 문제를 해결할 수 있다. (최소힙 사용) 코드 #include #include #include using namespace std; int main() { int n, tmp; priority_queue pq; cin >> n; while (n--) {..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121689 문제 내용 손님은 k초마다 카페에 들어온다. 각 메뉴를 만드는 시간을 담은 menu 배열을 입력받고, 카페에 오는 손님이 시키는 주문 내역인 order 배열을 입력받는다. 메뉴는 순서대로 만들어지며, 손님들은 자신의 음료가 나오면 바로 카페를 나간다. 최대 몇 명의 손님이 동시에 카페에 존재했는지를 구하면 된다. (같은 시각에 손님이 들어오고 나가는 경우, 카페에 있던 손님이 먼저 나가고, 그 이후에 새로운 손님이 들어온다.) 문제 풀이 음료 만드는 시간이 길어 여러 명의 손님이 기다리는 경우도 있지만, 음료 만드는 시간이 짧아 카페에 손님이 아무도 없는 경우도 생긴다. (손님은..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121688 문제 내용 교육에는 신입사원 2명이 필요하다. 교육 이후에는 서로의 능력을 흡수하여, 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 된다. 신입사원들의 능력치와 총 교육 횟수를 입력받아, 모든 교육 이후에 능력치 합이 최소가 되도록 하고 싶다. (한 번 교육을 받은 사원은, 다시 선발될 수 있다.) 문제 풀이 모든 교육 이후에 능력치의 합이 최소가 되려면, 매 교육마다 능력치가 제일 작은 2명을 골라야 한다. 이를 위해 priority_queue를 사용하여, 매번 가장 작은 능력치를 뽑으면 된다. 코드 #include #include #include using name..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121687 문제 내용 명령어 순서를 담은 문자열을 입력받아, 로봇이 해당 명령을 수행한 이후의 좌표를 구하면 된다. 문제 풀이 각각의 명령을 순차적으로 실행하여 이동을 하면 된다. 코드 #include #include using namespace std; int dy[4]={1,0,-1,0}; int dx[4]={0,1,0,-1}; vector solution(string command) { int dir=0; int y=0; int x=0; for(int i=0;i

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121685?language=cpp 문제 내용 완두콩의 세대와, 해당 세대에서 몇 번째 개체인지를 입력받아, 완두콩의 형질을 출력하면 되는 문제이다. 문제 풀이 가계도를 자세히 살펴보면, 재귀적인 부분을 찾을 수 있다. 완두콩이 자신의 형질을 알기 위해서는 부모의 형질을 알아야 하고, 부모의 형질은 그 윗세대의 형질을 알아야 한다. 코드 #include #include #include using namespace std; string calcBean(int level, int num){ // 몇레벨의 몇번째 개체 if(level == 1){ return "Rr"; }else if(level=..

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121684?language=cpp 문제 내용 각 학생별로 체육 대회 특정 종목에 나갔을 때의 능력치를 담은 2차원 배열이 주어진다. 종목마다 1명의 학생이 나갈 수 있고, 각 학생은 1개의 종목에만 나갈 수 있다. 능력치의 합이 최대가 되는 경우를 구하면 된다. 문제 풀이 각 종목별로 누가 나갈지를 정해야 한다. 이는 백트래킹으로 쉽게 구할 수 있다. 코드 #include #include using namespace std; vector studentOrder; vector used; int ex_num; int student; int mmax=-1; void decideStudent(in..