SLENDER ANKLES's 개발블로그

어려운 문제인줄 알았는데 쉬운 문제였다.

우선 완전탐색부터 해봐야한다는 것을 알았다.

문제를 푸는데 쫌 오래 걸리고, 안타까웠다.

처음에 제대로 된 접근을 했는데, 이상한 생각을 중간에 섞어서 풀지 못했던 것이었다. 

문제 정리)

윗 줄의 번호를 몇 개 뽑아 그 번호들과 아래 번호들이 일치하는 경우를 뽑는 것인데 최대인 경우의 뽑으라는 문제였다.

풀이정리)

반복문을 수행하면서

해당하는 두번째 줄값으로 다시 위의 인덱스를 타고 들어가면서 

처음에 시작한 위치로 돌아오면 이 것은 문제의 경우를 만족하는 것이다.

재귀를 수행할때마다 그 값을 temp라는 배열에 저장하다가 만족하면 result라는 결과값을 모아놓는 배열에

넣어주었다. 물론 방문점 체크 처리도 해야 한다.

시간안에 풀지 못해서 아쉽다

쫌 고민을 많이 했다. 

우선 문제를 간단히 정리하자면

1<= x <= 999999 의 숫자가 입력되면

이 수에 포함되어 있는 숫자들을 이용하여 만든 수들 중에 입력된 수보다 큰 최소수를 구하는 문제이다.

다소 문제 설명이 어렵지만,

156을 보자면 156이 포함되어 있는, 156의 자리수로 만들 수 있는 숫자는

156, 165, 516, 561, 615, 651 등등이 있다. 

이 중 입력된 156보다 큰 최소 수는 165이다.

문제 풀이)

처음에는 어떻게 풀어야 되나 굉장히 고민을 많이 했다. 156의 자리수를 가지고 만들 수 있는 수들을 다 구한다음에 정렬하고, 

입력받은 수 보다 큰 숫자를 출력해야 되나? 가 첫 번째 떠오른 방법이었다. 일단 1~999999이기 때문에 숫자를 만드는 방법에 대해서 어려운 점이 있었다.

한번 더 생각해보니까 

1~999999까지 for문을 돌리면서 조건을 만족시키는 숫자를 캐치해내면 되겠다고 생각했다. 

예를 들어 156이 입력되면

1) 156~999999까지 반복문을 수행한다.

2) 각 숫자들마다 자리 수에 있는 숫자들을 판별하여 1,5,6에 부합한지를 체크한다.

3) 만약 조건에 부합하면 바로 출력하고 프로그램을 끝낸다.

4) 조건에 부합하지 않으면 0을 출력한다.

http://www.ciokorea.com/slideshow/24721?slide=1#stage_slide

소프트스킬

소프트스킬은 모든 직종에서 요구되지만, 동시에 이력서에 명확히 기재하긴 애매한 역량이다. 새비 인턴(The Savvy Intern) 블로그를 인용하자면, 소프트스킬을 설명하는 가장 좋은 방법은 특정 성과 사례나 일상 생활의 맥락 속에 그것을 녹여내는 것이다. 모두가 할 수 있는 일을 소프트스킬이라 포장해 소개하는 것이 아닌, 회사의 일원으로서 당신이 줄 수 있는 가치를 설명하는 게 핵심이라고 블로그는 설명하고 있다. 

미국 국립산학협력협회(NACE)가 260명의 기업 경영자와 채용 담당자들을 대상으로 진행한 설문에 따르면, 기업이 채용 시 가장 중요하게 고려하는 소프트스킬은 다음의 5가지였다. 

팀워크

다른 사람과 공동으로 성과를 내는 능력은 언제나 환영 받는다. 모든 사람은 자신만의 전문 분야와 시각을 가지고 있다. 자신에게 부족한 부분을 타인과의 협력을 통해 보완할 수 있다는 점에서 팀워크는 무엇보다 중요한 자질이라 할 수 있다. 

의사 결정력

의사 결정력이란, 어떠한 비즈니스 의사 결정이 가져올 결과물을 다양한 시각에서 검토해 보고, 자신이 판단한 내용의 당위성을 다른 이들에게 설득할 수 있는 능력을 의미한다. 

커뮤니케이션 스킬

잘 읽고, 쓰고, 말하는 능력은 과학, 기술, 공학, 수학(STEM) 분야의 구직자들에게 매우 중요한 역량이다. 복잡한 기술적 개념과 전략을 일반 비즈니스 담당자들에게 설명할 수 있어야 하기 때문이다. 

계획 수립과 우선 순위 정하기

미래를 구체적으로 그려볼 수 있는 혁신적이고 창의적인 인물은 한정된 자원으로 글로벌 경쟁을 펼쳐야 하는 기업들에게 무엇보다 값진 자원으로 받아들여질 것이다. 

연구/비판적 사고

고용인들은 구직자가 모든 문제의 답을 알 것이라 생각하지도, 그것을 원하지도 않는다. 회사가 구직자에게 기대하는 것은 복잡한 비즈니스, 기술 문제를 고민하고, 답을 찾아낼 방법을 모색하려는 자세와 역량이다. 

IT기술력

소프트스킬과 달리 IT기술력은 산업군과 직종에 따라 많은 차이가 있지만, 그럼에도 최근 두각을 드러내는 영역을 확인해 보는 것은 충분히 가능하다. 얼마 전 링크드인이 진행한 설문 결과를 살펴보면 2014년 특히 많은 수요를 보인 대표적인 IT기술력을 확인할 수 있었다. 나아가 전문가들은 올 한 해 주목 받을 기술력에 관해서도 어느 정도 일치된 답변을 내놓고 있다. 여기 그 결과를 살펴보자. 

데이터 보안

데이터 보안은 분명 ‘돈 많이 드는’ 분야지만, 그것이 가져다 주는 사고 예방 효과를 고려하면 충분히 효율적인 활동이라는 인식이 산업 전반에 확산되고 있다. 어떤 기업도 제2의 소니, 제2의 타깃이 되길 원치 않는다. 

몬도(Mondo)의 디지털 마케팅 전략 사업부 로라 맥개리티(Laura McGarrrity) 부사장은 “보안은 모든 비즈니스들의 최우선 과제로 자리 잡았다. 기업들이 다루는 정보의 규모는 과거 그 어느 때보다 많아졌고, 그로 인해 보안의 중요성도 더욱 커졌다. BYOD 트렌드의 확산 역시 보안 부서의 역할(및 인원) 증대에 한 몫 했다”라고 설명했다. 

데이터 분석

빅데이터에 대한 관심은 앞으로도 한동안 계속될 전망이다. 기업들은 여전히 매일매일 쏟아지는 데이터의 홍수를 제대로 수집, 저장, 분석, 해석할 전문가를 수급하는 문제로 허덕이고 있는 상황이다. 

몬도의 맥개리티 부사장은 “물론 달라진 점도 있다. 이제 기업들은 ‘데이터 수집’의 문제에 연연하지 않는다. 그보다 더 중요한 것은 수집한 데이터에서 유용한 정보를 뽑아내고 그것을 다시 실천적인 프로세스로 변환하는 것임을 이해하기 시작한 것이다. 오늘날 데이터는 모든 곳에 있고, 쉴 새 없이 쏟아지고 있다. 이제 핵심은 그 홍수 속에서 진짜 가치 있는 것을 이해하고 발굴해내는, 그리고 그것에 기반해 전략과 의사 결정을 내리는 역량이다. 새로운 테크놀로지가 계속 선을 보일 것이며, 당신은 그것들을 제대로 학습해야 할 것이다”라고 조언했다. 

개발
스마트폰과 태블릿 환경에서 사용자들의 웹 접속은 더욱 확산될 것이다. 모바일, 웹 개발자에 대한 수요가 늘어나게 된다는 전망의 근거다. 맥개러티는 “환경은 완전히 바뀌었다. 앞으로 한동안 개발자와 디자이너들은 더욱 편리하고 아름다운 모바일 기기 UX를 구축하는데 집중할 것이다”라고 말했다.

프로젝트 관리

프로젝트 관리를 IT역량으로 분류하는 것이 적절한지 의아해하는 이들도 많을 것이다. 큰 착각이다. 효율적인 프로젝트 관리자가 없다면 보안, 데이터 과학, 개발 등 모든 프로젝트는 절름발이가 되어 우선순위와 중심을 잡지 못하고 허둥댈 것이다. 

데이터베이스 관리

더 이상 기업들은 고객, 파트너 데이터 수집에 땀을 빼지 않는다. 오늘날 핵심은 데이터의 효율적인 저장과 접근, 분석 역량에 기반해 전략적 의사 결정을 지원하는 것이다. 데이터베이스에 저장된 비즈니스 정보와 파트너 및 고객 데이터 등의 정보를 제대로 관리할 수 있는 당신이라면 현 데이터 주도 디지털 시장에서 그 누구보다 가치 있는 인물로 평가될 것이다.

문제정리)

- 시작은 계단으로 치지 않는다.

- 한계단 또는 두계단 씩 오를 수 있다.

- 연속되게 세개의 계단을 밟을 수 없다.

- 계단을 밟을때마다 점수가 오른다.

- 마지막 계단은 반드시 밟아야한다.

- 얻을 수 있는 점수의 최대값을 구하라.

문제풀이)

dp[계단의번호][1] => 지금 계단을 바로 전 계단에서 한 칸 오르는 경우의 최대 값

dp[계단의번호][2] => 지금 계단을 바로 전전 계단에서 두 칸 오르는 경우의 최대 값

초기 계단의 번호 0 과 1은 값을 지정해 준다.

dp[1][1] = arr[1]; dp[1][2] = 0;

dp[2][2] = arr[1] + arr[2]; dp[1][2] = arr[2];

3번 계단부터는 점화식을 통해 dp를 수행한다.

dp[i][1] => 지금 계단을 한 칸으로 오른 경우

dp[i][1] = dp[i-1][2] + arr[i];    => 전 칸까지 2칸으로 오른 경우의 최대 값에 지금 계단의 값을 더함

dp[i][2] => 지금 계단을 두 칸으로 오른 경우

dp[i][2] = max(dp[i-2][1], dp[i-2][2]) + arr[i] => 두 칸 전까지 오른 경우의 최대 값에 지금 계단의 값을 더함

재귀 함수를 사용해서 

2진 검색을 수행했다.

문제 요약)

1. 동점자수를 고려해서 정렬하라.

2. 원래 입력 했던 순서대로 등수를 출력하라.

문제 풀이)

구조체를 활용해서 풀었다.

구조체에는 원래인덱스, 점수순위인덱스, 점수 정보를 담았다.

(1) 점수를 입력받으면서 원래인덱스를 저장했다.

(2) 점수 별로 정렬했다.

(3) 여기에 점수순위인덱스를 갱신했다.

(4) 원래인덱스 별로 정렬했다.

(5) 출력

정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다. 

정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.

정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다. 

정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.

시간 복잡도 O(n2)

선택정렬(Selection Sort)

가장 큰 것을  선택해서 기준 범위의 앞과 스왑(swap)하는 방식(내림차순정렬)

가장 작은 것을 선택해서 기준 범위의 앞과 스왑(swap)하는 방식(오름차순정렬)

예를 들어

6 2 9 8 3 4 7 이 있다면, 이 것을 선택정렬을 사용하여 오름차순으로 정렬해보겠다.

(1) 6 2 9 8 3 4 7 => 2 6 9 8 3 4 7

(2) 2 6 9 8 3 4 7 => 2 3 9 8 6 4 7

(3) 2 3 9 8 6 4 7 => 2 3 4 8 6 9 7

(4) 2 3 4 8 6 9 7 => 2 3 4 6 8 9 7

(5) 2 3 4 6 8 9 7 => 2 3 4 6 7 9 8

(6) 2 3 4 6 7 9 8 => 2 3 4 6 7 8 9

이러한 과정을 거쳐서 정렬이 완성된다. 

선택정렬의 특징이 하나 있다. 배열의 원소를 최소로 바꾸면서 정렬하는 방법이다.

삽입정렬(Insertion sort)

삽입정렬과 선택정렬이 헷갈렷는데, 삽입정렬에 대해서는 확실히 알게 되었다.

한 마디로 말하자면 현재의 인덱스에 있는 값이 위치해야 할 자리로 가는 것을 말한다. 

예를들어 

6 2 9 8 3 4 7    이 있다면

6 2 9 8 3 4 7

2 6 9 8 3 4 7

2 6 9 8 3 4 7

2 6 8 9 3 4 7

2 3 6 8 9 4 7

2 3 4 6 8 9 7

2 3 4 6 7 8 9

이런식으로 범위를 늘려나가면서 해당 숫자의 자리를 찾아주는 코드이다.

버블정렬(Bubble Sort)

문자 그대로 마치 공기방울이 수면 위로 떠오르듯 가장 큰 레코드가 한칸씩 한칸씩 오른쪽으로 떠올라오는 정렬이다.

6 2 9 8 3 4 7

2 6 9 8 3 4 7

2 6 8 9 3 4 7

2 6 8 3 9 4 7

2 6 8 3 4 9 7

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 3 4 8 7 9

2 6 3 4 7 8 9

2 6 3 4 7 8 9

2 6 3 4 7 8 9

2 3 6 4 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

이런과정을 거쳐서 정렬이 된다. 

동적 계획법(dp)는 가장 흔한 문제 유형 중 하나이고 메모이제이션은 굉장히 자주 구현하게 된다. 

따라서 한 가지 패턴을 정해두고 풀게 되면 확실한 풀이 방법을 알 수 있을 것 같다. 

1. 가장 먼저 basecase 처리

2. cache[]를 모두 -1로 초기화하고, -1이 아니면 cache[]의 값이 없는 것으로 간주.

3. ret(리턴 값)을 참조형(reference)으로 관리하여 실수를 줄임

4. memset을 이용한 초기화

소수 결정 알고리즘을 사용 할 줄 알아야 하는 것도 핵심인 거 같다. 

그 이외에는 몇 가지 예외를 처리하는 식으로 문제를 풀었다. 좋은 방법으로 푼 것은 아닌 것 같아 조금 더 연구를 해봐야 할 것 같다. 

하지만, 더블릿에서 실행 속도 3등을 했다.!!!

설명하기 전에 소수 판별 알고리즘에 대해서 간단히 다시 정리하겠다. 

문제정리)

자연수 n(2이상 1 000 000 000이하)의 자연수가 주어지면

그 것을 소인수 분해하는 것이다.

풀이)

1부터 10000정도까지 소수들의 데이터를 배열에 저장 해 놨다. 굳이 말하자면 소수들에 대한 데이터베이스를 구축해놓고,

열람하며 활용하겠다는 방식이었다. 낭비라는 생각도 들었지만 결과론적으로 이 방법이 꽤 빠르다는 것을 알았다.

그다음부터는

수학공식에 있던 방법을 고대로 가지고 와서 코드로 옮기는 방식을 사용했다. 

매번 지금 계산 되고 있는 것이 소수 인지 판별한다. 소수이면 중단하고 소수가 아니면 소수리스트의 값으로 나누어준다.

이 과정을 반복하게 된다.