0m1n's Develog

문제 출처 : 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}; 다음으로는 방향을..

문제 출처 : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 컴퓨터과에서 저학년때 배우는 수식.. 이 문제는 중위표기식을 후위표기식으로 고치는 문제이다. 막막할 수 있지만 생각해보면 단순하다. 우선순위와 연산자를 처리해야 하므로 stack에 조건부로 pop, push를 처리해주면 된다. 먼저 문자열을 입력받고 인덱스를 순회하며 경우에 따라 처리한다. 알파벳 대문자인 경우 바로 정답으로 출력한다. (연산자와 관련없음) '(' 인 경우 ..

문제 출처 : https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 처음에 단순 구현으로 생각했으나, 문제를 보면 꼬리를 제거해야 하는 경우도 있고 머리 부분을 추가하는 경우도 있다. 즉 처음과 끝을 push, pop할 수 있어야 했기에 deque을 사용하기로 하였다. 방향 회전시키기 단순 구현이라 특별한 로직같은건 없으나 방향을 90도 회전 시켜야 할 경우에는 다음과 같이 풀이하였다. 인덱스를 접근할 dx, dy 배열을 선언한다. (상 우 하 좌 순..

문제 출처 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 이 문제는 아이디어가 잘 떠오르지 않는 문제였다.. 다른 여러 풀이를 참고했다. 현재 전구를 반복문을 돌린다. i 기준일때 i-1번째까지 정답과 일치하면 넘어간다. 이유는 i+1번째로 기준이 넘어가면 i-1은 더이상 영향을 받지 않기 때문이다. i-1번째가 일치하지 않는다면 스위치를 누른다.(뒤집기) 이 경우를 그냥 시작하는 경우 / 가장 처음에 뒤..

문제 출처 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리(최소 신장 트리) 우선 스패닝 트리는 그래프의 모든 정점을 잇고, 사이클이 없는 트리이다. 정점이 V개면 정점을 연결하는 간선은 V-1개이다. 최소 스패닝 트리는 간선의 가중치 합이 최소가 되는 스패닝 트리이다. 최소 스패닝 트리를 구하는 대표적인 알고리즘은 크루스칼(Kruskal), 프림(Prim) 알고리즘이 있다...