컴공과고씨

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 간단 정리 방향성 없는 그래프 주어짐. 1번 부터 n 정점까지 최단 거리로 이동함. 조건은 임의로 주어진 두 정점은 반드시 통과해야함. 그리고 한 번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이용가능. 1번에서 n정점으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 길이를 출력하라 경로가 없으면 -1을 출력. 문제 해..

Quick Sort는 배열을 더 작은 하위 배열로 분할하고 해당 하위 배열을 재귀적으로 정렬합니다. 즉, 분할 정복 알고리즘(divide-and-conquer)를 이용한 정렬이라고 볼 수 있습니다. 평균 및 최선의 시간 복잡도는 O(n log n)이고 최악의 시간 복잡도는 O(n^2)입니다. 효율적인 분할 및 무작위화 기술로 인해 버블 정렬 및 삽입 정렬과 같은 다른 정렬 알고리즘보다 빠른 경우가 많습니다. 또한 내부 알고리즘이므로 배열을 정렬하는 데 추가 메모리가 필요하지 않습니다. Quick sort 구현 1. 배열에서 "pivot" 요소를 선택합니다. 이 요소는 배열을 두 개의 하위 배열로 분할하는 데 사용됩니다. 하나는 피벗보다 작은 요소를 포함하고 다른 하나는 피벗보다 큰 요소를 포함합니다. e..

https://hagisilecoding.tistory.com/140 [자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨] * 참고서적 c++ plus data structures * 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다. 리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다. 이 리스트를 두 개로 나눕니다 hagisilecoding.tistory.com 이 글을 보기 전에 위 링크를 먼저 보고 오시는게 좋습니다. 위 글 처럼 sorted 리스트의 가장 큰 문제점은 삽입과 삭제할 때 발생을 합니다. 예를 들면 1,2,3,4,6,7,8,9,10,11,12,13,14 라는 리스트가 있다고 할 때 5..

들어가기 앞서 Linked Queue 구현을 위한 더 쉬운 이해를 위해 스택에 관한 앞 글인 https://hagisilecoding.tistory.com/141 를 보고 오시는게 좋습니다. 큐는 스택과 반대입니다. 스택은 들어간 것이 먼저 나중에 나오지만 큐는 먼저 들어간 것이 먼저 빠져 나온다고 생각하면 됩니다. 그렇기에 구현 할 때도 조금 더 생각을 해주어야 합니다. 스택은 top 변수로 늘려주고 빼주고 하면 되지만 큐 같은 경우는 변수를 두 개 두고 앞쪽 dequeue할 변수 한 개 enqueue할 변수 한 개 총 두개를 컨트롤 해주어야합니다. 문제는 이렇게 하면 Dequeue를 했을 때 낭비되는 칸이 생기게 됩니다. 이런식으로 그래서 %연산을 이용해서 circular(순환) 하도록 만들어 주는 ..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 간단 정리 NxN의 모눈 색종이가 있을때 각 칸에 1 또는 0이 적혀있음. 모든 숫자가 같아 정사각형이 되지 않으면 4등분하여 색종이를 나누어가면서 정사각형이 될 때 까지 나누었을 때 잘려진 흰색 종이와 파란색 종이의 개수를 구하시오. *이 문제는 본문에 있는 그림을 보면 더 쉽게 이해가능. 문제 해결 방법 분할 정복(divide and conquer), 재귀를 써..

Stack stack은 단어가 쌓다 뭐 이런 뜻이죠. 말 그래도 쌓는다 이렇게 이해하면 됩니다. 위 그림 처럼 동전을 쌓는다고 생각하고 원소를 하나씩 push (넣는다) 하면 밑에 부터 쌓이게 됩니다. pop을 하는 것은 원소를 빼는 것이고 stack은 위에서부터 하나씩 빼는 방식을 가지고 있습니다. 스택 클래스는 위 처럼 구성할 것이고 STL 스택을 써보신 분들은 아시겠지만 data type을 stack을 선언할 때 사용자가 정할 수 있습니다. 그것과 똑같이 만들기 위해 template class를 사용하여 data type을 사용자가 설정할 수 있도록 만들었습니다. 그래서 코드를 보시면 template 으로 선언된 것을 볼 수 있습니다. Stack을 구현하는 세 가지 방법이 있습니다. 하나는 배열을 ..

* 참고서적 c++ plus data structures * 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다. 리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다. 이 리스트를 두 개로 나눕니다. 1. 비정렬 리스트 2. 정렬 리스트. 책에서는 class를 사용하여 리스트에 대해 설명하고 있습니다. ItemType() 이 class 경우 두 리스트에서 이렇게 구성이 되어있습니다. 리스트에 원소를 넣을 때 우리는 ItemType() 객체를 넣어주는 것입니다. 우리는 Initialize()를 통해서 value에 값을 초기화 합니다. 즉, value 값이 실제 원소 값이 되는 것이죠. 그 생성한 ItemType() 객체를 리스트에 넣어주는..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 간단 정리 여러 도시가 있고 그 도시를 다닐수 있는 여러 버스가 있다. 시작 도시에서 도착 도시까지 비용을 최소로 하는 비용을 구하여라. 문제 해결 방법 다익스트라 알고리즘을 사용하면 풀 수 있는 문제이다. 다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 한번 어떤 알고리즘인지 보고 오면 어떤 식으로 이 문제..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 간단 정리 N x N 도시에 집과 치킨집이 있음. 한 집과 치킨 집의 거리는 | 집의 행 - 치킨집의 행 | + | 열 - 열 | 이런식으로 계산됨. 각 집과 가장 가까운 치킨 집 사이의 거리를 모두 합한 거리를 도시의 치킨 거리라고 한다. 문제에 M이 주어지는데 M개 만큼 치킨 집을 폐업했을 때 도시의 치킨 거리 가장 작게 되는 도시의 치킨 거리를 구하시오. 문제 해결..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 간단 정리 n * 3 개의 행렬 칸이 있고 각 칸에는 숫자가 적혀 있음. 맨 위 부터 출발 하여 내려오는데 바로 아래와 한 칸 대각선으로만 이동 가능함. 이 때 얻을 수 있는 최대, 최소 점수를 구하시오. 문제 해결 방법 이 문제 같은 경우 위에서 내려온다는 생각을 하지말고 도착할 칸이 위에서 내려오는 점수를 받는 다고 생각하면 쉽다. 이런식으로 첫번째 칸은 점수를 바로 위와 그 옆에서 밖에 올 수 없기 ..