2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 연속으로 3잔을 모두 마실 수 없다는 점을 유의해서 풀면 되는 문제이다. 이제까지 마신 최대 포도주의 양을 계산하고, 연속으로 마신 잔의 수에 따라 현재 위치에 있는 포도주를 마실지 말지 결정하는 것이 DP 문제에서 나오는 자주 나오는 로직이여서 DP를 사용하여 문제를 풀 수 있다고 생각할 수 있었다. 각 위치의 포도주의 양을 담은 배열을 arr라고 하고 dp[i] = 0~i번째 위치에 있는 포도주까지 고..

1. 부분 수열과 증가하는 부분 수열이란? 부분 수열 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열을 의미한다. 만약 { 3, 2, 5, 2, 3, 1, 4 } 라는 수열이 있다면 {3}, {2}, {2, 5}, {3, 5, 3, 1} 등이 해당 수열의 부분 수열이 되며, 수열 자체도 자기 자신의 부분 수열에 포함된다. 증가하는 부분 수열 증가하는 부분 수열은 부분 수열들 중에서도 그 수가 오름차순으로 증가하는 부분 수열을 의미한다. 위에 있던 수열의 증가하는 부분 수열은 {2, 5}, {2, 3, 4} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다. 이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 문제 설명 예제 1에서 1번부터 5번 회원의 점수는 각각 3점, 2점, 2점, 2점, 3점이다. 그러므로 가장 작은 점수는 2점이 되고, 점수가 2점인 2, 3, 4번 회원 총 3명이 회장 후보가 되는 것이다. 2. 구현 아이디어 1 - 틀렸습니다. 1. 현재 노드에서 가장 거리가 먼 노드까지의 거리가 해당 회원의 점수가 된다. 2. 모든 회원의 점수를 배열에 저장하고, 배열의 최솟값(=score)을 찾는다. 3. 값이 score인 원소의 index를 ca..

1. 들어가며 우리는 평소 스프링 부트 프로젝트를 만들 때 Controller, Service, Repository 크게 이 3가지 계층으로 나누어 아키텍처를 구성한다. 하지만 프로젝트를 하다 보면 문득 이런 생각이 들어보았을 것이다. 다른 방법으로 프로젝트 아키텍처를 구성해볼 수는 없을까? 이번 포스트에서는 우리가 가장 흔하게 사용하는 계층형 아키텍처부터 시작해서 클린 아키텍처와 헥사고날 아키텍처에 대해 훑어보며 다양한 아키텍처에 대해 살펴보자. 2. 아키텍처란 무엇일까? IEEE 국제 표준(ANSI/IEEE Std 1471-2000)에서는 소프트웨어 아키텍처의 정의를 다음과 같이 설명한다. 구성요소들간의 관계, 환경, 설계와 발전을 관리하는 원칙으로 이루어진 시스템의 근본적인 구조 클래스, 파일, 컴..

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 - 메모리 초과 문제 설명에 있는 예제 입력에 그린 것처럼 컴퓨터끼리의 관계를 그래프로 표현할 수 있고, 여기서 s초를 간선의 값이라고 생각하면 최초로 해킹 당한 컴퓨터부터 다른 컴퓨터까지의 최단 경로를 탐색하는 문제라고 생각할 수 있다. 한 노드에 대해서만 최단 경로를 생각하면 되기 때문에 다익스트라 알고리즘을 사용해보자. 다익스트라 알고리즘의 개념에 대해서는 아래 포스트에 정리해두었다. 최단거리 알고리즘 - 다익스트라 & 플로이..

1. 최단거리 알고리즘이란? 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 주로 그래프를 이용하여 표현하며 각 지점은 노드, 지점 간 연결선은 간선으로 표현한다. 이번 포스트에서는 대표적인 최단거리 알고리즘인 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 소개하겠다. 2. 다익스트라 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 음의 간선이 없을 때 정상적으로 동작하며, 매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류된다. 음의 간선 - 0보다 작은 값을 구하는 간선 음의 간선이 포함되었을 경우에는 벨만 포드 알고리즘을 사용해야 한다. 다익스트라 알고리즘의 구현 🍥 각 노드에 대해 현재까..