전체 글
-
이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프 가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자. 만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장..
[최단경로] 01.최단경로를 위한 알고리즘 소개이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프 가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자. 만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장..
2022.09.01 -
이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자. 위상정렬 알고리즘이란? 위상정렬(位相整列: Topological Sorting)이란 노드 서로간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다. 그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(directed acyclic grapy: 비순환의 유향 그래프)에서만 의미가 있다. 즉 닭이 먼저인지, 달걀이 먼저인지 인것 처럼 선행 요소를 알 수 없는 경우는 사용할 수 없다. 과..
[위상정렬] 1. 알고리즘 이해이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자. 위상정렬 알고리즘이란? 위상정렬(位相整列: Topological Sorting)이란 노드 서로간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다. 그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(directed acyclic grapy: 비순환의 유향 그래프)에서만 의미가 있다. 즉 닭이 먼저인지, 달걀이 먼저인지 인것 처럼 선행 요소를 알 수 없는 경우는 사용할 수 없다. 과..
2022.08.29 -
BJ S1 1342 행운의 문자열 문제링크 https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/LIBUyTyZ-F0 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼..
[BJ]1342. 행운의 문자열BJ S1 1342 행운의 문자열 문제링크 https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/LIBUyTyZ-F0 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼..
2022.08.14 -
알고리즘 문제를 풀다보면 양의 정수라는 표현과 자연수라는 표현이 나온다. 양의 정수는 명확한데 자연수가 애매한 구석이 있어서 정의하고 가보자. 정수의 분류 정수는 양의 정수, 음의 정수, 0으로 구분된다. 따라서 양의 정수에는 0이 포함되지 않는다. 땅땅땅. 자연수 자연수에 0이 포함되는지는 "그때 그때 달라요"이다. ㅜㅜ 수학의 범위가 광범위해서 특정 수학(집합론, 이산수학 등)에서는 0을 포함하기도 하고 일반적으로는 포함하지 않는다. 하지만 알고리즘 문제에서는 대부분 0을 포함하지 않는 경우가 많다.
자연수는 0을 포함하는가?알고리즘 문제를 풀다보면 양의 정수라는 표현과 자연수라는 표현이 나온다. 양의 정수는 명확한데 자연수가 애매한 구석이 있어서 정의하고 가보자. 정수의 분류 정수는 양의 정수, 음의 정수, 0으로 구분된다. 따라서 양의 정수에는 0이 포함되지 않는다. 땅땅땅. 자연수 자연수에 0이 포함되는지는 "그때 그때 달라요"이다. ㅜㅜ 수학의 범위가 광범위해서 특정 수학(집합론, 이산수학 등)에서는 0을 포함하기도 하고 일반적으로는 포함하지 않는다. 하지만 알고리즘 문제에서는 대부분 0을 포함하지 않는 경우가 많다.
2022.08.09 -
BJ G3 10986 나머지 합 문제링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/siBSDIbXZCU 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고..
[BJ]G3 10986. 나머지 합BJ G3 10986 나머지 합 문제링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/siBSDIbXZCU 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고..
2022.08.04 -
이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자. 피보나치! 피보나치 수열 구하기 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. ko.wikipedia.org 피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀..
[재귀]05. 메모이제이션(memoization)이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자. 피보나치! 피보나치 수열 구하기 피보나치 수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. ko.wikipedia.org 피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀..
2022.08.01