성장 일기 - Small Step

동적 할당이 없이 NODE 구조체 배열에서 하나의 노드씩 가져와 더블 링크드 리스트를 만드는 예제이다. 더블 링크드 리스트를 이해했다면 크게 어렵지 않은 내용이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include int node_index; // NODE 배열 선언 struct NODE { int value; NODE * prev; NODE..

알고리즘 프로 등급을 준비하기로 하였다.. 입사 준비를 위해 DFS, BFS, 브루트포스, DP 등 과같은 알고리즘과 다른 방식으로 출제된다. 특정 자료구조를 활용한 문제가 나오기 때문에 우선 자료구조를 공부하기로 하였다. 어느 글에서 동적 할당대신 구조체 배열을 이용하여 링크드리스트를 만드는 글을 보았고 구연해 보았다. 특별한 것은 동적할당 없이 이미 선언된 노드 배열에서 노드를 가져온다. 주석을 달아 놓았다. 장점은 동적할당보다 속도가 우수하며 디버깅이 쉽단다!! 아직 활용을 안 해봐서 모르겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..

주어진 범위 안에 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

1차원 배열의 부분합을 구하는 문제이다. N개의 수들이 무작위로 입력될 경우 N개의 범위 안의 범위의 부분합을 구하는 문제이다. 입력을 받을 때 이전 까지의 입력들에 합에 자신을 합하여 인덱스에 넣어주면 된다. 여기서 a~b까지의 범위를 합을 구하라고하면 b까지의 합 - (a-1) 까지의 합을 해주면 정답이 된다. 정답 코드 http://colorscripter.com/s/HEsTF1J

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