문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 문제 링크 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 수의 각 자릿수가 등차수열을 이루는 지를 확인하는 ..

개요 우리가 집합이라는 개념을 생각했을 때 보통 아래의 그림처럼 벤-다이어그램으로 생각을 하곤 한다.▼ 그런데 이런 집합이라면 아래와 같이 배열로 표현할 수 있다.▼ 하지만 두 원소가 같은 집합에 있는지를 판단하라고 하면 약간 곤란해진다. A집합에 있는 1 원소와 B집합에 있는 5 원소가 같은 집합에 있는지를 판단하려면 A집합이나 B집합을 다 확인해야한다. A집합에 5 원소가 있는 지 없는 지, B집합에 1 원소가 있는지 없는 지를 확인해야한다. ▼ 배열로 구현하게 되면 집합의 대표를 알아내기가 힘들어서 같은 원소에 대해서 또 확인하게 되면 같은 연산을 계속 수행해야한다. 심지어는 두 집합이 서로소인것을 알아내어 합한다고 했을 때도, 원소를 옮기는 과정에서의 연산도 적지않게 수행된다. ▼ 이런 집합에 대..

개요 프로그래밍을 하다보면 상태를 저장해야할 때가 종종 생긴다. 예를 들면, 내가 주인공 캐릭터가 죽었는지 살았는지를 체크한다거나, 주인공이 공격력 두배 효과를 받고 있다거나, 주인공이 특정 아이템을 갖고 있다거나 등등 … 한 주인공의 상태를 엄청나게 많이 표시해야할 때가 등장한다. 그런데 이 상태들을 표시할 때, 한 상태당 int 하나씩 쓰게 되면 0과 1밖에 쓰지 않는데 불필요한 자원을 쓰게 된다. 그렇다고 0과 1만 쓰는, 1byte도 아닌 1bit 크기의 데이터형식이 존재하지 않는다. 허나 잘 생각해보면, 1bit는 자료형의 기본적인 단위다. 즉, 1bit 크기를 찾을게 아니라, int를 1bit 플래그가 32개 붙어있다고 생각하자는 것이다. int의 각 비트를 플래그로 생각하자는 이야기이다.▼ ..

개요 플로이드-와샬 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 가중치가 음인 그래프는 있지만, 음수 싸이클은 없다. (음수 싸이클이란? 음의 가중치가 더 커서 최단 경로를 계속해서 줄일 수 있는 상태의 간선을 말함.) 벨만-포드와 음의 가중치의 최단 경로를 계산할 수 있다는 점에서 비슷하지만, 플로이드-와샬 알고리즘은 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 즉, 벨만-포드와 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구했다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구한다. 또한 플로이드-와샬 알고리즘은 다이나믹 프로그래밍으로 볼 수도 있다. 알고리즘 알고리즘 분류..

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

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