Coding_Test_C++
BaekJoon 1062번: 가르침(C++)
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이법 1) 들어온 문자열을 전처리하지 않고 바로 백트래킹을 실시 했을 때 바로 시간 초과가 났던 문제이다. 2) 알파벳 소문자만 입력 값으로 들어오므로 넣을 수 어떤 것이 현재 들어온 것들인지 표기 하기 위해 26개짜리 visited 배열을 만든 후 a,n,t,c,i를 미리 넣어 주었다. 3) 이후 들어온 값들은 "anta"로 시작하고 "tica"로 끝나므로 이 부분들을 substring..
BaekJoon 1939번: 중량제한(C++)
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이법 1) 단순 bfs로 문제를 풀고자 했더니 문제가 많이 생겼어서, 검색을 해서 풀어낸 문제이다. 2) 이분 탐색과 함께 bfs를 이용해서 풀 수 있는 문제였기에 공식처럼 bfs 문제를 풀던 것을 반성할 수 있는 문제였다. 3) 이분 탐색을 통해 나온 mid 값 이상인 무게를 지닌 트럭이, 시작점부터 종착점까지 갈 수 있는지를 bool..
BaekJoon 16987번: 계란으로 계란치기(C++)
https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이법 1) 백트래킹과 구현이 합쳐진 문제로서 해결함에 있어 시간이 오래걸렸다. (일단 문제에 필요 없는 tmi가 너무 많았다 ㅠㅠ) 2) 왼쪽부터 차례대로 탐색한다는 것이 가장 중요했으며, 구현을 위해 현재 계란의 내구도가 0보다 작을 경우, 깰 수 있는 다른 계란이 남지 않았을 경우를 if문으로 명시하였다. 3) 서로의 무게로 계란을 깬 이후 깨진 계란 만큼 수를 추가시켜 주었고..
BaekJoon 1941번: 소문난 칠공주(C++)
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이법 1) 백트래킹과 BFS를 섞어야지만 풀 수 있는 문제이다. 2) 기존의 2차원 배열에서 DFS 형식으로는 십자가 형태의 값들을 체크할 수 없기에 1차원 배열로 만든 백 트래킹과 인접한 행렬임을 확인하기 위한 BFS를 활용하였다. 3) 7명을 백트래킹으로 선정한 이후, 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 다음과 같은..
BaekJoon 1759번: 암호 만들기(C++)
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이법 1) 백트래킹을 활용해서 해결할 수 있는 문제였다. 초기에 들어 오는 값을 sort하여 오름차순으로 만드는 작업이 필수적이다. 2) 이후 백트래킹을 활용하여 원하는 길이의 배열이 만들어 졌을 때, 모음의 개수가 1개 이상인지, 자음이 2개 이상인지 확인하여 출력을 진행하면 된다. 3) 출력 형식 때문에 틀렸습니다가 떠서 놀랬었던 문제이다. 꼭 문제를 제대로 읽도록 하자 #include #incl..
BaekJoon 6603번: 로또(C++)
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이법 1) 전형적인 백트래킹 문제였다. 2) 현재 값 보다 큰 index를 이용해서 경우의 수를 탐색했으며, cnt가 6에 도달하게 되면 현재까지의 값을 출력하는 방식으로 문제를 해결할 수 있었다. 3) 재귀와 백트래킹이 익숙하지 않은 분들은 소스코드를 보며 이해하심을 추천드린다. #include #include #include #include #include #include usin..
BaekJoon 1182번: 부분수열의 합(C++)
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이법 1) 백트래킹을 활용해서 해결할 수 있는 문제였다. 2) 현재 값 보다 큰 index를 이용해서 경우의 수를 탐색했으며, 원하던 s값과 현재의 sum 값이 같은 경우 결과값을 증가시켰고, 조건 처리를 통해서 모든 경우의 수를 탐색하였다. #include #include #include #include #include #include using namesp..
BaekJoon 3190번: 뱀(C++)
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이법 1) queue를 사용했지만 사실상 deque를 이용해서 푼 문제이다. 2) arr에 사과가 존재하는 위치를 담아 주었고, visited 배열에 현재 뱀이 위치하는 것을 표시하였다. 3) queue 안에는 현재 x값, y 값, 시간 초, 방향, 방향전환을 위해 확인해야할 vec 배열과의 비교 index를 담아 주었다. 4) 사과를 만나지 않은 경우는 단순히 구현으로 풀 수 있는 문제이다. 허나 뱀..
BaekJoon 2473번: 세 용액(C++)
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이법 1) 투 포인터를 활용하여 탐색을 진행했으며, 조건을 설정하여 문제를 해결하였다. 2) 투 포인터를 활용하기 위해 처음에 들어온 배열을 정렬하였다. 3) 기준이 될 용액을 잡기 위해 for문을 모든 index에 활용하였으며, 해당 index보다 하나 큰 것을 left, 배열의 마지막 index를 right를 두고, 세 용액의 최소 합을 구하려 노력하였다. -> [ind..
Programmers Level 2: 구명보트(C++)
https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이법 1) Greedy 방식을 사용해서 해결하는 문제였다. 2) 사람들의 무게인 people 배열을 오름차순으로 정렬 후, 가장 몸무게가 많이 나가는 사람 부터 보트에 태웠다. 이후 몸무게가 다음으로 많이 나가는 사람이 보트에 들어갈 수 있으면 반복하며 태워주었고, 불 가능할 경우 가장 가벼운 사람, 그 다음으로 가벼운 사람을 넣는 ..