본문 바로가기

백준189

백준 2357 c++ "최솟값과 최댓값" -PlusUltraCode- https://www.acmicpc.net/problem/2357 [필자 사고]이 문제를 처음 봤을 때 부르스트 알고리즘을 적용하려 했지만 범위를 보고 그만두었다.다음으로 누적합을 이용하면 뭐 달라질까?? 생각했지만 에초에 최솟값과 최댓값이라 상관이 없었따.처음으로 배운 세그먼트트리를 이용해야 된다. 세그먼트 트리는 초기값을 잘 설정하면 그 이후부터는 쉽게 풀 수 있따.시간복잡도가 logN 이라 시간내에 풀 수 있다.아래는 코드 해설이다.[코드 해설] Input 함수배열 크기(N)와 질의 수(M)를 입력받습니다.배열 arr를 초기화하고, 데이터를 입력받아 저장합니다.Init_Segment_Tree 함수세그먼트 트리를 초기화합니다:treeHeight: 배열의 크기(N)에 대한 로그 값으로 세그먼트 트리의 .. 2025. 1. 5.
백준 1194 c++ "달이 차오른다, 가자." -PlusUltraCode- https://www.acmicpc.net/problem/1194 [필자 사고]기본적인 탐색 알고리즘을 이용하여 푸는 문제이다.이 문제만의 특이한 점은 비트마스킹 즉 현재 키를 가지고 있으면 on/off 를 수행하게 해주는 비트마스킹을 이용해야 된다는 점이다.또한 이 문제를 풀면서 배운점은 visited를 2차원 배열로 선언하게 되면 방문했떤 지점을 어떻게 초기화 시킬지 고민이였는데 3차원 배열로 선언하여 추가된 인덱스의 범위를 1[코드 해설] Input 함수Input 함수는 미로의 크기(N, M)와 미로 데이터를 입력받습니다.미로는 vector> 형태의 2차원 배열로 저장됩니다.입력 도중 시작 위치(0)를 찾아 변수 originX와 originY에 저장합니다.visited 배열은 특정 위치와 열쇠 상태.. 2025. 1. 5.
백준 9935번 c++ "문자열 폭발" -PlusUltraCode- https://www.acmicpc.net/problem/9935 [필자 사고]처음에 필자는 string 내장함수인 find 와 erase를 사용하여 문제를 해결했지만 시간초과가 발생했다.찾아보니 erase의 시간복잡도가 최악일경우 O(n^2) 이 발생할 수도 있기 때문이다.그래서 stack을 이용하여 폭파시킬 bomb 문자열이 들어가 있으면 스택에서 지우는 형식으로 방향을 바꿨다.필자가 실수한 점은 string temp; 변수를 초기화 시키지 않고 계속 사용하여 메모리초과가 발생했다. ㅇㅏ래는 소스코드 해설이다.[코드 해설] 문자열 str과 폭발 문자열 bomb을 입력받는다.사용자로부터 문자열 str과 폭발 문자열 bomb을 입력받아, 이후 문자열 처리에 사용할 준비를 한다.스택을 사용하여 문자열을 처.. 2025. 1. 4.
백준 2493 c++ "탑" -PlusUltraCode- https://www.acmicpc.net/problem/2493  [필자 사고]대표적인 스택 자료구조를 묻는 알고리즘이다. 필자는 알고리즘 전공 수업 때 스택관련 자료구조를 설명해주실 때 위와 비슷한 문제를 들어 설명해 주신 기억이 났다.이 문제에서 키포인트는 다음과 같다.현재 최상단의 스택의 값과 현재 입력으로 주어진 값을 비교하여 작은지 큰지에 따라 스택을 뺄지 널지 정하면 된다.아래는 소스코드 해설이다. [코드 해설] 스택 myStack을 사용하여 각 숫자에 대해 이전 숫자들을 처리한다.입력으로 주어진 수열을 하나씩 처리하면서, 현재 숫자보다 큰 이전 숫자를 찾기 위해 스택을 사용한다.현재 숫자보다 큰 이전 숫자를 찾는 과정스택의 상단에 있는 숫자가 현재 숫자보다 크다면, 해당 숫자의 인덱스를 출.. 2025. 1. 4.

티스토리툴바