GetComponent<('0')>

1. 정렬해서 풀기 #include #include #include //sort using namespace std; string solution(vector participant, vector completion) { string answer = ""; //정렬 sort(participant.begin(),participant.end()); sort(completion.begin(),completion.end()); int i = 0; for(; i < completion.size(); i++) { if(participant[i] != completion[i]) { break; } } return participant[i]; } algorithm에서 지원하는 sort 기능이 필요하다. 2. 해시로 풀어..

해시? 다양한 길이의 데이터를 고정된 길이 데이터로 mapping한다. 이렇게 고정 크기 값으로 변환된 데이터를 해시라고 한다. 여기서 변환해주는 함수를 해시 함수라고 부른다. 해시 테이블? Key, Value로 이루어지는 data에서 Key값에 해시 함수를 사용하여 Key 값을 index로 변환하여 만들어지는 테이블 사람 이름이 Key, 전화번호가 Value인 데이터에 해시 함수를 적용시켰다. 문자열이던 Key는 해싱되어 두자리 정수 해시값이 된다. 이 고유 index에 Value값이 저장되는 것이다. 이로 인한 이득? 정렬을 안하므로 검색과 삽입이 정말 빠르다. 평균 시간복잡도 O(1) 그냥 hash function에 내가 찾고자 하는 값을 넣어서 index 변환을 하면 끝 주의점 1. 해시 함수의 ..

sort 함수를 쓰면 끝나지만, 자료구조때 얼렁뚱땅 스킵했던 정렬에 대해 제대로 정리하고 직접 구현해볼 필요성을 느꼈다. 1. 선택 정렬 배열에서 가장 작은 데이터를 앞으로 보내는 정렬. (최댓값도 같이 처리한다던지의 개선 방법 존재) 1. 주어진 리스트 중 최소값 찾기(min) 2. 그 값을 맨 앞에 위치한 값과 교체(temp) 3. 해당 값을 제외한 나머지 리스트에서 반복 시간 복잡도 정렬해야하는 개수 N-1마다 (N-1, N-2, ... 1)번에 해당하는 비교 작업 + 교체 작업을 한다. 비교 시간복잡도 최악/최선에 상관없이 항상 같다. N(N-1)/2 = O(n^2) 정렬 시간복잡도 3(N-1) = O(n) 공간 복잡도 배열 O(n), 교환용 상수 O(1) 소스 코드 #include using n..

주어진 값 범위 내에서 소수를 구하고, 주어진 값에서 소수를 뺀 값도 소수인지 검사하는 방식으로 생각했다. 다만 골드바흐 파티션이 여럿이라면 이 값의 차이가 가장 적은 것을 반환해야 한다. 작은 숫자부터 검사하게 되면 골드바흐 파티션을 찾았더래도 차잇값이 더 작은 파티션을 찾기 위해 계속 반복문을 진행해야 할 것이다. 그래서 범위 내 소수 검사를 값이 큰 것부터 내림차순으로 진행하도록 바꿔보기로 했다. 예를 들어, 16이 주어졌다면 소수 검사는 2부터 16/2=8까지만 내림차순으로 진행한다. (덧셈이기때문에 /2 범위) 그러면 7 5 3 2의 값이 나온다. 7부터 내림차순으로 16에서 뺀 값이 소수인지 검사한다는 의미. Prime 검사 함수는 이전에 쓴 것을 그대로 사용했다. int main(int ar..

단순하게 반복문을 돌려서는 시간초과가 난다. 시도 1) 나누기 검사 범위를 주어지는 값 a의 절반까지만 수행하기 bool isPrime(int a) { if(a == 1) { return false; } else { for(int i = 2; i < a/2; i++) { if(a % i == 0) { return false; } } } return true; } 시도 2) 2의 배수 배제하기 bool isPrime(int a) { if(a == 1 || a % 2 == 0) { return false; } else { for(int i = 3; i < a/2; i+=2) { if(a % i == 0) { return false; } } } return true; } 1 검사문에 짝수인지도 검사하게끔 했다..

흔히 정수처리를 할 때 int만 쓰는데, 이 int로도 감당안되는 엄청나게 큰 수는 어떡할래? 라는 문제. 그냥 자료형 중 제일 큰 것을 쓰면 되지 않나 싶었는데 unsigned long int로도 해결이 안됐고, 구글링해서 찾은 __int64로도 값 처리가 안되는 엄청 큰 숫자다... 아쉬운 점은 내가 자료형 구글링하면서 이미 저 문제의 해결법들을 봐버렸다는 점.. ㅜㅜ 주어지는 입력값을 string으로 받고, answer 배열에 자리수마다 연산하여 저장하게 된다. 이 answer 배열의 크기는 a와 b중 더 긴 자릿수+1이 최대가 될것이다. (10 올림때문에) string a("9223372036854775807"),b("9223372036854775808"); int aLen(a.length()),..

보면 알겠지만, 현재 층의 호수 거주인을 구하려면 이전 층의 값이 필요하다. 재귀의 냄새가 난다. 식으로 정리해보면... fn(k) = fn(k-1)+fn-1(k)이다. n층k호 거주민 수 = n층 k-1호 거주민 수 + n-1층 k호 거주민 수 라는 얘기다. f1(k) = k, fn(1) = 1 이라는 초기화 조건이 있다. int apartment(int floor, int room) { if(floor == 0 || room == 1) { return room; } else { return apartment(floor, room-1)+apartment(floor-1,room); } } 이를 이용한 재귀함수를 짜서 돌렸다. 고등학교 수열 공부를 다시 해두면 여러모로 편해질 것 같다.

굳이 배열로 풀 필요가 없어보여서 배열을 사용하지 않았다. 1중 반복문으로 81개의 값을 cin으로 받고 currentMax를 갱신하는 흔한 방법으로 진행 입력값 조건이 자연수 ~99까지이기 때문에, 만약 현재값이 99라면 무조건 MAX값이므로 반복문 종료. (break를 써야해서 2중반복문 대신 1중으로 변경한 이유이기도 하다) 1중 반복문이라 index가 입력순차번호인 딱 하나만 존재하는데, 이 값을 %9 하면 y값이 나오고, index에서 y를 뺀값의 몫에 1을 더하면 x값이 나온다. int currentMax(-1), num, index, x, y; const int MAX(99); for(int i = 1; i > num; if(num == MAX) { index..

그냥 주어진대로 반복문을 활용해 풀면 시간초과가 발생하는 문제. 수식을 세워야 함. (day - night)*x > height로 구하면 안된다. 이 조건을 위배하기 때문. 낮중에 이미 정상에 올라갔는데 그날 밤에 내려가는 걸 계산했을 시, 높이 미달성인 경우를 고려하지 않은 수식이다. 즉, 위 수식은 '밤 기준'으로 세워진 수식이기 때문에, 높이를 갱신하게 되는 '낮 기준'의 수식을 세워야 한다. day x일의 높이는 어떻게 구할까? x일만큼 낮에 올라간 거리에서 (x-1)일만큼 밤에 내려간 거리를 빼면 된다. x*day - (x-1)*night > height 를 달성하는 최소 정수값 x를 구하면 끝이다. 식을 잘 정리하면 x > (distance - night) / (day - night) 이다. ..

먼저, 분수의 형태는 사실상 배열의 rol. column을 /로 구분한 형태라서 분수는 크게 중요치않다. 분수 배열의 "순서"만 놓고 따질때 저 초록선대로 그룹을 지어보면 다음과 같다. 1, 2 3, 4 5 6, 7 8 9 10, ... 여기서 i = 1으로 놓고 그룹의 시작값만 보면... 1, 2, 4, 7 ... 이 시작값의 차이는 1, 2, 3 이라는 규칙을 가진다. 이제 할 것은 간단하다. 입력값 n에 대해서 배열 시작값(1,2,4,7..)과 반복적으로 비교하다가 입력값 n이 배열 시작값보다 작아지는 때가 온다면 여기서 위치를 추적하는 방식이다. 예를 들어, n으로 9가 주어졌다. 1, 2, 4, 7, 11... n과 비교하다가 11에서 조건을 달성하게 된다. 1 2 6 7 15 3 5 8 14 ..