백준/탐색18 백준 1062 c++ "가르침" -PlusUltraCode- https://www.acmicpc.net/problem/1062 [필자 사고]문제에서 주어지는 특정 글자들은 이미 존재한다.visited를 이용하여 미리 true형태로 해놓고나머지 모든 문자열에 대해서 브루트포스 및 combination 즉 백트래킹을 이용해서 문제를 풀어보자마지막 size가 원하는 K값과 같게 된다면 모든 문자열들을 확인하여 count값을 계산한다. 위와 같이 문제를 풀었다. 아래는 자세한 코드 해설이다.[코드 해설]Input 함수사용자로부터 단어의 개수 N과 가르칠 수 있는 글자 수 K를 입력받는다.N개의 단어를 입력받아 arr 벡터에 저장한다.동시에 myMap이라는 맵에도 해당 단어를 기록하지만, 이 맵은 이후 코드에서 사용되지 않기 때문에 불필요하다.combination 함수백.. 2025. 6. 26. 백준 5427 c++ "불" -PlusUltraCode- https://www.acmicpc.net/problem/5427 [필자 사고]처음에는 매번 currentTime이 갱신되면 불의 위치를 sprayFire()함수를 통해 갱신해젔다. 그런데 시간 초과가 났다. 생각해보니 현재 N,M의 크기가 1000정도가 된다. 매번 1000정도를 하게 되면 시간초과가 날 수 밖에 없다. 방법을 바꿔보자fire관련 된 기록들을 BFS탐색을 이용해 한번에 하게 하고 방문핳 것을 시간 즉 숫자를 기록해 놓으면해당 문제를 타파할 수 있다. 이런 아이디어를 배울 수 있어서 좋은 문제라고 생각한다.[코드 해설]Input()입력을 받고, 초기 상태를 설정하는 함수입니다.맵의 크기 N, M을 입력받고, 맵(arr), 불의 도착 시간(fireTime), 사람 방문 여부(visited.. 2025. 6. 26. 백준 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. 백준 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 다음
