문제 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[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 풀이 BFS를 통해 문제를 해결할 수 있었다. 최단 거리 측정이 요구되기 때문에 dist배열을 만들어 각 칸의 도달하는 최단 스텝을 저장해주었다. 또한 문제에서 게임 맵의 행과 열이 주어지지 않기 때문에 따로 행과 열을 구해주었다. BFS를 돌며 벽의 유/무를 확인해주고 dist배열을 통해 최단 거리 및..
문제 https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 백트래킹이란 것은 바로 알아차렸지만 코드도 좀 더러워지고 구현하는데 애를 좀 먹었던 문제이다. 풀이 백트래킹 + 구현 문제이다. '0'인 로또 칸에 대해 갯수를 세고 이를 바탕으로 이미 나온 번호를 제외한 0 ~ 45의 번호들에 대해 조합을 구해주면 된다. 조합을 구한 후에는 정답 로또와 조합을 통해 맞은 로또..
문제 https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 풀이 백트래킹으로 해결할 수 있었다. nums의 모든 요소에 대해 n개 중 3개를 뽑는 조합을 만들어주고 조합이 완성되면 소수 판별 함수를 통해 소수인지 아닌지 판별해주었다. 코드 #include using namespace std; int result = 0; int arr[1001]; bool isused[1001]; bool isP..
문제 https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 풀이 정렬을 통해서 해결할 수 있었던 문제이다. numbers에 들어온 값들을 문자열 백터에 새로 담아주고 compare 조건을 구현해서 정렬해 주고 각 원소들을 더해주면 된다. compare에 a + b > b + a라는 조건을 구현해 주었는데 예를 들어 34, 33를 compare 할 때 ..
