programmers N으로 표현 사람들이 많이 못 푼 문제 중 하나라 어려울거라 생각했지만 정말 해법이 떠오르지 않더라구요. 약 40분 정도 고민을 했는데 도저히 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였습니다. 그 이전에 제가 생각했던 아이디어랑 이 아이디어의 문제도 같이 기록해볼게요. 분명 문제 분류에서 말하듯이 '동적계획법'을 사용하는 문제입니다. '동적계획법'은 말 자체는 어려우나 그냥 한 마디로 '그 이전에 계산한 부분 계산을 이용하여 더 큰 계산을 해결한다'입니다. 이렇게 사용하기 위해선 컨셉을 잘 잡아야합니다. 그 이전의 부분계산을 어떻게 설정하느냐에 따라서 문제를 쉽게 해결할 수도 있고 더 미궁으로 빠져들 수도 있죠. 저의 경우 처음에 이..
너비 우선 탐색(BFS) 오늘은 너비 우선 탐색(BFS, Breadth-First Search)에 대해 간략하게 정리해보려 합니다1. 우선 시작하기 앞서 그래프에 대해서 알아야 하는데요. 알고리즘에서 말하는 그래프는 중고등학교 때 수학시간에 배운 x축, y축과 전혀 관련이 없는 것이더라구요. 그래프 알고리즘에서 말하는 그래프는 정점(node)와 간선(edge)를 말합니다. 그래프에 대해 알아야할 것은 여기까지 입니다. 이제는 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 다음과 같은 질문을 해결해줍니다. 정점A에서 정점B로 가는 경로가 존재하는가? 정점A에서 정점B로 가는 최단 경로는 무엇인가? 특히 두번째 질문 '정점A에서 정점B로 가는 최단 경로는 무엇인가' 를 해결해주는 알고리즘으로 유명..
programmers 주식가격 처음에 문제를 이해하지 못해 당황했었지만 입출력 예를 보고 어떤 것을 구하는 것인지 알 수 있었습니다. 간단하게 얘기를 하자면 각각의 주식가격 이후 더 낮은 주식가격이 나올 때의 시간(1초 단위로 주식가격 나옴)을 배열에 넣어 구하는 문제였습니다. 저는 Queue를 이용하여 풀었는데요. 간략하게 정리하면 다음과 같습니다. 주어진 시간 배열을 Queue에 담는다 Queue에서 poll()를 이용해 수를 하나 뽑는다 남은 Queue 내에 돌면서 시간(time)을 1씩 증가시키며 뽑았던 수보다 작은 수를 만나면 break한다 반복문 밖에서 time을 List에 넣는다. 2~4까지의 과정을 Queue가 비워질 때까지 반복한다. 물론 할때마다 time은 0으로 초기화 class So..
Today's Algorithm(2018-10-31) programmers 모의고사 문제 자체는 크게 어렵지 않아 어떻게 좀 더 효율적으로 풀 수 있을지에 초점을 맞춰 설명해보겠습니다. 전 좀 길게 그리고 비효율적으로 푼 것 같아 아쉬운데요. 역시나 다른 사람들은 짧고 효율적으로 풀었더라구요. 비교해봅시다. 각 학생들의 성적을 매기는 과정 저의 코드는 다음과 같습니다. for (int j = 0; j < student.size(); j++) { for (int i = 0; i < answers.length; i++) { if (answers[i] == student.get(j)[index[j]]) { score[j]++; } index[j]++; if (index[j] == student.get(j).l..
Today's Algorithm(2018-10-30) programmers 소수의 합 소수를 이용하여 푸는 문제가 있을 때 가장 효율적인 방법은 '에라토스테네스의 체'를 이용하는 방법입니다. 이름은 어렵지만 구현이나 아이디어 자체는 크게 어렵지 않습니다. '에라토스테네스의 체'는 다음과 같이 구현할 수 있습니다. 소수인지 아닌지 체크할 수 있는 배열을 하나 만들고 안에 boolean 값으로 true 를 모두 넣어둔다 본격적으로 작업을 처리하기 전에 1보다 작거나 같은 수는 return처리하여 종료시킨다 2부터 for문을 돌면서 해당 수가 소수 체크 배열에 true값인지 확인한다. true값이면 우선 그 수는 소수로 등록시키고, 그 수의 배수는 false 처리하여 이후 처리에서 제외시킨다 3번째 과정이 핵..
programmers 완주하지 못한 선수 문제 자체는 크게 어렵지 않았습니다. 하지만 효율성 테스트도 있기 때문에 출제자의 의도에 맞게 푸는게 관건일 것 같네요. 이를 고려하면 HashMap을 이용하여 풀 수 있는데요. 간략하게 정리해볼게요. HashMap에 주어진 참가자를 차례대로 넣는다. 그리고 동명이인의 경우 value값을 증가한다. HashMap에서 완주한 사람을 찾아 value값을 감소한다. 이 때 value값이 0이면 remove()하여 없앤다 HashMap 에 마지막에 남은 1명을 출력한다. 이 방법대로 풀면 다음과 같이 구현할 수 있습니다. class Solution { public String solution(String[] participant, String[] completion) {..
