coding tasty house

AC 문제 설명 AC라는 언어에 R, D 두가지 함수가 존재한다. R은 뒤집기, D는 첫 번째 숫자를 지운다. 이때 입력으로는 테스트 케이스 수 (T)가 주어지고, 숫자의 수, 배열 [x1,x2,...]이 주어진다. 각각 함수 실행 결과를 출력 시킨다. 이때 배열에 숫자가 없는데 D를 실행시키면 error를 출력시킨다. 알고리즘 필요한 입력들을 받고, 배열을 deque에 넣어준다. 이때 배열에 넣을 때 숫자의 범위는 1부터 100까지인 것을 감안하고 처리하여 넣는다. R과 D를 차례차례 읽어서 실행한다. R의 경우 반복문 내에서 실행하면 시간초과가 발생하므로 bool type flag를 not을 사용하여 처리한다. D의 경우 deque의 비어있는지 여부를 확인하고 비어있는 경우 error를 출력한다. 비..

제로 문제설명 단순히 0이 들어오면 가장 최근에 입력되었던 수를 뺴고 그렇지 않으면 저장한 뒤, 전체 수의 합을 출력하는 문제이다. 알고리즘 입력된 수가 0이면 stack 에서 top을 지운다. 입력된 수가 1이면 stack 에 넣는다. #include #include #include using namespace std; int main() { int K; cin >> K; stack s; int x; for (int i = 0; i > x; if (x == 0) s.pop(); else s.push(x); } int sum = 0; for (int i = 0; s.size(); i++) { sum += s.top(); s.pop(); } cout 나중에 온 것이 가장 먼저..

토마토 문제설명 첫 줄에 가로 M , 세로 N 그리고 각각의 가로 세로에 맞춰 0,1,-1의 입력이 각각 주어진다. 이때 0은 익지 않은 토마토, 1은 익은 토마토, -1은 토마토가 없는 상태를 의미한다. 토마토 1개가 익어있으면 상하좌우 방향의 토마토는 다음날 익는다. 그리고 대각선은 익지 않는다. 모든 토마토가 익는데 걸리는 날짜를 구한다. 만약 토마토가 전부 익을 수 없다면 -1을 출력 시킨다. 이미 익어있는 상태면 0을 출력한다. 알고리즘 입력 받는 즉시 1이 들어오면 queue 에 담아 놓는다 -> 이는 익어있는 토마토가 모두 다른 토마토에 영향을 끼치게 하기 위함이다. bfs함수를 실행한다. visited 배열을 조회 하는데, 최대 값이 모든 토마토가 익는데 걸린 기간이라고 간주 할 수 있다...

A와 B 문제 설명 시작하는 문자열 S와 만들고자 하는 문자열 T를 입력 받은 뒤, 규칙을 지켜서 T로 만들 수 있으면 1을 출력하고 그렇지 않으면 S를 출력한다. 그 규칙은 다음과 같다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 알고리즘 S와 T를 입력 받는다. 반복문을 통해서 T를 맨 뒤 글자부터 확인한다. 맨뒤가 A인 경우 맨 뒤 한 글자를 지운다. 맨뒤가 B인 경우 맨 뒤 한 글자를 지우고 뒤집는다. 반복문에서 S의 길이와 T의 길이가 같은 경우 반복을 멈춘다. S와 T를 비교해서 같으면 1 다르면 0을 출력시킨다. 정답 코드 #include #include #include #include using namespace std; int main() { string S, T..

벽 부수고 이동하기 문제 설명 N,M의 값을 입력받고 0일때는 이동이 가능하다. 1인경우 벽이기 때문에 이동할 수 없다. 하지만 단 한번 벽을 부수고 이동하는 것이 가능하다. 최적 이동경로를 구하도록 하자. 알고리즘 입력 값을 모두 입력 받은 뒤 (0,0)에서 시작하고 벽을 뚫을 수 있는 지 여부를 나타내기위해 visited에 배열을 한 차원 추가한다. BFS 알고리즘을 사용하여 현재 그래프가 0이고 방문하지 않은 경우는 접근이 가능하다. 그래프가 1이고 현재 block이라는 변수가 1일때는 벽을 부수고 방문하는 것이 가능하다. 이때 값을 계산할 때 한 번 부쉈기 때문에 1을 0으로 바꾸어 준다. 이동 할 수 없는 경우 -1을 반환한다. #include #include #include #include #..

미로 탐색문제 설명첫 입력 값으로 N,M을 입력 받는데 각각 미로의 가로와 세로 값이 된다.다음 줄에는 0,1로 붙어서 현재 칸을 방문 할 수 있는지의 여부로 입력된다.(1,1)에서 시작해서 (N,M)에 도달하기 까지의 최적 경로를 구해 출력시킨다.알고리즘먼저 N,M을 입력받고 각각 0,1을 이어서 입력 받는다.bfs함수로 시작위치인 (0,0)을 전달한다.queue에 pair형태로 x,y좌표를 넣고 visited를 활용하여 방문했다는 의미인 1을 대입한다.queue가 빌때까지 반복하는데, 각각 queue에서 front값(x,y) 즉, 현재 위치를 꺼낸다.상하좌우 이동한 좌표값을 계산해보고 이동가능하고 방문이 가능한 경우 방문한다.방문시 visited 를 이용하여 현재 값에서 +1해서 최종 값에 최소 이동..

동전 0 문제설명 첫 줄에 N,K를 입력 받고 N은 동전의 종류 수 이고, K는 맞추는 금액이다. 최소한의 동전으로 금액을 구성하여 필요한 동전 수의 최소 값을 출력시킨다. 알고리즘 필요한 값들을 입력 받는다. 최대한 빨리 찾기 위해서 오름차순으로 정렬된 동전들을 뒤 부터 조회한다. 금액 K를 동전으로 나누어서 sum에 몫을 저장한다. 나머지를 K에 다시 대입한다. 반복문을 통해서 최소한의 동전을 구한다. #include #include using namespace std; int arr[11]; int main() { int n,k,cnt=0; cin >> n >> k; for (int i = 0; i > arr[i]; for (int i = n-1; n>=0 ; i--) {..

바이러스 문제설명 첫 줄(node)에 컴퓨터의 수, 두 번째 줄(num)에 간선의 수가 주어진다. 그리고 연결관계를 입력 받은 뒤, 1번 컴퓨터부터 시작해서 바이러스에 감염된 컴퓨터의 수를 출력시키는 문제이다. 알고리즘 설명 input을 입력받는다. 연결관계를 2차원 배열에 graph[x][y]=1, graph[y][x]=1에 각각 넣어준다. dfs 함수에서 현재 방문 노드를 매개변수로 받고 반복문을 1부터 노드의 수까지 반복하여 연결된 노드를 찾아 재귀적으로 방문한다. 방문할 때 바이러스에 감염된 컴퓨터의 수도 같이 세어준다. #include #include #include #include using namespace std; #define MAX 101 int graph[MAX][MAX]; bool ..

단지번호 붙이기 문제설명 첫 줄에 주어지는 입력은 지도의 크기(5 node; vector v; for (int i = 0; i > x; for (int j = 0; j < node; j++) graph[i][j] = x[j]-'0'; } for (int i = 0; i < node; i++) { for (int j = 0; j < node; j++) { if (graph[i][j] == 1 && visited[i][j] == 0)//방문 가능한 노드로 재귀 { DFS(i, j); all++;//전체 단지수 측정 v.push_back(cal); } cal = 0;//단지당 집 수 초기화 } } cout

유기농 배추 (DFS) 문제설명 dfs알고리즘을 사용한 문제로 노드간의 연결된 관계를 파악하여 그 갯수를 세는 문제이다. 알고리즘 순서 테스트케이스(T)와 밭의 가로세로 크기(M,N), 간선의 갯수(K)를 입력 받는다. 연결관계를 2차원 graph에 1로 표현한다. 예) 2,3 -> graph[2][3]=1 graph를 반복해서 연결관계가 1이고 현재 방문하지 않은 노드를 방문한다. dfs함수에서 방문했다는 visited[x][y]=1 표현으로 방문 여부를 체크하고 현재 노드에서 상,하,좌,우 연결관계를 재귀적으로 확인한다. 재귀적인 확인을 마친뒤 다시 main 함수로 돌아오면 answer값을 증가시킨다. 여러번 테스트를 위해서 vector에 값을 담아 놓았다. #include #include #incl..