문제 조건 입출력 예제 솔루션 주식 정보를 저장하는 Stock 클래스를 만들었다. Why ?) 인덱스와 가격을 함께 다루기 위해서. Stock 객체를 다루는 스택 자료구조를 사용하였다. prices의 길이만큼 반복문을 수행한다. 스택이 비어 있거나 (아직 아무것도 담겨 있지 않거나 이전에 가격이 최하로 떨어져 스택이 모두 비워진 경우), 현재 스택의 맨 꼭대기에 있는 주식 가격이 현재 비교하려는 i번째의 prices[i] 보다 크지 않다면 (주식 가격이 내려가지 않았다는 의미), 스택에 현재 비교하려는 주식을 넣어준다 (Push()). 현재 스택의 꼭대기에 있는 주식의 가격이 더 크다면, 스택 내 주식 가격이 작아지거나 스택이 빌때까지 스택에서 뽑아낸다 (Pop()). 그리고 뽑아낸 주식이 지속된 시간은..
문제 조건 입출력 예제 솔루션 각 학생의 점수를 담을 배열인 score, 답을 저장할 answer, 그리고 가장 많이 맞춘 문제 수를 저장 할 max를 선언한다. pt2, pt3는 2번, 3번 학생이 답을 맞추는 패턴을 저장한 배열이다. 먼저 score 배열을 0으로 초기화 한다. 문제 갯수만큼 반복문을 수행한다. 1번 학생이 답을 맞췄는지 확인한다. 1번 학생은 순차대로 1, 2, 3, 4, 5번을 선택함으로 따로 배열을 만들 필요없이 비교하면 된다. 수식은 i % 5 + 1 인데, 5개를 주기로 패턴이 반복되며 답은 1 ~ 5 까지이므로 + 1을 해준다. 답안을 비교한 점수와 max를 비교하여 갱신한다. 2번 학생이 답을 맞췄는지 비교한다. 2번 학생은 2, 1, 2, 3, 2, 4, 2, 5 패턴으..
문제 조건 입출력 예제 솔루션 스택 자료구조를 사용하였다. why ?) FILO 형식으로 뒤에서부터 진행하고, 신호가 수신된 탑은 고려할 필요가 없어 스택을 사용하면 다루기가 편할거라 생각. 몇 번째 탑이고, 높이 크기가 얼마나 되는지 관리하기 위해 Top 클래스를 정의한다. idx는 현재 비교하려는 탑이 몇 번째 인덱스인지 현재 위치를 의미하는 변수이다. 스택 두개를 만들어 stack은 입력으로 주어진 탑들을 순서대로 집어넣고 다시 꺼내기 위한 변수이며, wait은 이전 탑보다 높이가 큰 탑들을 담아놓기 위한 스택 (자기보다 높이가 큰 탑이 나올때까지 대기) 이다. stack에 현재 탑 정보를 Top 객체로 만들어 Push() 한다. 그리고 처음 answer에 모두 0으로 초기화 (수신이 되지 않는다면..
문제 조건 입출력 형식 입출력 예제 솔루션 링크드 리스트 자료구조를 사용하였다. Why ?) 큐를 사용할까 고민했지만 FIFO 형태이므로, 큐 중간 위치에 있는 데이터를 제거하지 못하기 때문에 큐는 적합하지 않다고 판단하여 링크드 리스트를 채택. 먼저 특이한 상황을 처리한다. 캐시 사이즈가 0 이라면, 캐시에 쌓이는 것이 하나도 없으므로 모두 캐시 미스가 발생한다. 따라서 아래의 반복문을 갈 필요도 없이 총 cities 갯수 x 5를 반환해주면 된다. 캐시 사이즈가 0이 아니라면, cities 갯수만큼 반복문을 수행한다. 대소문자 구분이 없다고 했으므로, cities[i]를 소문자로 바꾼다. (대문자로 바꿔도 무방) 먼저 시간을 5만큼 더해준다. 캐시에 현재 비교하려는 cities[i]가 존재한다면, 캐..
단순한 문자열 검색 문자열 'ACBABCBABC' 에서 'ABC'를 찾는다고 해보자. 단순한 방법은 'ABC'를 한 칸씩 옮기면서 비교하는 것이다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 같다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 다르다. A C B A B C B A B C A B C -> 같다. 문자열 끝까지 진행하며, 여기서는 문자열 패턴 'ABC'가 총 2번 등장하는 것을 알 수 있다. ACBABCBABC 하지만, 이 단순 비교는 ..
문제 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 그렇지 않으면 J를 인쇄합니다. 조건 입출력 예제 솔루션 먼저 문서의 인덱스와 중요도를 가지고 있는 문서 객체를 만드는 클래스를 구현한다. 클래스 생성 이유 ?) 문서의 인덱스와 중요도를 함께 다루기 위해서 (배열 2개를 사용할 경우 굉장히 번거로울 거라 생각). idx는 중요도가 높은 것부터 차례대로 접근하기 위한 인덱스이며, 순차적으로 문서를 뽑아내는 것이므로 큐 자료구조를 사용한다. 중요도가 담겨 있는 priorities 배열을 순서대로 모두 큐에 삽입해준다 (Offer()). priorities 배열을 오름차순 ..
문제 조건 입출력 예제 솔루션 먼저 정답인 answer = 1로 초기화하고 (성공할 수 있다고 가정), 스택 자료구조를 사용한다. Why 스택 ?) 동일한 문자열이 나오면 스택의 Pop()을 이용하여 제거하고, 다음 문자부터 다시 Push() 하면 될 것이라 판단. 문자열 s의 길이 만큼 반복한다. 스택이 비어 있다면, 문자를 스택에 Push() 한다. 스택이 비어 있지 않다면, 동일한 문자인지 비교한다. 스택의 꼭대기 (Top) 문자와 문자열 s의 i번째 문자가 동일하다면, 스택을 Pop() 하여 제거한다. 동일하지 않다면, 스택에 i번째 문자를 Push() 한다. 반복문이 종료된 이후에도 스택이 비어 있지 않다면, 성공적으로 수행하지 못하는 것이므로 answer = 0 으로 바꿔준다. (실패) Cod..
벨만-포드 (Bellman-Ford) ? 다익스트라 알고리즘은 한 시작점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 중 가장 유용한 알고리즘이다. 하지만, 음수 간선이 있는 그래프의 경우 그 정당성이 보장되지 않는다. 벨만-포드의 최단 경로 알고리즘은 이와 같은 문제점을 해결하는 알고리즘이다. 벨만-포드는 다익스트라와 동일한, 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우, 이 또한 알려준다. 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 이것은 BFS를 기반으로 한 번..