매일 꾸준히

BFS는 너비 우선 탐색(Breadth-First-Search)의 약자이고, DFS와 마찬가지로 그래프의 탐색을 위한 알고리즘이다. 시작 정점에서 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 알고리즘이다. 즉 , 깊게(deeply) 탐색하는 것이 아닌 넓게(widely) 탐색하는 알고리즘이며 , 두 노드 사이 최단 경로나 임의의 경로를 알고 싶을 떄 너비 우선 탐색을 선택한다. 너비 우선 탐색의 특징 -직관적이지 않은 면이 있다. (시작 노드부터 시작해서 거리에 따라 단계적으로 탐색한다.) -BFS는 재귀적으로 동작하지 않는다. -어떤 정점을 방문했었는지 여부를 반드시 검사해야 한다 ( 그렇지 않으면 무한루프에 빠질 수 있다.) -BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 ..

https://www.acmicpc.net/problem/1544 1544번: 사이클 단어 사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 www.acmicpc.net 문제 사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다. N개의 단어가 주어졌을 때, ..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 문제 집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다. 2 3 5 2 5 3 3 2 5 3 5 2 5 2 3 5 3 2 각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다. {b,e,i,n}으..

백트래킹으로 시도하다가 시간초과 나서 다른 분들의 코드를 보았다.! 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막..

문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 ..

C++에서 풀기에는 K의 범위가 10^100이여서 long long범위를 넘어간다. 그래서 파이썬으로 풀었다 문제 암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다. 소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다. 따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K와 정수 L이 주..

https://www.acmicpc.net/problem/23028 23028번: 5학년은 다니기 싫어요 2022년 1학기에는 전공 수업이 4과목, 비전공 수업이 3과목이 주어진다. 아리는 전공 2과목, 비전공 2과목을 듣게 되면 전공학점이 66학점, 총 학점이 132학점이 된다. 그래서 총 8학기 안에 졸업을 www.acmicpc.net 문제 5학년은 다니기 싫은 아리는 4학년까지 졸업 학점을 채워 졸업할 수 있는지 궁금해졌다. 아리가 졸업하려면 총 130학점 이상 들어야 하고, 그중 66학점 이상은 전공학점이어야 한다. 아리는 현재 2021년 2학기까지 N학기를 마쳤고, 전공학점 A를 포함하여 총 B학점을 이수하였다. 고민하던 아리는 학교 홈페이지에서 다음과 같은 공지가 올라온 것을 확인했다. 202..

플로이드-와샬을 사용 해야 할 경우! 플로이드-와샬 알고리즘은 "모든 정점 쌍에 대해 최단 거리를 구할 떄 " 사용한다. 즉, 모든 정점의 최단거리를 구하고 싶을 떄 다익스트라나 밸만-포드가 아닌 플로이드-와샬 알고리즘을 사용하면 된다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 map[][]을 계산한다. map[u][v]의 의미는 정점 u에서 정점 v로 가는 최단거리를 나타낸다. 플로이드 알고리즘의 경로와 경유점의 개념 두 정점 u와 v를 이어주는 경로가 있을 때, 이 경로는 항상 u와 v를 지난다. 이 외에도 다른 정점을 거칠 수 있다. 정점 u에서 정점 v로 가는 최단 경로를 D(u,v)라고 하자. 정점 a에서 정점 b로 갈때 5만큼의 비용이 드는데, c,d를 거..

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 ..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net #include using namespace std; int max(int a,int b){ if(a>b){ return a; } else{ return b; } } int arr[100001]; int sum[100001]; int main(void){ int n; cin >> n; for(int i = 0;i> arr[i]; sum[i] = sum[i-1] + arr[i]; } //1) 벌과 벌 사이 꿀통 위치 벌---꿀통----벌 int max_sum = 0; int left = 0; int right = n-1; /* 꿀통이 le..