Coding_Test_C++
BaekJoon 1697번: 숨바꼭질
풀이법 1차원 배열과 BFS를 이용하면 문제를 쉽게 풀 수 있었다. 정확한 조건에 대한 이해가 수반되어야 문제를 풀 수 있기에 힌트에 적힌 5-10-9-18-17 부분을 이해하는 것이 중요하다. #include #include #include #include using namespace std; int arr[100001]; bool visited[100001]; int n, k; int minimum=100001; void bfs(int n) { visited[n] = true; queueq; q.push({ n, 0 }); while (!q.empty()) { int now = q.front().first; int count = q.front().second; q.pop(); if (now == k)..
BaekJoon 4179번: 불!
풀이법 BFS를 이용한다면 정답의 실마리를 찾을 수 있는 문제이나, 낮은 정답률이 말해주듯 난이도가 꽤 있는 편이다. 두 번의 bfs를 이용하여, 불이 이동하는 경로를 먼저 구한 후, 지훈이가 이동할 수 있는 경로를 비교하는 방법으로 문제를 해결했다. 해당 문제의 핵심 logic과 검색을 통해 쉽게 구할 수 있는 Hidden TC는 source code 밑에 기술하였다. #include #include #include #include using namespace std; bool visited[1001][1001]; bool visitedF[1001][1001]; char arr[1001][1001]; int ansj[1001][1001]; int ansf[1001][1001]; int vx[4] = {..
BaekJoon 7576번: 토마토
풀이법 BFS를 이용하여 문제를 해결하는 것이 가장 쉽게 문제를 해결할 수 있는 방법이다. countNum 변수를 이용하여 최대 걸리는 시간을 계산한다면 쉽게 해결할 수 있다. #include #include #include using namespace std; int vx[4] = { 1,0,-1,0 }; int vy[4] = {0,-1,0,1}; int arr[1001][1001]; bool visited[1001][1001]; int n, m; int countNum = 0; void bfs() { queue q; for (int i = 1; i > m >> n; for (int i = 1; i arr[i][j]; } } github.com/pearlcrum/CodingTest/tree/main p..
BaekJoon 2178번: 미로 탐색
풀이법 BFS를 이용해서 문제를 해결하였다. 움직일수 있는 count를 queue의 매개변수로 넣어서 계산을 편히 하도록 설계하였다. #include #include #include using namespace std; int vx[4] = { 1,0,-1,0 }; int vy[4] = {0,-1,0,1}; int arr[101][101]; bool visited[101][101]; int n, m; void bfs(int x, int y, int count) { queue q; visited[x][y] = true; q.push({ x,{y,count} }); while (!q.empty()) { int tempx = q.front().first; int tempy = q.front().second.f..
BaekJoon 1926번: 그림
풀이법 BFS를 이용해서 문제를 해결하였다. 기초적인 공식과 같은 풀이 알고리즘을 알고 있다면 어렵지 않게 풀 수 있는 문제이다. (X가 행, Y가 열임을 기억해서 범위를 설정해주는 것이 중요하다) #include #include #include using namespace std; int n, m; int arr[501][501]; bool visited[501][501]; int vx[4] = { 0,1,-1,0 }; int vy[4] = { -1,0,0,1 }; int ea; //그림의 개수 int area;//넓이 void bfs(int i, int j) { ea++; visited[i][j] = true; queue q; int tempArea=0;//비교를 위한 tempea; q.push({ ..
BaekJoon 2193번: 이친수
풀이법 규칙을 구하기 위해 각 항의 개수를 트리 형태로 만들어보았다. 1 1 2 3 5 8 과 같은 규칙을 발견할 수 있었으며, 이는 곧 피보나치 수열에 해당한다. 배열의 크기가 90이상일 수 있으니 꼭 long long형으로 선언해야 한다. #include #include #include using namespace std; int n; long long arr[91]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; arr[1] = 1; arr[2] = 1; for (int i = 3; i
BaekJoon 11659번: 구간 합 구하기 4
풀이법 arr 배열이 100,000까지 있기에 시간 초과를 방지하기 위해서는 DP를 사용해야 한다. 입력과 동시에 모든 배열의 합을 구해서 합의 배열을 만들어두고 arr[j] - arr[i-1]을 이용하면 쉽게 풀 수 있는 문제이다. #include #include #include using namespace std; int n, m; int arr[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; arr[0] = 0; int temp = 0; for (int i = 1; i > a; temp += a; arr[i] = temp; } vector ans; for (int k = 1; k > i >> j; ans.pu..
BaekJoon 1912번: 연속합
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 메모이제이션을 활용하여 현재까지의 최대 합을 구하고 이를 ret이라는 변수에 담아 최대를 반환하게 했다. max(직전까지 최대 합+ 현재 값, 현재 값) #include #include using namespace std; int n; int c[100001]; int d[100001]; int res = -100000000; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i > a; c[i] = a; } d[0] = c[0]; for (int i = 1; i < n; i++) { d[i] ..
BaekJoon 11726번: 2xn 타일링
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 방법만 안다면 쉽게 풀 수 있는 문제이나 정답률이 낮은 이유는 여러 번 시도한 사람이 많아서일 것이다. 1차원 배열을 선언 한 후 규칙을 찾아 보았다. n=1 : 1개 n=2 : 2개 n=3 : 3개 n=4 : 5개 위의 요소를 토대로 규칙을 찾아보니 일종의 계차수열임을 알 수 있었다. 점화식을 구해보니 arr[i]=arr[i-1]+arr[i-2]를 도출할 수 있었다. 10007로 나눈 나머지를 구해야 하므로 최종 점화식은 arr[i] = arr[i-1]%10007 + arr[i-2]%10007 이 된다. 최총 출력 값: arr[n]%10007 #include #include using namespace std; int fix ..
BaekJoon 1149번: RGB거리
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다. 나올 수 있는 경우의 수를 구현하되 DP의 메모이제이션을 활용하여 시간 제한인 0.5초의 벽을 뚫는 것이 핵심이다. arr[i][0] : i번째 집을 빨간색으로 칠하는 비용 arr[i][1] : i번째 집을 초록색으로 칠하는 비용 arr[i][2] : i번째 집을 파란색으로 칠하는 비용 ans[i][0] : i번째 집을 빨간색으로 칠했을 때까지의 최소비용 ans[i][1] : i번째 집을 초록색으로 칠했을 때까지의 최소비용 ans[i][2] : i번째 집을 파란색으로 칠했을 때까지의 최소비용 해당 배열을 이용하여 재귀 식을 만들면 다음과..