문제 문제 링크 - https://www.acmicpc.net/problem/11501 접근법 정답을 얻기 위해서는 아래와 같이 계산하면 된다. 현재 주식 가격 이후에 더 비싼 가격이 있으면 -> 오늘 주식을 산다 현재 주식이 남은 주식 가격 중 가장 비싼 가격이면 -> 현재까지 구매한 주식을 모두 판다 앞으로 더 비싼 주식 가격이 없으면 -> 아무것도 하지 않는다 문제는 이를 구현하는 방법인데, 처음에는 단순히 (주식 가격) 배열의 앞에서부터 순회하며 계산을 시도했다. 코드는 아래처럼 될 것이다. // main()에서 입력 처리 후 solution을 부르도록 작성 public static int solution(final int days, final int[] prices) { PriorityQueue..

문제 문제 링크 - 프로그래머스 그렇다고 합니다. 무지가 갑자기 얄미워보이는 마법의 코테 결국 정리하면 0, 1, …, n초 동안 주어진 음식을 먹는데 k초뒤에 어떤 음식을 먹고있을지 출력하는 문제이다. 단순하게 k번 루프를 돌리면 답이 나오긴 하곘지만 입력 범위가 엄청 크기 때문에 다른 방법을 써야 될 것 같았다. 풀이 방법 그래서 처음에 생각한 방법은 이렇다. LinkedList에 주어진 음식(섭취에 걸리는 시간)들을 모두 넣어 오름차순으로 정렬 정렬되기 이전 순서대로 ArrayList로도 하나 만들어두고 두 list가 같은 객체들을 참조하도록 해준다 루프안에서 현재 count를 기억해두고 현재와 동일한 시간을 갖는 음식을 removeFirst() - O(1) 으로 제거 이때 음식의 시간을 0으로 변..

배경 넥스트스텝의 학습테스트로 배우는 Spring 과정을 수강하고 있는데, 과정 진행 중 controller 패키지의 DTO를 어떤 계층까지 사용하면 좋을지에 대한 고민이 들었다. 처음엔 간단하게 생각했지만 생각보다 고민할 내용이 많았어서 고민한 내용과 결론을 정리해보려고 한다. DTO란 먼저, DTO는 Data Transfer Object의 약자로 말그대로 계층 간에 데이터를 주고 받기 위해 사용하는 객체이다. 보통 비지니스 로직은 두지 않고 필드와 그에 대한 getter와 생성자 등만 구현해두고 사용하는 경우가 많다. 예를 들어 아래와 같은 객체가 DTO이다. @NoArgsConstructor @Getter public class PlayRequestDto { private String names; ..

문제 문제 링크 풀이 문제를 푸는 여러 가지 방법이 있을 것 같았는데 간단한 방법으로 문제를 풀었다. 입력으로 간선 정보가 주어지므로 순회를 통해 하나씩 간선을 제외하고, 제외된 간선에 속한 노드를 각각 시작점으로 하여 그 시작점과 연결되어 있는 노드들의 합이 몇 개인지 카운트한다. 그리고 그렇게 카운트된 두 값의 차의 절댓값을 구한다. 이렇게 구한 절댓값의 최솟값을 계속해서 갱신해가면 모든 간선을 순회했을 때 가장 노드의 차이가 적을 때의 값을 구할 수 있다. 예를 들어 입력이 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 라고 하면, 가장 먼저 [1, 3] 간선이 선택될 것이고 (그래프에서 해당 간선을 제외) 1번과 3번 노드를 분리해놓고 1번과 3번으로부터..

문제 문제 링크 풀이 예를 들어 phone_book 배열이 ["12","123","1235","567","88"] 처럼 주어졌을 때 1235에 12가 포함되므로 접두사가 되며 false가 정답이 된다. 이를 단순하게 확인하려면 모든 원소에 대하여 모든 다른 원소와 비교하면 문제는 해결되지만 시간복잡도가 O(n^2)이 되어 효율성 테스트에서 오답이 나오게 된다. O(n)에 문제를 해결하려면 한번만 순회하면서 답을 찾아야 한다. 이를 위해서는 각각의 자릿수에 대하여 더 작은 수가 앞에 오도록 정렬을 해주면 된다. 예를 들어 "12"와 "123" 이 있다면 "12", "123"으로 정렬을 해야 하고 "1"과 "123" 이 있다면 "1", "123"으로, "2"와 "24"와 "134"이 있다면 "134", "2..

문제 문제 링크 풀이 이 문제는 하나의 노드에서 다른 모든 노드까지의 최소 경로를 구하는 문제로 다익스트라 알고리즘을 이용해 풀이할 수 있다. 다익스트라 알고리즘 다익스트라 알고리즘은 아래와 같은 방식으로 동작한다. 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 && 최단 거리가 가장 짧은 노드를 선택 3에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신 끝날 때 까지 3, 4번 과정을 반복 문제의 테스트 케이스에 적용 1번 노드부터 나머지 노드로의 최단 경로를 구하는 문제이므로 출발 노드는 1번으로 설정 간선에 가중치가 없으므로 출발노드와 이웃하는 노드까지의 거리를 1로 설정 방문하지 않은 노드 중 최단 경로가 최소인 2(또는 3)번 노드를 선택 이웃한 노드의 최..

문제 이해 문제 링크 문제에 int[][]computers 배열로 컴퓨터의 연결에 대한 정보가 주어진다. 서로 연결된 컴퓨터들은 하나의 네트워크를 이룬다고 할 때 총 네트워크의 개수를 구하는 문제이다. 예를 들어 연결이 아래와 같다면 네트워크는 2개이고 아래와 같다면 네트워크는 1개가 된다. 풀이 이 문제는 전형적인 그래프 탐색 문제로, visited 배열에 방문한 노드들을 저장하면서 노드를 탐색해나가는데, 새로운 네트워크가 발견될 때마다 해당 네트워크에 연결된 모든 노드를 탐색 상태로 만들어둔다. 이렇게 하면 아직 탐색되지 않은 노드가 발견된다는 의미가 새로운 네트워크를 발견한다는 의미와 같아지므로 그때마다 count를 증가시켜서 총 네트워크의 개수를 확인할 수 있다. public int solutio..

비선형 자료구조 선형으로 표현할 수 없는 데이터를 표현할 때 사용되는 자료구조 예를 들어 지하철 노선도와 같이 하나의 선으로 표현할 수 없는 데이터를 표현하고자 할 때 사용된다 대표적으로 graph가 비선형 구조이다 graph 데이터를 갖는 Node와 Node들을 이어주는 Edge로 구성 Edge는 단방향 / 양방향의 방향성을 가질 수 있다 Edge는 가중치를 가질 수 있다 데이터의 탐색 선형 자료구조와 달리 비선형 구조는 시작과 끝이 모호하다 따라서 먼저 하나의 Node를 탐색하고 해당 Node와 Edge로 연결된 Node들을 탐색한다 연결된 Node들은 Queue / Stack 등에 넣어 탐색을 예약해둔다 원하는 Node를 찾을 때 까지 이 과정을 반복한다 탐색에 사용하는 자료구조에 따른 탐색 순서 ..

문제 문제 링크 풀이 문제 이해 아래와 같은 m x n 크기의 격자가 있을 때, 가장 왼쪽 위 (1, 1) 에서 가장 우측 아래쪽 (m, n) 으로 가는 방법의 개수를 구하는 문제이다. (1,000,000,007로 나눈 나머지 반환) 단, 이때 위 그림에서처럼 웅덩이가 있는 곳은 지나가지 못한다. 입력으로는 격자의 크기 m, n과 웅덩이의 좌표가 [[2, 2]]와 같은 형태로 puddles 이름으로 제공된다. 풀이 방법 문제에서 우측 및 아래로 움직이는 경로만 가능하다고 했으므로 (1, 1)에서 시작하여 (m, n)까지 우측 및 아래로 한 칸씩 이동하며 경로의 개수를 계산한다. 이때, 예를 들어 (3, 3)까지의 경로 경우의 수는 아래와 같이 (2, 3) 까지의 경로 경우의 수와 (3, 2) 까지의 경로..

스프링 시큐리티 ignoring() 아래와 같이 index 페이지에 css를 적용하고 다시 요청을 해보자. Hello #hello { font-size: 100px; } css로 폰트 크기를 변경했음에도 실제로는 반영이 되지 않은 것을 확인할 수 있다. 개발자 콘솔로 요청과 응답 상태를 확인해보면, css 파일을 요청하는데 302(리다이렉션) 코드가 뜨고 login 페이지를 추가로 요청한 것을 확인할 수 있다. 이는 WebSecurityConfigurerAdapter를 통해 시큐리티를 설정할 때 지정한 경로 외의 모든 요청은 인증을 받도록 했기 때문에 정적 리소스를 요청하는 경로 또한 인증을 필요로 하게 되었기 때문에 발생하는 문제이다. 이를 해결하기 위해서는 시큐리티 필터가 적용되지 않도록 ignori..