https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr H-Index라고 하는 것에 대한 정의가 실제로 존재했다! 위키백과에 말과 프로그래머스를 인용하자면 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, ..
숫자 문자열과 영단어 2021 카카오 채용연계형 인턴십 LEVEL 1 문제 'one2three4fivesix' 라는 문구가 주어지면 '123456' 이라는 값을 return하면 된다. 규칙은 간단하다. 즉, 숫자는 숫자 그대로를 출력하고, 문자는 숫자로 변환시켜 출력하면 되는 것이다. 문제를 해결하기 위해 StringBuilder를 하나 선언하여 이후에 한 번에 출력하기 전까지 차곡차곡 쌓을 것이다. 또한, for구문을 통해서 주어진 문자열에 대해 charAt으로 접근하고 알파벳마다의 첫 문자를 기준으로 어떤 문자열인지 알아내는 구조로 진행할 예정이다. 숫자영단어 0 zero 1 one 2 two 3 three 4 four 5 five 6 six 7 seven 8 eight 9 nine 경우의 수는 9가..
2019 KAKAO BLIND RECRUITMENT LEVEL 2 오픈채팅방의 문제는 다음과 같이 이해하면 된다. '111', '222'라는 닉네임을 가진 사람이 채팅방에 들어오고 나가는 과정을 예시로 보여주자면 다음과 같다. 111님이 들어왔습니다. 222님이 들어왔습니다. 111님이 나갔습니다. 다만 여기서 '111'이라는 친구가 '333'이라는 닉네임으로 바꾸어서 들어오면 다음과 같이 출력문이 바뀌어야 한다. 333님이 들어왔습니다. 222님이 들어왔습니다. 333님이 나갔습니다. 333님이 들어왔습니다. 이전에 있었던 모든 공지가 '333'이라는 닉네임으로 바뀌어야 하며, 333이라는 닉네임으로 들어왔으니 들어온 공지를 내야한다는 의미이다. 즉 여기에서 알 수 있는 사실들을 몇 가지 뽑아보자. 첫..
2019 KAKAO BLIND RECRUITMENT LEVEL 1 문제를 보면 이해가 어려운 것은 아니지만, 레벨 1 치고 단번에 이해하기 어려워서 문제를 읽는데에 조금 시간을 투자했다. 아무튼 결론은 테스트하고 싶은 스테이지를 알려주고, 현재 사람들의 스테이지 현황을 파악하여 그 단계의 실패율을 구하는 문제이다. stages.length가 곧 사람들의 수를 의미하며, 스테이지가 올라가는대로 해당 스테이지에 관한 인원수가 -1씩 된다. 정리하면 이렇다. 예를 들어 [1, 2, 2, 4, 5] 라는 스테이지가 주어지고(물론 오름차순으로 주어지는 것은 아니다), 구하고자 하는 스테이지가 4스테이지 일 때로 가정해보겠다. 총인원 : 5명 1 스테이지 : [1, 2, 2, 4, 5] - 1명 (총 인원 5명) ..
가장 먼 노드 문제는 노드로 주어지는 상황속에서 1부터 n까지의 관계 안에 가장 먼 노드를 찾는 문제이다. 즉, 위와 같은 모형이 주어지면 가장 먼노드인 5, 4, 6 의 개수 3을 return하면 된다. 우선 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 둘 중 어느 방식을 선택할 것인가에 대해 생각이 필요해보였다. 가장 먼 노드를 따져본다고 했을 때 가정을 해보았다. 그랬더니 순서가 대충 이렇게 나올 것 같다. 1 - 2 - 5(return) - 4 - 3(?) - 6 ... 어떻게 순서를 잡냐에 따라 다르겠지만 4에서 3으로 가는게 말이 될까? 2에서 이웃한 노드도 사실 상 3, 4, 5이기 때문에 2 - 3으로의 순서도 고려해볼 필요가 있다. 깊이 우선 탐색에서는 가장 먼 노드가 몇개있는지 ..
2018 KAKAO BLIND RECRUITMENT LEVEL 2 레벨 2문제 치고는 상당히 쉬운 문제라 고민하지 않고 풀었다. 단지 고민했던거라면 ArrayList의 사용이냐 LinkedList의 사용이냐였는데 일단 어느 하나 구현해보고 나서 무엇이 더 빠른지 체크만 하고 왜 그렇게 나왔는지에 대해서 공부해보기로 했다. 다만 알고리즘 LRU(Least Recently Used)을 사용한다고 나와있었는데, 그 알고리즘이 어떤 알고리즘인지 알 수 없던 터라 그 부분에 대해서는 어떤 개념인지에 대해 조사를 해보았다. LRU는 캐시 사이즈가 주어지는데, 그 사이즈 안에 있는 노드들이 있고 사이즈를 벗어나게끔 하나의 노드가 들어오게 되면 가장 오래된 노드를 버리고 새로운 노드를 받아들인다. 또한, 데이터 노드가..
2018 KAKAO BLIND RECRUITMENT LEVEL 2 LEVEL2인 뉴스클러스터링 문제만 해도 이렇게 까지 오래걸리지는 않았다. 그리고 문제가 나름 길었어도 풀 의욕은 있었는데 이 문제 만큼은 의욕이 떨어졌다. 계속되는 반복문에 일회성 계산이 아닌, 터뜨린 자리는 위에서부터 순차적으로 내려와 메꾸는 알고리즘 형태를 가지고 있어야 했기 때문이다. 물론, 더 나은 알고리즘으로 푼 사람들도 있겠지만 말이다. 중요한건 어떠한 참고서나 메소드 등을 활용하지 않았다는 점에서 문제를 풀었을 때 희열이 있었다. 내가 생각한 이 문제의 핵심적인 부분들은 다음과 같다. 1. 네모 확인하기 ---네모 형태가 없으면 break--- 2. 확인된 사항의 인덱스를 공백으로 변경(꼭 공백일 필요는 없다.) 3. 공백 ..
같은 Level 1이었던 비밀지도 편에서는 이렇게 오래걸리지는 않았지만, 다트 게임에서 시간을 오래 쓴 것 같다. 이유는, 조금 더 효율적인 방법이 있을 줄 알았다. 지속적으로 S, D, T에 대해 파악해야 하며, 한번에 들어오는 값에 의해서 숫자를 어떻게 분리할 것인지, option이 나왔을 때에 이전 점수에 대해 어떻게 처리할 것인지, 현재 값을 어떻게 - 시키는지 이런 잡다한 고민들 때문에 시작하기부터 애를 먹었다. 처음부터 비효율적이라고 생각하게 되면 시도조차 하지 않는 성격이기에 노가다성의 알고리즘 문제보다는, 효율적인 알고리즘을 생각해내는 것이 더 어울리는 것 같다. 이 문제가 무작정의 알고리즘 문제는 아니지만, 이해는 나름 쉽지만 구현하는데에 애를 먹기도 하고, 상수처럼 값을 집어넣어 하는 ..
이 문제는 애초에 동적 계획법이라는 파트 아래에 나와있는 문제였다. 동적 계획법에 대해서는 이전 포스트에 작성해 놓은 것이 있다. 여기서 중요한 것은, 아래의 표 순서에서 1번에 대한 정보는 확인했으니 2번부터 어떻게 절차를 밟아 나갈 것인가에 대한 질문이었다. 1. 동적 계획법을 사용해서 풀 수 있는 문제인지 확인 2. 문제의 변수 파악 3. 변수 간 관계식 제작(점화식) 4. 메모 5. 기저 상태 파악 6. 구현 또한, 2번부터 6번까지 진행하면서 마지막 구현단계에서 반복문을 사용해서 구현할 것인가, 재귀함수를 사용하여 구현할 것인가에 대한 논의도 이루어져야 했다. 일단 문제는 변수를 파악하고 점화식을 작성하는 것 부터에서 애를 먹었다는 것이다.. 너무 어려워요 그러다가 깊이우선탐색으로 푼 알고리즘이..
동적 계획법 프로그래머스 문제 중 'N으로 표현'이라는 문제를 접하게 되었다. 이 문제의 분류는 다름아닌 동적 계획법(Dynamic Programming) 이었다. 동적계획법이라는 말을 처음 접한 나는 이 개념이 무엇인지 찾아보게 되었고, 이해한대로 정리해볼 것이다. 먼저, 동적 계획법이라는 것은 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 다시 저장하여 다시 큰 문제를 해결할 때 사용하는 방식이다. 즉, 어떠한 문제를 풀기 위해 특정한 알고리즘을 사용하여 푸는 것이 아닌, 하나의 문제를 풀기 위해 접근하는 방식에 조금 더 가깝다고 할 수 있겠다. 이는 특히 일반적인 재귀를 단순히 사용하여 시간 단위가 더 큰 문제들을 구하기 위해 필요 없는 재귀까지 순차적으로 돌아 비 효율적인 계산 방식이..
알고리즘을 풀 때에 set과 list의 선택은 중요하다. 당연히 어떤 key를 가지고 사용하는 문제이거나, 값을 빨리 찾기 위한 의도를 가지고 있다면 set을 사용하는게 맞지만, 그 중간점에 있는 애매한 문제들도 여러 개 있다. 사실 사이즈가 정해져있으면 배열을 사용하는게 맞다고 생각하지만, 제한된 시간안에 풀어야 하는 문제라면 컬렉션을 사용해서 풀 문제들도 있을 것이다. 수 찾기에서는 set을 사용했다. 값을 일차적으로 넣은 상태에서 이후에 나오는 수가 초기에 세팅한 값인지 알기 위해서는 그 해당 값을 찾아야 한다. 즉, 추가와 삭제에 대한 문제가 아닌, 검색에서 성능차이가 발생하는 문제라는 것이다. 수 찾기 문제에서는 명확한 알고리즘을 생각해내지 못해 틀린 사람에 대한 비율보다, 효율성테스트에서 떨어..
