학습저널

https://www.acmicpc.net/problem/14889 알고리즘 설명은 주소 참고 N이 작기 때문에 Brute force 방법을 이용해 풀기로 했고 모든 팀 조합을 조사해서 min 값을 출력하면 된다고 생각했다. 이 문제의 핵심은 조합 (Combination)을 짧은 시간 내에 구할 수 있느냐다. 순열과 조합에 대한 개념은 아래 글을 참고해주길 바란다. (글 작성중) 코드는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909..

https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem N개의 계단이 주어졌을 때 1, 2, 3번의 걸음으로 가는 모든 경우의 수를 구하는 문제다. 처음에는 DFS를 이용하는 줄만 알고 재귀호출을 이용한 DFS를 구현해서 풀었으나 타임아웃이 나와 2시간이나 헤메었다. 도저히 생각이 안나 해당 문제의 Discussions 게시판을 참고했고, 알고보니 이 문제는 아래의 피보나치 수 구하는 문제와 매우 비슷한 문제였다. 나는 피보나치 수열이 점화식으로 표현이 된다는 점은 알고 있었지만 점화식에 대한 응용법과 정확한 개념을 알지 못했었다. 그래서 이 문제를 풀면서 이 문제가 점화식을 활용한 DP 풀이로 해결할 수 있을 거라고 생각하지 못했다..

https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem N개의 아이스크림들 중 서로 다른 2개를 골라야 하는데, 주어진 Money와 두 아이스크림 가격의 합이 같은 경우를 찾는 것이다. 아이스크림은 정수의 나열로 주어지며 아이스크림의 ID는 그 수의 순서, 아이스크림의 가격은 그 수가 된다.(단 1번째 아이스크림부터 순차적으로 검사) 문제 설명이 애매한것인지, 내가 영어를 못해서인지 모르겠는데 문제 이해만 하는데 너무 오래 걸렸다. 단순한 두 수의합 문제이므로 순차적으로 검사하되 첫번째 아이스크림을 고른 다음에 해시 테이블을 이용해 (Money - 첫 아이스크림 가격)과 같은 가격의 아이스크림 ID(순서)를 찾으면 된다. 즉 Key = 아..

https://www.hackerrank.com/challenges/ctci-big-o/problem 주어진 수가 소수인지 아닌지 판별하되, O(sqrt(n)) 시간안에 답을 내야하는 문제다. 에라토스테네스의 체라는 방법을 알아보면, n이 소수인지 아닌지 판별하기 위해서는 sqrt(n) 이하의 수만 나눠보면 된다고 한다. 왜 sqrt(n)이하의 수만 나누어 보면 되는지는 포스트 http://makedotworld.tistory.com/13 를 참조하길 바란다. 코드는 아래와 같다. 123456789101112131415161718192021222324252627282930313233void isPrime(int number){ bool isprime = true; if(number == 1) { cout

https://www.hackerrank.com/challenges/ctci-comparator-sorting/problem 주어진 구조체 player를 정렬하되, 첫번째로 멤버변수 score를 내림차순으로 정렬하고 만약 score가 같으면 멤버변수 name을 사전순으로 정렬하도록 하는 함수를 만드는 것이다. 간단하게 두 변수를 비교하는 compareBySN(p1, p2) 함수를 만들어 첫번째 파라미터가 더 앞에 오는 조건이면 true, 아니면 false를 반환하게 구현한 다음 STL algorithm 안에 내장되어 있는 sort를 사용하면 된다. algorithm::sort 함수의 사용방법은 다음과 같다. sort(배열의 첫 주소, 배열의 마지막 주소, 비교에 사용할 함수이름) 그리고 string::c..

https://www.hackerrank.com/challenges/ctci-lonely-integer/problem 수열이 주어졌을 때 똑같은 값이 딱 하나인 녀석을 찾는 문제다. 아주 짧은 코드로 구현할 수 있었는데, 비트연산의 활용법을 잘 몰라서 약간 긴 코드가 되어버렸다 주어질 수 있는 수는 100 이하로 100개의 배열을 준비한 후 수열을 처음부터 탐색하면서 배열[수열의 값] 의 값을 1씩 증가시킨 후, 배열의 값이 1인 index를 리턴하는 방식으로 구현했다. 1234567891011121314int lonely_integer(vector a) { int numLength = 100; int isPair[numLength] = {}; for (int i = 0; i

해시 함수(Hash function) 해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 바꿔주는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값 또는 해시라고 부른다. 위키백과에 게재되어 있는 해시 함수의 정의다. 간단히 말하면 특정 값을 넣었을 때, 내가 원하는 범위의 값이 나오게 만드는 함수라고 말 할 수 있다. 간단히 그림으로 표현하자면 다음과 같이 표현할 수 있다. 해시 함수의 용어로는 충돌(Collision)과 클러스터(Cluster)가 있다. 충돌은 다른 값을 넣었을 때 같은 해시 값이 나오는 경우를 말한다. 클러스터는 해시 값에 의해 저장된 값들이 특정 구역에 몰리는 현상을 말한다. 그럼 이런 해시 함수는 왜 존재하는 걸까? 해시 함수는 주로 보안, 오류 검사, 자료구조 등 활용 ..

https://www.hackerrank.com/challenges/ctci-fibonacci-numbers/problem 피보나치 수열을 구하는 아주 간단한 예제다. 거의 시키는 대로 구현만 하면 되므로 아주 간단하게 짤 수 있지만 아래 코드의 시간복잡도를 계산해 보면 효율적이지 못한 코드다. 풀이시간 : 1분 50초 1234567891011121314int fibonacci(int n) { if(n == 0) { return 0; } else if(n == 1) { return 1; } else { return fibonacci(n-1) + fibonacci(n-2); }}Colored by Color Scriptercs 한번 함수가 호출 될 때 마다 2번씩 함수를 호출하므로 그림으로 그려보면 바이너..

https://www.hackerrank.com/challenges/ctci-queue-using-two-stacks/problem Queue를 Stack 두개로 구현하는 문제이다. 처음 생각난 방법으로 구현했을 때 Time Out이 발생했고, 두번째 방법으로 풀었을때 성공을 했다. 방법 1 Push : 1. Push를 할 떄마다 Stack1의모든 원소를 순차적으로 꺼내 Stack2에 넣고 주어진 원소를 Stack1에 Push 한다. 2. Stack2의 모든 원소를 순차적으로 꺼내어 Stack1에 Push 한다.Pop : 1. Stack1은 이미 Queue 형태로 정렬되어 있기 때문에 Pop하면 된다. 하지만 이 방법을 쓰면 모든 원소를 총 두번 이동시키므로 Push는 2N의 시간복잡도를 가지게 된다. ..

https://www.hackerrank.com/challenges/ctci-balanced-brackets/problem ( ), { }, [ ] 로 이루어진 String이 주어졌을 때, 이 괄호 문자열이 Balanced 인지 판별하는 문제다. 이 문제에서 말하는 Balanced는 한번 열린 괄호가 짝이 맞춰지면서 모두 닫히는 조건을 말한다. 괄호 문제는 Stack 자료구조를 활용하면 쉽게 풀 수 있다. 열린 괄호가 입력되면 Stack에 넣고, 닫힌 괄호가 입력되면 Stack의 맨 위 요소와 쌍이 맞는지 확인하고 Stack에서 제거하는 방식으로 진행하면 된다. 코드 상에서 Balanced 한 조건을 판별하기 위해서는 다음과 같은 조건을 갖추면 된다. 1. 닫힌 괄호인 경우 Stack이 비어있지 않은지 ..