성장 일기 - 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인덱스 번호를 저장하고 ..

N개의 실수가 입력되었을 때 연속으로 입력된 값들의 곱 중에서 최대값을 출력하는 문제이다. 실수가 N개가 최대 10,000이다. 이 경우 배열에 입력받아 첫 번째 인덱스 부터 곱해서 최대의 값을 구하면 시간초과가 난다. 이 경우 시간 복잡도가 N!이다. 맞나??? 결론은!!입력을 받자마자 바로바로 처리를 해줘야 된다. 시간복잡도 N으로 풀어야함. 풀이는 입력되는 값들을 곱해나가면서 현재 까지의 곱의 결과가 1이하면 더 이상 곱해봤자 의미가 없다. 그래서 현재의 곱셈의 결과가 1 이하면 1로 초기화 해준 후 다음부터 다시 곱해나간다. 곱해나가면서 최대값을 체크해주면 끝!! 정답코드 http://colorscripter.com/s/h49CwPP

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

오랜만에 알고리즘 풀이...조합문데인데 헷갈렷다. 망함 프로는 언제땀??ㅋㅋㅋㅋ 1개~n개의 집합을 모두 조합해주어서 차이가 최소인 값을 구해주면 된다. 중요한건 그냥 차가 아니라 차의 절대값의 최소값을 구해주어야 한다!!

음...최근에 업로드한 1600번 말이 되고픈 원숭이나 벽부수고 이동하기와 같이 풀었다. 다른 사람들은 어떻게 풀었는지 모르겠지만..위와 같은 방식이면 이렇게 정답률이 높을리가 없는데!!내가 어렵게 풀었나ㅋㅋㅋㅋ맞추기만 하면 되지!!! 접근법1. 최악의 경우 맵 크기는 50*50이다. 벽이 출발, 도착 지점 말고 전부 벽이면 최대 100개의 돌을 부셔야 한다.2. 1개 ~ 100개의 벽을 부술 수 있는 경우를 모두 고려해주었다. (삼성 기출 연구소와같이 벽을 조합으로 부수면 시간초과 남)3. 그래서 최근에 풀었던 벽부수고 이동하기와 비슷한 느낌이라!! 같은 방식으로 풀기를 결정.4. 최대 100개를 부순다고 생각하고 arr[101][50][50] 의 배열을 만들어준다.5. 100은 0~100개의 벽을 부..

오늘 역테...너무 쉽게 나왔다.ㅜ,ㅠ1번 큐브는 노가다라 2번 먼저 풀었는데, 2번 40분 컷인데 1번은 디버깅하다 시간 다 갔다ㅜ,ㅠ 정답 출력할 때, 인덱스 값을 잘 못 준거 같긴한데...확인할 길이 없으니ㅜ,ㅠ둘 중 하나는 다들 푼 것 같아 면접이나 갈 수 있을지 모르것다!!!!!!!!!! 접근법1. 단순 BFS이나 큐에 넣기 전 다음 칸의 값과 현재 칸의 값의 차가 일정 범위 안에 들어와야 큐에 넣는다.2. 큐에 넣는 작업이 없을 때 까지 BFS를 반복해준다. 끝~ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697..