알고리즘

[C++] 백준 1260번 DFS와 BFS

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있다면 계속해서 탐색하는 것. 시작점이 루트가 되어서 깊이를 1씩 더해가는 방식이다. 보통은 재귀함수를 이용해서 구현한다. BFS의 시간복잡도는 n개의 정점과 m개의 간선이 있을 때, O(n + m)이다. 백트래킹(backtracking) 알고리즘이 DFS에서 파생됐다. BFS란? 너비 우선 탐색(Breadth First Search)라는 그래프 탐색 방법 중 하나로, 이번에 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다. 보통은 자료구조 queue를 이용..

[C++] 백준 1002번 터렛

수학 문제. 예전에 처음 이문제를 봤을 때 원의 접점을 구하는 문제라고 생각 못했던 것 같다. 항상 그렇듯 알고리즘 문제에는 문제에 정말 많은 힌트가 들어있다 여기서도 변수에 r이라는 힌트가 주어져 있다. 그 말은 r은 원의 반지름. 원을 이용해서 풀라는 말이다. 문제 접근 방식 우선 두 원이 있을때 어떤 경우들이 있는지 확인해 보았다. 그렇게 보니 총 여섯 가지가 나오게 되었다. 따라서 두 원의 중점 사이의 거리, 반지름끼리의 합과 차만 알면 이 조건들을 구현할 수 있다. 우선 math.h 라이브러리를 사용해서 두 원의 중점 사이의 거리를 구할때 제곱과 루트 메서드를 사용했다. pow(수, 지수) : 수를 지수승 한다. sqrt(수) : 수에 루트를 씌운다. 메인함수의 시작부분에는 테스트 케이스 수를 ..

[C++] 백준 10989번 수 정렬하기 3

문제에서 입력받는 수의 개수가 1000만개이다. 메모리 제한이 8MB이고, int 자료형이 4byte이므로 모든 수를 저장했을 때 40MB가 돼서 메모리 초과가 난다. 문제 끝에 수가 10,000보다 작거나 같은 자연수라는 조건을 잘 확인했으면 카운팅 소트를 시도해 봤을 것 같다. 뭔가 고민을 많이 안하고 그냥 sort, priority_queue를 사용해서 풀려고 시도하다가 많이 틀렸다. 구현 자체는 크게 어려운 게 없다. 카운팅 소트는 입력을 받으면서 sort하는 알고리즘이다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creati..

[C++] 백준 10282번 해킹

다익스트라의 기초적인 문제. 다익스트라란? 그래프에서 시작점이 있을 때, 시작점에서부터 최단 거리로 한 점씩 이동해보며 해당 점의 최소거리를 확정해 나가는 알고리즘이다. 이 때, 특정 점에서 다른 점들까지의 거리를 구한다는 뜻은 그 특정 점까지의 최단 거리는 확정됐다는 뜻이다. 그래프 이론에서 중요한 알고리즘이다. 이 때 모든 간선치는 양의 정수라고 가정한다. 다익스트라는 머리로는 그리기가 쉬운데, C++에서 구현하려면 복잡한 문법을 많이 알아야 한다. 내 구현 기준으로는 pair : pair 자료형은 특정 자료형 두개를 동시에 저장할 수 있다. make_pair(1, 2) 혹은 {1, 2} 이런 식으로 사용 가능하다. priority_queue : 우선순위 큐는 T 자료형을 container(vecto..

[C++] 백준 15649번 N과 M (1)

백트래킹의 기본적인 문제. 백트래킹 알고리즘을 알고있다면 쉽게 접근할 수 있는 문제이다. 백트래킹이란? 기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다. 이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다. 다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데 이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다. 출처 : https://www.acmicpc.net/board/view/15738 - simm4256님 댓글 참고 쉽게 말해서 내가 길을 가다가 이 길이 아닌거 같으면 돌아가서 다른 길로 가는 것을 뜻한다. 물론 경우의 수가 상당히 많으로 시..

[C++] 백준 1011번 Fly me to the Alpha Centauri

처음 문제를 접근 했을 때 백트래킹으로 풀려고 시도했다. 재귀함수로 모든 경우를 돌면서 최소로 접근할 수 있는 것으로 계속해서 갱신하려고 했다. 구현은 했는데, 메모리 초과가 나면서 풀지 못했다. 단계별로 풀어보기에서 발견한 문제였는데, 분야가 수학이였다. 결국 조금 도움을 얻고자 게시판을 조금 검색해서 규칙성이 있다는 것을 얼핏 보았다. 그래서 이 규칙성을 가지고 어떻게 구현을 해야할까 고민했지만 결국 해답을 얻지 못했다. 글 읽기 - 풀이 정리해 보았습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 그러다가 게시판을 찾던 중 이런 글을 발견했고, step마다 갈 수 있는 거리가 정해져 있다는 것이였다. 이동 횟수 과정 이동 거리 1 1 1 2 1 1 2 3 1 2 1 4 4 1..

[C++] 백준 1436번 영화감독 숌

처음에 이 문제를 봤을 때 문제를 처음 봤을 때 666, 1666, 2666 ... 이런식으로 흘러가는 건 이해를 했다. 근데 너무 쉬워서 그냥 N - 1 출력하면 되는 게 아닌가 생각했는데 아무리 생각해도 너무 쉬워서 문제를 계속 읽었다. 함정은 6이 연속으로 3번 들어가면 그게 영화의 번째수가 된다는 것. 7번째는 따라서 6666이 아니라 6660이 된다는 것이다. 접근한 방식 처음에는 모든 경우의 수를 나누려고 했다. 맨 처음에는 모든 경우의 수를 다 생각하려고 했다. 그러다 보니 문제가 고려할 부분도 상당히 많아졌고, 맞았다고 생각해도 틀렸습니다 가 나왔다. 결국 이 방법으로 1, 2시간 고민하다가 이건 아닌 것 같아서 다 지우고 새롭게 생각했다. 1000씩 더하는 게 아니라 1씩 더해봐서 6이 ..

[C++] 백준 1920번 수 찾기

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다. big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다. STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다. 이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다. head와 tail (보통 left와 right로 표현하는 것 같다.) 그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다. 물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다. (사실 STL 없이 sort하라고 하면 정말 답없을 것 같다..

[C++] 백준 1018번 체스판 다시 칠하기

오랜만에 풀어보는 알고리즘 문제였다. 어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다. 처음 이 문제를 봤을 때 내가 접근했던 방식은 백트래킹을 생각했었다. 그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다 push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다. 그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다. 후에 접근한 방식 문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다. 즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다. 좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다. 이렇게 하면 모든 경우의 수를 다 고려할 수 있다. 보드를 나타내는 변수, n과 m을 나타내는 변수..