백준290 백준 2580 c++ "스도쿠" -PlusUltraCode- https://www.acmicpc.net/problem/2580 [필자 사고]처음에 어떻게 해야 문제를 해결할지 고민했따. 일단 나는 스도쿠를 할때면 먼저 가로나 세로 네모칸에 없는 숫자들을 생각하곤 한다.맞다 이게 이 문제의 핵심 포인트다.visited배열을 이용하여 사용되지 않는 숫자들을 체크한뒤 백트레킹으로 문제를 해결하면 된다. 아래는 자세한 코드 해설이다.[코드 해설]1. Input 함수스도쿠 보드를 입력받는 함수이다.9×9 크기의 2차원 배열을 생성하고, 사용자로부터 한 줄씩 값을 입력받는다.입력값이 0인 경우, 즉 비어 있는 칸은 따로 emptyArr라는 벡터에 해당 좌표를 저장한다.이렇게 하면 나중에 백트래킹 탐색 시 빈 칸만 대상으로 재귀 호출을 할 수 있어 효율적으로 탐색이 가능하다... 2025. 6. 16. 백준 1987 c++ "알파벳" -PlusUltraCode- https://www.acmicpc.net/problem/1987 [필자 사고]백트레킹 문제이다.처음에는 BFS문제로 인식하고 풀다가 이러면 최대거리로 가는 경로가 만들어지지 않게 된다.즉 백트래킹 문제로 최대로 가는 거리를 찾아야 된다. 교육 문제로 좋은거 같다. 아래는 자세한 코드 해설이다.[코드 해설]1. Input 함수이 함수는 전체 프로그램에서 입력을 담당한다.사용자로부터 격자의 크기 N과 M을 입력받고, N개의 줄에 걸쳐 M개의 알파벳으로 이루어진 문자열들을 입력받아 2차원 문자 배열 형태로 저장한다.또한, 알파벳의 방문 여부를 판단하기 위한 visited 배열의 크기를 27로 설정하고 초기화한다. (실제로는 A~Z까지만 사용되므로 26으로 해도 충분하다.)2. isInside 함수이 함수는 .. 2025. 6. 16. 백준 1351 c++ "무한 수열" -PlusUltraCode- https://www.acmicpc.net/problem/1351 [필자 사고]문제에서 N의 범위가 10^12승이다 일반적인 방법으로 배열을 선언시 시간초과가 난다. 그렇다면 맵이나 set을 이용해서 원하는 값만 넣고 값을 찾느 ㄴ형태로 구현해야 된다는 사고과정이 흘렀다.또한 저 값들을 N에서 부터 시작하여 백트래킹 즉 탑 다운 방식으로 문제를 해결할 수 있따는 아이디어도 떠올려 졌다. 위 두 가지 사고과정이 생기게 되면 해당 문제를 타파할 수 있따.아래는 자세한 코드해설이다.[코드 해설] DFS 함수:이 함수는 idx라는 인덱스를 받아 재귀적으로 값을 계산합니다.만약 idx가 0이라면, 값이 1로 설정되고 종료됩니다.myMap[idx]가 이미 계산되어 있으면 재귀 호출을 하지 않고 값을 반환합니다. 이.. 2025. 6. 11. 백준 1038 c++ "감소하는 수" -PlusUltraCode- https://www.acmicpc.net/problem/1038 [필자 사고]문제를 보고 시간복잡도를 생각했다. dfs를 이용하면 모든 수를 시간안에 완료할 수 있을 지 ..일의 자리 수부터 시작하여 마지막 digit을 관리하면서 dfs로 다음 수로 나아가게 되면 N의 최대가 1000000이기 때문에 1억을 넘지 않으므로 충분히 시간복잡도가 널널하다. 좋다 이방법으로 가보자 하는 식으로 문제를 해결했다. [코드 해설]Input() 함수사용자로부터 정수 N을 입력받는다.N은 "N번째 감소하는 수"를 구하기 위한 목표 인덱스이다.dfs(long long number, int last_digit) 함수감소하는 수를 재귀적으로 생성하는 백트래킹 함수이다.number는 현재까지 만든 감소하는 수이며,last_d.. 2025. 6. 10. 이전 1 2 3 4 5 6 ··· 73 다음
