성장 일기 - Small Step

주어진 범위 안에 On된 전등의 개수를 출력하는 문제이다. 입력의 범위가 크고 범위가 주어진 문제이므로 세그먼트 트리를 이용한다. 여기서 중요한것은 전등의 상태는 On/Off 만 있다는 것이다. 그리고 입력이 매우 크므로 Lazy를 이용해준다. 범위에서 On의 개수는 범위-현재 노드의 값이다. Lazy변수에 저장되는 값은 0아님 1이다. 상태는 On/Off 만 있으므로. 이 부분은 비트 연산으로 처리해주었다. http://colorscripter.com/s/1s6zdVO 공유된 코드 - Color Scripter colorscripter.com

삼전 역량 테스트에 최적화 되어서인지...아직도 모든 경우의 수 다 해보기 밖에 안 떠오른다..ㅎㅎ 왼쪽 상단의 좌표와 오른쪽 하단 좌표를 찾고, 이 영역 내부가 색종이 내부인지 판단해 주었다. 통과는 하였으나 시간이 완전 별로다...ㅎㅎ 정답 http://colorscripter.com/s/3EAYprm 공유된 코드 - Color Scripter colorscripter.com

처음 입력 받는 수의 열에서 원하는 번째의 숫자가 몇 번째로 출력하는지를 계산하는 문제이다. 풀이 우선 순위를 입력 받을 때, 우선 순위만 저장하는 것이 아닌 그 위치 정보도 같이 저장하고 있으여 원하는 값 출력이 가능하다. 그래서 구조체에 우선 순위와, 처음의 위치를 저장하는 변수를 선언하고 여기다가 우선순위와 함께 인덱스 번호도 같이 넣어준다. 그리고 반복문을 통해 우선 순위가 높은 순서대로 찾아 출력해준다. 출력해줄 때 print를 카운트해주는 변수에 +1을 해준다(초기값 0). 그리고 현 우선순위가 모두 출력하면 이 보다 낮은 우선 순위들을 출력해준다. 낮은 우선 순위를 출력해주다 내가 결과를 알고 싶은 데이터의 우선순위와 현재 우선 순위가 같고 내가 원하는 데이터의 위치 정보와 현재 데이터에 저..

전체 배열에서 k개의 연속된 부분 배열을 선택하였을 경우, 부분 배열안에 다른 값들의 종류가 최대가 되는 개수를 출력하는 문제이다. 그리고 쿠폰을 사용하여 정해진 번호의 초밥을 추가로 먹을 수 있으며 이 초밥이 기존에 먹지 않았을 경우 종류가 다른 초밥으로 인정되어 최대 값에 +1이 된다. 풀이 문제에서 주어진 테스트 케이스로 설명을 해보겠다. 벨트에 놓인 초밥의 수 : 8 초밥의 종류 : 30 연속해서 먹는 접시의 수 : 4 사용 가능한 쿠폰의 번호 :30 입력된 n개의 초밥의 정보 : 7 9 7 30 2 7 9 25 처음 입력된 7을 기준으로 연속해서 4개씩 먹어보겠다. 7 9 7 30 -> 먹은 초밥의 종류 : 3 9 7 30 2 -> 먹은 초밥의 종류 : 4 7 30 2 7 -> 먹은 초밥의 종류..

오른 차순으로 입력 받는 배열들 중 2개를 선택해 그 합이 가장 작을 때의 두 배열 인덱스를 출력하는 문제이다. 이 경우도 완전 탐색으로 2개의 용액을 다 더해보면 시간 초과가 난다. 그래서 모든 결과 값을 구하여 결과를 얻는 방법 말고 새로운 방법으로 문제를 풀어야 한다. 오름차순으로 정렬되어 있다는 것을 기반으로 좀만 더 생각해보면, 우리는 이것을 시간복잡도 N으로 풀수 있다. 변수 및 배열 선언 문제에서 주어진 범위가 -10억~10억. int의 범위 대략 -21억~21억 문제에서 알칼리만 -10억짜리 2개이면 -20억, 산성 +10억짜리 2개이면 +20억으로 int의 범위안에 들어온다. long long을 쓸 필요가 없다. N개의 입력 받은 배열 arr의 0번 인덱스와 N-1인덱스 번호를 저장하고 ..

오~~랜만에 문제를 풀기 시작했다. 요즘 알고리즘을 배우기 시작했는데....나의 머리가 나쁘다는 것을 다시금 느끼고 있다. 2805 나무 자르기는 '이진 탐색'을 이용해야지!!!만 떠올리면 바로 풀리는 문제이다. 아마도..그렇다. 나무의 높이를 범위로 해서 가져가려는 나무의 길이를 만족하는 절단기의 최대 높이를 구하면 된다. 이분 탐색을 구분 짖는 기준은 범위의 중간 값 M과 절단기의 높이 이다. 이분 탐색에서 가장 중요한 것은 탐색 범위를 바꾸어주는 것이다. 여기서 현재 구한 절단기의 최대 높이가 중간 값 M보다 작을 경우는 탐색을 해서는 안 되는 구간이다. 왜냐하면 우리는 절단기의 최대 높이를 구하야 하기 때문!! 그래서 현재 구한 최대 높이가 M보다 같거나 클 경우 탐색의 시작 범위 s를 바꾸어준다.