본문 바로가기

백준288

백준 14888 c++ "연산자 끼워넣기" -PlusUltraCode- https://www.acmicpc.net/problem/14888  [필자 사고]연산자를 끼워넣어 최대값 혹은 최소값을 만들어야 되는 문제이다.현재 N의 값은 최대11이므로 시간복잡도 측면에서 너그럽다. 필자는 DFS를 이용하여 조합알고리즘을 작성하였다. 글로 설명하자면  + - * / 가 있을때 하나하나를 숫자 사이에 배치해 둔다.DFS알고리즘을 이용하면 일단 하나의 문장을 완성하고 마지막 부분만 연산자를 거둔뒤 사용안한 연산자를 넣는 방식으로 코드를 작성하였다. 주의할 점은 DFS의 매개변수를 어떻게 설정하는지가 중요하다. 아래는 필자가 작성한 코드해설이다. 코드 흐름 설명:변수 및 배열 초기화:arr는 입력된 숫자들을 저장하는 배열입니다.buho는 각 연산자의 개수를 저장하는 배열로, 덧셈, 뺄셈.. 2024. 10. 4.
백준 2668 c++ "숫자고르기" -PlusUltraCode- https://www.acmicpc.net/problem/2668  [필자 사고] 처음 방문한 index를 재 방문 했을 경우를 구현할수 있냐 없냐를 묻는 문제이다. 필자는 visited를 int 자료형으로 선언하여 부모index 를 저장하게 구현해났다. 조심해야 될점은 중복 방문 될 수 있으니 set으로 중복을 없애주거나 따로 조건을 추가하여야 된다. 아래는 소스코드 자세한 설명이다. DFS 함수 (깊이 우선 탐색)DFS(int startNum, int parentNum, int count) 함수는 깊이 우선 탐색을 수행하는 핵심 함수입니다.먼저 startNum 노드가 이미 방문된 상태인지 확인합니다.만약 visited[startNum]이 -1이 아니라면, 즉 방문된 상태라면 두 가지 경우로 나뉩니다:.. 2024. 9. 30.
백준 1520 c++ "내리막 길" -PlusUltraCode- https://www.acmicpc.net/problem/1520  [필자 사고]처음 이 문제를 접했을 때 BFS 탐색을 이용했따.다만 visited배열을 이용하게 되면 모든 경로의 탐색을 구할 수 없게 되었다.그래서 visited배열을 빼고 작동시키니 시간초과가 발생했다.N과 M이 각각 500이므로 시간복잡도를 생각해보니500*500*4 와 더불어 계속 새로운 경로가 곱해지니 2초가 넘어가게 된다. 그래서 필자는 DFS탐색을 이용하여 DP count누적을 이용하여 문제를 해결 했따.다음은 소스코드 해설이다. Input() 함수:먼저, 배열의 크기 N x M을 입력받고, 2차원 배열 arr과 방문 여부를 기록하는 visited 배열을 초기화한다.arr는 각 지점의 높이를 저장하는 배열이며, visited.. 2024. 9. 27.
백준 13913 c++ "숨바꼭질 4" -PlusUltraCode- https://www.acmicpc.net/problem/13913   [필자 사고]bfs 탐색을 활용하여 현재위치에서 상대방의 위치까지의 경로를 찾아야 되는 문제이다.현재위치에서 상대방까지 가는 방식은 숨바꼭질 1,2,3 에서 쉽게 알 수 있따.다만 경로를 저장하는건 다른 방식앋. 무식하게 매번 배열을 만들어서 경로를 저장하고 큐에 저장하게 되면 메모리와 시간초과가 나게 된다. 새로 배운 방식은 vistied배열에 값에 자신의 이전 노드를 저장하는 방식이다.vistied[next] = nowIdx; 방식으로 저장하게 되면 어떤 경로로 진행했는지 알 수 있게 된다. 다음은 아래의 코드 해설이다. 1. 입력 처리 및 초기화먼저, 사용자로부터 출발점 N과 목표점 K를 입력받습니다. 그 후, 방문 여부를 저장.. 2024. 9. 26.

티스토리툴바