C++

14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 과정 더 쉽게 풀 수 있는 방법이 있을거 같지만 시간을 재고 푸는 바람에 하드 구현을 했던거 같다.. 방향 값이 입력 받을 때마다 먼저 주사위를 이동시켜서 바깥으로 이동할 경우는 제외시켰다. 안쪽으로 이동할 경우 rotation 함수를 실행 시키는데 해당 함수는 방향과 이동된 좌표(주사위 입장에서는 바닥)를 넘겨 주었다. 그 이후에는 간단하게 구현하는 방법이 생각나지 않아서 주사위의 배열 값을..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 과정 - 모든 노드들은 ABCDE 친구 관계가 성립하는지 그래프 탐색을 한다. - 방문한적이 없는 노드는 해당 DFS로 탐색하고 깊이를 1 증가 시킨다. 깊이가 총 5번이면 관계가 성립 되었기에 ans 값을 true로 설정하고 return 해준다. - dfs로 탐색이 끝났는데 ans 값이 false 면 해당 탐색했던 노드는 다시 방문 표시를 false로 설정한다. #include #include #include using namespace std; int n,m; map friends; vector visited; bool ans = false; void dfs(..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 - 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓으면, 그 퀸과 같은 가로, 세로, 대각선에는 또 다른 퀸을 놓을 수 없다. - 해당 문제는 dfs의 재귀 호출로 해결하였으며, 2차원 배열과 1차원 배열 두 가지로 해결을 하였다. 1차원 배열을 사용하는 게 미숙하여 다른 블로거님들의 풀이를 보면서 이해하면 문제를 풀었고 혼자 풀 때는 1차원 배열을 풀어야겠다는 생각을 못하여 2차원 배열로 해결하였다. - 0번째 행부터 각 행에 대해 각각 ..

코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr N * M 행렬에서 최단 거리를 보장해주는 탐색 알고리즘인 BFS를 사용하였다. 단순히 N*M의 범위를 넘지 않고 벽이 아닌 곧이 있을 경우 해당 값을 큐에 삽입 후 좌표의 값을 1 증가시켰다. 최종적으로 반환 값은 N*M 좌표의 값을 반환시켰다. 하지만 해당 값이 1인 경우 모든 벽에 둘러 쌓여서 탐색을 하지 못한 경우이기에 -1 값을 반환하도록 설정하였다. #include #include using na..

> lang >> job >> level >> food >> score; vs[0][0] = lang; vs[1][0] = job; vs[2][0] = level; vs[3][0] = food; for(int i=0 ; i lang >> temp >> job >> temp >> level >> temp >> food >> score; string s = lang + job + level + food; auto itr = lower_bound(info_[s].begin(),info_[s].end(),stoi(score)); answer[index++] = info_[s].size() - (itr - info_[s].begin()); } return answer; }

코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 시작 지점에서 -> 도착 지점까지의 최소 비용을 탐색해야하기 때문에 플로이드-와샬 알고리즘을 사용해야 한다. 2차원 배열을 만들고 해당 값들을 큰 값으로 저장 시킨다. 여기서 주의해야할..

코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 카드의 수가 6장으로 제한되어 있다. 그렇기에 카드 숫자에 따른 순열 조합으로 가장 최단 거리를 조사했다. 먼저 board에 있는 카드의 숫자를 card 벡터에 저장하여, 중복된 숫자는 제거하고 next_permutation으로 bfs 탐색을 한다. bfs로 카드를 탐색하기 전에 각 순열마다 최소 거리를 구해야하기 때문에 순열이 돌때마다 board와 r, c 값은 항상 새로운 인자에 초기화 시켜준다. bfs 함수에 들어가면 방문함수와 queue를 생성했다. queu..

코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr #include #include #include #include using namespace std; vector dp(360000,0); string solution(string play_time, string adv_time, vector logs) { string answer = ""; int start_hh,start_mm,start_ss , end_hh,end_mm,end_ss,st..