알고리즘
-
[C++] pair, tuple 보다 편한게 구조체(Struct) ?프로그래밍/C++ 2020. 5. 8. 23:13
요약 : pair 와 tuple 보다 구조체(Struct) 를 사용하면 보다 효율적이고 직관적인 알고리즘 코딩이 가능합니다. 우선 pair 와 tuple 의 장단점을 조금 생각해보자면 pair는 원소의 접근이 편하지만 공간이 두 개로 한정적입니다. tuple은 공간이 무한하지만 접근이 불편합니다. 이러한 이유에서 저는 상황에 따라서 사용했습니다. 그러다가 최근에 구조체(Struct)를 사용하게 됬습니다. 구조체는 이름만으로도 무겁고 귀찮게 느껴집니다. 예를 들어 봅시다. 왼쪽, 오른쪽, 위, 아래의 4가지 정보를 한 세트로 하는 알고리즘을 구현한다고 생각해봅시다. 아래의 두 가지 구현에서 느끼셔야 할 부분은 세 가지 입니다. 1. 구조체 구현이 얼마나 간단한가. 2. 원소 추출이 얼마나 간편한가. 3. ..
-
[Python] 벌써 백준문제 풀어보기프로그래밍/Python & Ruby 2020. 3. 4. 15:05
프로그래밍을 공부하다 보면 한 번쯤 들어보는 단어 백.준. 아마 이미 알고 있으신 분들이 많겠죠!! 맞습니다 코딩 문제들을 푸는 사이트인데요 앞에서 두 개의 글만 보고 저희는 백준에 올라와있는 문제를 꽤 많이 풀 수 있게 됐습니다. https://www.acmicpc.net/problem/2557 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 마치 RPG 게임의 시작 마을과도 같은 Hello World 이거 하나만 출력해주면 답이 해결됩니다. 우리는 이미 입출력을 할 줄 압니다. print("Hello World!") 너무 간단하게 첫 번째 문제가 해결됐습니다. ※ 제출방법은 왼쪽 상단에 을 클릭한후 언어를 Python 3 으로 ..
-
[알고리즘] 집합 찾기(Union Find)프로그래밍/알고리즘 2019. 6. 5. 20:17
List 1. 연결 리스트를 이용한 집합 찾기 2. 배열을 이용한 집합 찾기 3. 트리를 이용한 집합 찾기 4. 연산의 효율을 높이는 법 ※ 코드구현은 생략 연결 리스트를 이용한 집합 찾기 연결리스트를 이용한 표현에서 집합의 원소는 노드로 표현이 됩니다. 각 노드에는 원소를 저장하는 필드, 다음 원소와 대표 원소를 기리키는 두 개의 포인터가 있습니다. 다음 원소를 가리키는 포인터를 통해 집합의 모든 원소들이 연결됩니다. 여기서 대표 원소는 각 집합의 가장 앞에 있는 원소를 의미합니다. 그리고 각 집합에는 마지막 원소를 가리키는 tail 변수 라는것이 존재합니다. 이 변수는 두 집합을 합칠 때 이용됩니다. 하나의 원소 x 만을 갖고 있는 집합이 있다고 가정해봅시다. 연결 리스트의 한 노드의 구성은 오른쪽 ..
-
[Greedy] BOJ 2217 번 : 로프백준 문제풀이/etc 2019. 6. 3. 22:30
문제 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다. 입력 첫째 줄에 정수 N이 주어진다. 다..
-
[알고리즘] 탐욕적 기법(Greedy Algorithm)프로그래밍/알고리즘 2019. 5. 29. 16:02
Goal 1. 탐욕적 기법(Greedy Algorithm)의 개념 2. 탐욕적 기법(Greedy Algorithm)의 특징 3. 탐욕적 기법(Greedy Algorithm)의 구현 서론 가장 유명하지만 가장 기초적이어서, 알고리즘에 입문하기 가장 좋은 녀석입니다. 접근법이 굉장히 직관적이고 단순하기 때문에 알고리즘 대회, 코딩 테스트에서 적지 않게 볼 수 있습니다. 그래서 저는 그리디 알고리즘 문제를 적어도 10 문제 정도는 풀어보고 다른 알고리즘을 풀어보시는 걸 추천드립니다. 왜냐하면 10문제 정도 풀어보시면, 내가 생각하는 것을 코드로 구현하는 능력과 문제를 직관적으로 보는 능력이 생기기 때문입니다. 개념 서론이 길었습니다. 탐욕적 기법(Greedy Algorithm), 욕심쟁이 기법 혹은 그냥 그리..
-
[Greedy] BOJ 4796 번 : 캠핑백준 문제풀이/GREEDY 2019. 5. 29. 00:15
문제 보기 정말 작심삼일이라고 고작 8일하고 포기했던 1일 1백준을 다시 시작합니다... 정말 직관적이고 쉬운 문제를 풀면서 자신감을 키우기 위해 그리디문제를 가져왔습니다. 풀이 연속하는 20일중 10일을 사용할 수 있다 .... 이런 경우에 캠핑을 가장 많이 사용하기 위해서는 어떻게 해야될까요? 당연히 휴가 시작날짜부터 바로 캠핑을 시작하는 것이 가장 많이 사용하는 방법일겁니다. 그렇게 되면 휴가 28일중 첫날부터 사용하여 연속하는 20일 동안 총 10일을 사용할수 있을것입니다. 그리고 남은 8일은 다시 연속하는 20일이 되기 때문에 사용횟수가 초기화되서 8일 모두 사용할 수 있게 됩니다. 이러한 상황을 이제 코드로 구현해봅시다. 이러한 Case 의 번호를 저장할 변수 a 를 선언합니다. 연속적인 연산..
-
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)프로그래밍/알고리즘 2019. 5. 26. 15:45
Goal 너비 우선 탐색(BFS, Breadth-First Search)의 개념 너비 우선 탐색(BFS, Breadth-First Search)의 특징 너비 우선 탐색(BFS, Breadth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색은 시..
-
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)프로그래밍/알고리즘 2019. 5. 23. 11:51
Goal 깊이 우선 탐색(DFS, Depth-First Search)의 개념 깊이 우선 탐색(DFS, Depth-First Search)의 특징 깊이 우선 탐색(DFS, Depth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 미로를 탐색하는 ..