개요 가중치가 있는 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 최단 경로 문제라고 하면 다익스트라와 같은 작업을 수행하고, 심지어는 다익스트라가 더 빠르기까지 하다. 하지만 벨만-포드 알고리즘의 의의는 다익스트라 알고리즘이 처리하지 못하는 음수인 간선을 처리할 수 있다는 것이다. 그래서 음수인 간선이 등장하는 경우에는 벨만-포드 알고리즘을 사용한다. 알고리즘 벨만-포드 알고리즘에서 중요한 부분 벨만-포드 알고리즘에서 가장 중요시 해야할 부분은 음의 싸이클이다. 벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 값이 더 작은 값이 나오면 갱신하는 식으로 진행된다. 그런데 음의 싸이클이 등장하게 되면, 한 번 순회를 돌 때마다 값이 계속 작아져서 무한히 갱신하게 된다. 그래서 우리는 순회 횟수를 V - ..

개요앱 개발을 하다보면 해상도 대응이 상당히 까다롭다.디자이너가 준 화면을 구현하고, 실제 기기에서 보면 뭔가 이상할 때가 많다.이는 해상도가 맞지 않아, UI 배치가 조금씩 틀어지면서 생기는 문제다. 각 기기마다 해상도가 다르기 때문에 모든 기기에 맞게 코드를 작성하는 것은 어렵다.이를 위해 iOS에선 Auto Layout과 같은 방법론이 등장했다. 하지만 Flutter에서는 어떨까? Flutter에서도 padding을 사용하여 CSS나 iOS와 같이 해상도 대응을 할 수 있다.일반적으로는 이게 정석인데, 약간의 꼼수를 사용할 수 있다. 바로 ScreenUtil 패키지를 이용하는 것이다.  ScreenUtil 이란?ScreenUtil 패키지는 해상도를 자동 대응해주는 패키지이다.기준 화면을 설정하면, ..

Spacer란? Spacer는 Row와 Column과 같은 Flex Container (이는 뒤에서 알아볼 것이다.)의 공간을 조절하는 빈 공간을 만들어주는 위젯이다. 이름 그대로 Space + er로 공간을 만들어주는 위젯이다. Spacer 위젯은 추가적인 공간을 잡는 위젯이기 때문에 Flex container안에 있는 Flex.mainAxisAlignment를 MainAxisAlignment.spaceAround, MainAxisAlignment.spaceBetween, MainAxisAlignment.spaceEvenly 로 설정하면 추가 공간을 모두 차지했으므로 재배포할 공간이 남아 있지 않아 가시적인 효과가 없다. 즉, Spacer는 MainAxisAlignment 속성을 모두 무시한다는 것이다..

개요 Flutter로 크로스 플랫폼 앱 개발을 하다보면, 아래와 같이 `const`를 붙이라는 경고메세지가 등장한다. ▼ 이는 Error가 아닌 단순 Warning이라서 지키지 않아도 프로그램이 컴파일 되는 데에는 큰 문제가 없다. 하지만 아래에 파란줄이 남은 것을 볼 때면 굉장히 찝찝해져서 const를 붙이지 않고 넘어갈 수 없다. ▼ 이쯤되면 의문이 하나 생긴다. "도대체 왜 `const` 키워드를 붙이라고 권장하는걸까?" 프로그래밍 문법을 배울 때 const는 상수라고 배운다. 그리고 상수는 변하지 않는 값을 선언할 때 사용한다고도 배우는데, Dart에는 `const`외에 `final`이라는 키워드가 존재한다. 변하지 않는 값을 선언하는 것을 권장하는 것이라면 `const`가 아니라 `final`을..

문제 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. 두 개의 양의 정수를 나타내는 비어 있지 않은 두 개의 연결 리스트가 제공된다. 숫자는 역순으로 저장되며, 각 노드에는 단일 숫자가 포함..

문제 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 예제 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, ..

문제 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 문제 링크 1152번: 단어의 개수 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백..

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 ..

개요 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 그러나 음의 간선을 포함할 수 없다. 음의 간선을 포함하려면 벨만-포드 알고리즘을 사용해야한다. 하지만 현실에는 음의 간선이 존재할 수 없기도 하고, 그게 아니어도 양의 간선만을 비교하는 상황에서도 다익스트라 알고리즘이 벨만-포드 알고리즘보다 빠르기 때문에 다익스트라 알고리즘을 선호하는 편이다. 알고리즘 알고리즘 분류와 특징 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리가 단일 대상의 거리를 말하는 게 아니라 여러 개의 최단 거리의 합으로 이루어져 있기 때문이다. 거대한 최단 거리가 있다고 생각하..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 4 × 4 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 입력 첫째 줄에 정수 N, r, c가 주어진다. 출력 r행 c열을 몇 번째로 방문했는지 출력한다. 제한 1 ≤ N ≤ 15 0 ≤ r, c < 2N 문제 링크 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. ..