Coding_Test_C++
BaekJoon 9205번: 맥주 마시면서 걸어가기(C++)
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이법 1) DFS를 이용하여 푼다면 쉽게 풀 수 있는 문제이다. 2) 절댓값의 값이 1000이하인지를 확인하여, 중간에 편의점을 들릴 수 있는지 확인하는 것이 중요하다. #include #include #include #include #include #include #include #include #include using namespace std; int t; int pantaX, pan..
BaekJoon 1706번: 크로스워드(C++)
https://www.acmicpc.net/problem/1706 1706번: 크로스워드 동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 www.acmicpc.net 풀이법 1) 문자열 처리를 위해 여러번 반복을 한다면 풀 수 있는 문제이다. 2) 배열에서 #이 나오는 경우 크기가 2이상이면 결과값의 후보인 vec 배열에 넣어준다. 3) 배열에서 #이 나오는 경우 크기가 2미만이면 기존에 string 값을 초기화 시킨다. 4) 배열에서 #이 나오지 않으면, string에 값을 추가한다. 5) 배열에서 #이 나오지 않았으며, 마지막 행 혹은 열을 탐색 시 if (..
BaekJoon 7785번: 회사에 있는 사람(C++)
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 풀이법 1) C++의 장점인 STL을 활용하였다. 2) map을 활용한다면 쉽게 풀 수 있다. 중복이 불가능하다는 점을 이용하여 map 객체에 값을 넣어둔다. 3) auto로 반복하여, 역순으로 출력하기 위해서 rbegin() 과 rend()를 사용하였다. #include #include #include #include #include #include #in..
BaekJoon 1302번: 베스트셀러
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이법 1) C++의 장점인 STL을 활용하였다. 2) map을 활용한다면 쉽게 풀 수 있다. auto로 반복하여, 최대 값을 찾고 해당하는 값을 출력하면 되는 문제이다. #include #include #include #include #include #include #include using namespace std; int n; map m; int cnt; int main() { ios..
BaekJoon 16953번: A->B(C++)
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이법 1) BFS를 활용하면 풀 수 있는 문제이다. 2) visited 배열을 사용하게 되면 memory 초과가 발생할 수 있기에 사용하지 않고 문제를 풀었다. 3) 최대 값을 1000000000로 정의하고 queue에 넣을 조건을 꼼꼼하게 설정하였다. #include #include #include #include #include #include #include #include using namespace std; #define MAXNUM 1000000000 int a, b; int ans = 0; void bfs(..
BaekJoon 10825번: 국영수(C++)
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이법 1) C++의 강점인 STL과 algorithm 헤더 내의 sort 함수를 이용하면 풀 수 있는 문제이다. 2) 조건을 compare 라는 bool type의 함수를 만들고 설정하는 과정이 가장 중요하다. 3) 팁을 적어 보자면 감소(내림차순: >) / 증가(오름차순: b.second.first) return true; else if (a.second.first == ..
BaekJoon 11123번: 양 한마리... 양 두마리...(C++)
https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 풀이법 1) BFS를 활용하여 나올 수 있는 묶음의 수를 문제이다. 2) 겹치지 않게 visit 배열을 활용하여 겹치지 않게 처리하면 풀 수 있다. 3) test case가 여러 개이므로 visited 배열을 초기화 하는 작업이 중요하다. #include #include #include #include #include #include #include #include using ..
BaekJoon 2210번: 숫자판 점프
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이법 1) DFS를 활용하여 나올 수 있는 숫자의 합을 구하는 문제이다. 2) 겹치지 않게 visit 배열을 활용하여 겹치지 않게 처리하면 풀 수 있다. 3) 재귀와 stack을 활용할 수 있으나, stack으로 문제를 풀어보았다. #include #include #include #include #include #include #include #incl..
BaekJoon 10026번: 적록색약(C++)
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이법 1) BFS를 활용하여 몇 개의 덩어리가 존재하는지 묻는 문제이다. 2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다. 3) 총 두번이 반복 되어야 하니 visit 배열은 초기화 시켜야 한다. 4) 두 번째에 적록 색약이신 분들을 위해 R과G 가 인접한 부분은 G->R로 바꾸는 방식으로 문제를 해결했다 (for문을 활용하는 것 보다..
BaekJoon 10451번: 순열 사이클(C++)
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이법 1) DFS를 활용하여 최소를 구하는 문제이다. 2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다. 3) stack을 활용하여 dfs를 구현하였으며, 다음의 노드가 이미 방문되었다면 cycle이 있는 것이다. 4) cycle로 새로운 값을 넣을 때는 for문을 활용하..