0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 이 문제는 덱을 사용하는 문제이다. 2번 방법(왼쪽으로), 3번 방법(오른쪽으로) 중 짧은 거리를 구해서 해당 방법대로 push, pop을 반복한다. 이때 주의할 점은, left < right 인 경우 이동횟수가 +1이므로 최종 cnt에 1을 더해주어야 한다. 코드 #include #include #include using namespace std; int N, M; int..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 압축한 문자열 중 가장 짧은 길이를 찾는 문제이다. 중요한점은 가장 짧은 것의 길이를 리턴해야 한다! 1단위부터 문자열 길이의 절반까지 압축 단위를 잡자. 그 이유는 절반 이상은 압축이 불가능하기 때문이다. a는 비교할 문자열이고, temp는 압축 단위에서 압축된 문자열 이다. (aabbaccc 에서 단위가 1이라면 -> 2a2baccc) for문을 한번 더 순회하며 일치하는 ..

문제 출처 : https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > N >> M; for(int i = 0; i > a >> b; graph[a].push_back(b); graph[b].push_back(a); } bfs(); cout

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 연결되어 있는 네트워크의 개수를 찾는 문제이다. 하나의 네트워크를 끝까지 하나씩 탐색하므로 dfs를 활용하자! 1. main 처음 컴퓨터 개수만큼 반복하며 방문하지 않은 경우 dfs를 실행하며 정답 카운터를 1 증가시킨다. 2. dfs 방문한 노드를 true처리한 후, for문을 돌아 연결되어 있는 경우(computers[idx][i]) && 방문하지 않은 경우(!visit[i..

문제 출처 : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 어떻게 이분탐색을 돌려야할지 고민이 되는 문제이다. 중요한 부분은, A와 B의 누적합을 미리 저장해두는 것이다. 누적 합 A, B 배열에서 모든 부 배열의 누적합을 저장한다. vector aSum, bSum; for (int i = 0; i < N; i++) { int sum = A[i]; aSum..

문제 출처 : https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 조건과 같은 친구 관계가 있는지 구하는 문제이다. DFS로 친구를 찾아가고 중간에 기존에 있었던 친구가 나오면 탐색을 중단하는 백트래킹을 사용하면 된다. 친구 추가 a,b가 입력됐을때 a와 b는 서로 친구이므로 a, b 모두 친구 리스트에 push 해준다. vector v[2001]; vector check(2001, false); for(int i = 0; i > a >> b; v[a].push_back(b); v[b].push_bac..

문제 출처 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 https://www.acmicpc.net/problem/1149 의 응용 문제이다. 기존 문제는 마지막 N번집에서 1번집 고려를 하지 않았지만 이번에는 고려해야 한다. 마지막 집 -> 첫 집 결국 마지막에서 첫 집을 고려해야 하기에, rgb 반복문을 돌려 첫 집을 어디로 선택할지 순회하며 계산하면 된다. for(int rgb = 0; rgb > a..

문제 출처 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 입력한 구간이 팰린드롬인지 확인하는 문제이다! 시간 제한에서 dp로 풀어야 한다는 것을 알았다. 어떻게 하면 dp로 풀 수 있을까? 먼저 dp 배열을 하나 선언한다. (기본 false) bool dp[2001][2001]; 해당 배열에서 dp[i][j]는 i번째 수부터 j번째 까지 팰린드롬인지 여부를 나타난다. S, E가 같은 경우 ex) 1 이 경우는 팰린드롬이다! => 따라서 dp[i][i]는 true이다. S,..

문제 출처 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 미세먼지는 동시에 네 방향으로 확산하고 공기청정기는 미세먼지를 밀어내는 시뮬레이션이다. 여기서 핵심은 동시에 확산한다는 것이다. 이 부분을 못봐서 헤맸었다.... 두번째는 공기청정기 위, 아래에 따라 밀어내는 방향이 다르다. 미세먼지 동시 확산 동시에 확산하는 것을 구하려면 어떻게 해야 할까? 바로 추후 한 번에 추가할 배열을 따로 선언하고, 거기에 각 계산 결과를 넣어두었다..

문제 출처 : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 방향에 따른 경우의 수를 모두 찾아 정답을 구하는 브루트포스 문제이다. 그러나 1,2,3,4,5번의 방향과 개수가 각각 달라 어떻게 시뮬레이션을 돌려야 할지 고민했다. 방향 시뮬레이션 우선 상하좌우 인덱스 dx, dy를 선언한다. int dx[4] = {0, -1, 0, 1}; // 우, 상, 좌, 하 int dy[4] = {1, 0, -1, 0}; 다음으로는 방향을..