본문 바로가기
반응형

SWE/코테137

Selection Problem 선택 알고리즘 Selection Problem 선택 알고리즘 Q. n개의 원소 중 k번째로 큰 숫자는 무엇인가? {45, 33, 21, 5, 6, 8, 63, 54, 76, 82} 선택 알고리즘이란 다음과 같은 문제가 주어졌을 때, O(n) 시간 복잡도를 가지는 풀이법이다. 선택 알고리즘을 설명하기에 앞서, 다른 방식으로 문제를 해결할 때의 시간 복잡도를 확인해보자. 방법1. 가장 큰 숫자를 찾고, 그 숫자를 제외한 나머지에서 가장 큰 숫자를 찾고, ... 이를 반복하는 방법. - k번째 큰 숫자를 찾을 때? 1번째 큰 수는 n번의 비교, 2번째 큰 수는 n-1번의 비교, ... k번째 큰 수는 n-(k-1)번 비교 => 따라서, O(kn) - k=1번째 큰 수는 O(n) - k=n번째 큰 수는 O(n^2) 방법2. .. 2018. 11. 7.
[성실코딩 18일차] 백준 #2493 탑 / 스택 ** 재밌는 문제당 근데 처음엔 stack사용할 생각 못하고, 만약 높이가 5인 세 번째 탑이 들어오면 배열1~5까지 3으로 초기화하고, 그 후에 높이가 2인 네 번째 탑이 들어오면 배열 1~2까지는 4로 초기화하고, 다음에 높이가 7인 다 섯번째 탑이 들어오면 배열 1~7까지 5로 초기화 이런 식으로 풀어나가려 했다. 그러면 현재 탑의 높이를 배열의 인덱스로 바로 참조할 수 있으니까! 근데 탑의 높이가 1억까지 가능하고, 따라서 메모리 초과. 두 번째 생각한 방법은 스택을 사용하는 것이였다. 현재 들어온 탑의 높이가 스택안의 값보다 크면 pop하고 현재 값 push하기. 현재 들어온 탑의 높이가 스택안의 값보다 작으면 pop하지말고 그대로 push하기 근데 시간초과 나왔다 ㅠㅠ 그냥 다른 분 코드 보려고한다.. 2018. 11. 5.
백준 컴파일 에러 / 런타임 에러 c++11 에서 INT_MAX 를 사용하면 컴파일 에러가 난다. -> INT8_MAX 사용하기visual studio에서 돌렸을 때 INT8_MAX는 127이라는 값을 가져서 진짜 최대값이 아닐 수도 있음,,,(이유모르겠음)차라리 987654321을 최대로 넣는게 나은 것 같다. c++ 에서 memset을 사용하려면 #include 헤더를 추가해줘야 한다.c에서 memset을 사용하려면 #include 헤더를 추가해줘야 한다.(memcpy도 동일한 헤더) 최대 배열 할당전역변수 int로 선언할 때, 최대 3,000,000(삼백만)까지 할당 가능했었음. (이건 그냥 내 경험에서,,,) 런타임 에러 이유- 배열에 할당된 크기를 넘어서 접근했을 때- 전역 배열의 크기가 메모리 제한을 초과할 때- 지역 배열의 .. 2018. 11. 5.
[성실코딩 17일차] 백준 #11866 조세퍼스 문제0 11월2일 금요일이 17일차여야하는데 부산 학술대회 다녀오고 노느라고 못했다ㅜㅜ 그러므로 오늘 일요일인데 17차 메꾸고잇당 허허 원래의 나였으면 이 문제를 풀 수 있는 규칙성이 있을까 엄청 고민했을 것 같은데 귀찮아서인지,,,, 시간제한도 2초나 되니까 그냥 반복적으로 컴퓨터 연산에 맡겼다. 숫자를 출력할 때는 visited 1 표시해서 다시 방문하지 않고 넘어가도록 했다. 다른 사람 코드보니까 대부분 두 개 중 하나 방식으로 푼 것 같다. 1. queue를 구현해서 M-1번째까지는 모두 pop하고 queue 뒤에 다시 push 하는 방법 2. sll로 구현해서 출력하면 해당 노드를 delete하는 방법 내 방식 포함해서 대부분 방식들이 비슷한 시간 복잡도를 가질 것 같다. 그러므로 코드 안짜봐야징 #i.. 2018. 11. 4.
반응형

티스토리툴바