Coding_Test_C++
BaekJoon 3048번: 개미(C++)
https://www.acmicpc.net/problem/3048 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 풀이법 1) 구현(시뮬레이션)을 활용하여 풀 수 있는 문제였다. 2) 첫번째 개미 그룹은 역순으로, 두번째 개미 그룹은 순방향으로 최종 배열 vec에 넣어주었고, 입력받은 time(몇 초 후)를 통해 while 반복을 돌려 주었다. 3) for문을 돌림에 있어 항상 첫번째 인자 부터 돌렸기에 pair를 두어서 두번쨰 인자가 1인 경우 우측으로 이동, 2인 경우 좌측으로 이동하는 것으로 코딩을 진행하였다. 4) 현재 값의 방향과 다음 index의 방향이 같은 경..
BaekJoon 2784번: 가로 세로 퍼즐(C++)
https://www.acmicpc.net/problem/2784 2784번: 가로 세로 퍼즐 6개 단어를 3*3 가로 세로 퍼즐에 놓을 수 없다면 0을 출력한다. 그렇지 않다면, 3개 줄에 퍼즐을 출력한다. 만약 가능한 답이 여러개라면 사전순으로 앞서는 것을 출력한다. 사전순으로 비교를 할 www.acmicpc.net 풀이법 1) 구현과 브루트 포스로 풀어내는 문제였다. 난이도가 높은 문제는 아니었으나, 스스로 너무 문제를 꼬아서 생각하여 오랜 시간이 걸렸다. 2) 행과 열이 들어갈 visited배열을 선언하였고, next_permutation을 활용하여 행을 3개 먼저 추출하는 6C3의 조합을 이용하여 모든 경우의 수를 탐색하였다. 3) 최종 후보들은 모두 string 형태로 담았기에 사전 순으로 s..
BaekJoon 1986번: 체스(C++)
https://www.acmicpc.net/problem/1986 1986번: 체스 첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1= 1 && nextRUY > m; cin >> queenNum; for (int i = 0; i > a >> b; arr[a][b] = 1;//queen qPair.push_back({ a,b }); cnt++; } cin >> knightNum; for (int i = 0; i > a >> b; arr[a][b] = 2;//knight; kPair.push_back({ a,b }); cnt++; } cin >> pawnNum; for (int ..
BaekJoon 1347번: 미로 만들기(C++)
https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 풀이법 1) 구현을 하는 문제이며, 출력에 신경써야 하는 부분이 존재한다. 출력시에 arr[i][j]와 arr[i][j+1] 사이의 공백 없이 출력을 진행해야 정답으로 인정된다. 2) 가장 중요하다고 생각한 부분은 배열의 크기이다. 필자는 arr[101][101]을 두었고, 시작점을 x=50,y=50으로 두었다. 실제 초기 방향이 남쪽인데 50개의 초기 문자열이 모두 'F'인 경우를 고려한다면 ..
BaekJoon 1331번: 나이트 투어(C++)
https://www.acmicpc.net/problem/1331 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 풀이법 1) 배열 자체가 크지 않은 배열이기에, 시간 초과의 걱정 없이 세밀하게 구현을 잘 해낼 수 있는지를 묻는 문제라고 생각한다. 2) 모든 칸을 정확히 한 번만 방문해야 하기에 visited배열을 통해서 방문 여부를 확인했고, 마지막 방문 칸에서 다시 시작점으로 돌아와야 하기에, 시작점은 visited배열에 처음에 넣지 않았다. 3) 나이트가 갈 수 없는 칸일 경우, 바로 Invaild를 써서 ..
BaekJoon 14620번: 꽃길(C++)
https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 풀이법 1) Brute Force로 문제를 해결해 보았다. 실제 들어올 수 있는 배열의 값이 10x10이기에 시간 제한 2초 내에 가능할 것이라 생각하였다. 2) dp 배열을 생성하여, (0,0)부터 (n-1,n-1)까지의 배열 중 값이 들어갈 수 있는 범위인 (1,1)부터 (n-2,n-2) 범위에서 각 index에 들어갈 수 있는 꽃이 있다고 가정 시에, 대지 임대료를 각각 계산해 주었다. 3..
BaekJoon 2302번: 극장 좌석(C++)
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이법 1) 전형적인 DP 문제로, 피보나치를 활용하여 푸는 문제이다. [ ] [ ] [ ] [VIP] [ ] [ ] {VIP] [ ] [ ] 위와 같은 형식의 배열이 있다면, VIP 좌석은 움직일 수 없기에, [ ] 이 연속되는 수를 구하여, 경우의 수를 구해주면 되는 문제였다. 자유롭게 움직일 수 있는 칸의 개수를 확인한다음 미리 만들어진 dp배열의 값을 불러오는 것이 중요할 것이다. dp 배열의 규칙은 ..
BaekJoon 1965번: 상자 넣기(C++)
https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이법 1) 전형적인 DP 문제로, 이전의 값 중 자기 보다 작은 값 중 현재 dp배열의 값이 가장 큰 값+1을 자신의 dp 값으로 가져가면 되는 문제이다. 2) 초기 dp배열을 1로 만들어 주어야 한다는 점이 중요하다. 5 4 5 1 2 3 dp를 처음에 0으로 초기화 하게되면 1 2 0 1 2 라는 dp 배열이 나와서 오류가 나게 된다. 고로 dp 배열을 처음에 1로 초기화 하는 것이 매우 중요하다. ..
BaekJoon 1890번: 점프(C++)
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이법 1) 얼핏 보면 경로의 개수를 세면 되니 방문한 곳을 세지 않고 반복하는 dfs를 사용하면 되는 문제처럼 보이나 dfs를 사용하게 된다면, 시간 초과가 발생한다. 2) 마찬가지로 bfs를 사용하게 되면 메모리 초과가 나서 문제를 해결 할 수 없다. 모든 map이 1로 가득 차 있는 경우 경우의 수가 너무 많아지기 때문이다. 3) 문제를 해결함에 있어 2차원 dp 배열을 만들어서 ..
BaekJoon 2294번: 동전 2(C++)
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이법 1) DP를 활용하여 문제를 풀어보았다. arr라는 DP의 값이 들어갈 배열을 만들었으며, 사용 가능한 동전을 cases라는 vector에 담았다. 2) 각 동전 별로 나올 수 있는 최소의 수를 만들기 위해 algorithm 헤더의 min을 활용하였고, 초기 값으로 dp의 모든 배열을 큰 수(INF)로 설정하였다. for (int i = 0; i < cases..