Algorithm

[백준 1688] 지민이의 테러 C++

1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있 www.acmicpc.net 기하학, 선분 교차, 레이 캐스팅 알고리즘 1. 문제 해결 아이디어 많은 예외 케이스 때문에 10번넘게 틀린 문제... 오래 고민한 만큼 정이 들어버린 문제다.. [백준 17387] 선분 교차 2 C++ 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을....

[백준 16197] 두 동전 C++

16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net DFS, BFS 1. 문제 해결 아이디어 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다. 문제에 나와있는 그대로 구현했다. DFS를 통해서 잘못된 길에 들어선 뒤에 백트래킹이 가능하게 구현을 하였다. memset(Map..

[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 C++

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 다이나믹 프로그래밍, 투 포인터 코딩꿈나무 조정현 : 네이버 블로그 빠르게 꾸준히 blog.naver.com 정현님의 추천문제를 풀어보았다! 1. 문제 해결 아이디어 [백준 1644] 소수의 연속합 C++ 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학, 두 포인터, 정수론 1. 문제풀이 아이디어 에라토스테네스의 체를 이용해서 N까지의 소수를 배열에 순서 hye..

단어 제한 끝말잇기 (WORDCHAIN)

algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 www.algospot.com DFS, 오일러 서킷, 오일러 트레일 1. 문제 해결 아이디어 끝말잇기에 사용되는 단어들이 주어진다. 주어진 단어 모두를 사용해서 끝말잇기를 만들면 된다. -> 오일러 회로임을 알 수 있다. 단어를 모두 사용해서 다시 시작점으로 돌아올 수도 있고, 시작점이 아닌 지점에서 끝날 수도 있다. 다시 시작점으로 돌아오는 경우는 오일러 서킷이라고 할 수 있다. 모든 간선을 한 번씩 통과하지만 시작점이 아닌 다른 정점에서 끝나는 경로를 오일러 트레일 이라..

[백준 1199] 오일러 회로 C++

1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net DFS, 오일러 1. 문제 해결 아이디어 오일러 서킷 오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접 hyeo-noo.tistory.com 이 문제는 오일러 서킷을 구하는 문제이다. 위 링크의 알고리즘에 따라서 구현을 하고, 간선정보를 받은 후 정점에 대한 degree가 홀수인 정점이 존..

오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다. v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다. 2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다. u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다. 한 정점에 인접한 간선의 개수를 degree라고 하자. 오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로..

[백준 2162] 선분 그룹 C++

2162번: 선분 그룹 첫째 줄에 N(1≤N≤3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 www.acmicpc.net 선분 교차 알고리즘, Union-Find 1. 문제 해결 아이디어 [백준 17387] 선분 교차 2 C++ 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을.. hyeo-noo.tistory.com 위 문제에서 사용했던 선분 교차 알고리..

[백준 1405] 미친 로봇 C++

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트래킹 1. 문제 해결 아이디어 로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다. 초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다. 움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다. 이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌) 결과는 단순한 경우를 찾으므로 1-..

[자료구조] Single Linked List 예제 코드 #2 (C)

Single Linked List 구현하기 #2 따로 list의 크기를 입력받는 상황은 구현하지 않고 정적으로 이미 만들어진 노드에서 circular list로 만들고 검색하는 기능을 구현했다. 구현을 위한 메서드들 struct Node : list의 한 노드를 구성하는 구조체 struct Node* Create(int data) : list의 새 노드를 만드는 함수 struct Node* Insert(struct Node* current, int data) : current 라는 노드 뒤에(after라는 노드 앞에) 노드를 새로 만들고 data값을 설정 후 노드를 반환하는 함수 void destroy(struct Node* destroy, struct Node* head) : head 노드부터 탐색해서..

[백준 6543] 그래프의 싱크 C++

6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net 강한 연결 요소 코사라주 알고리즘 1. 문제 해결 아이디어 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 이전에 포스팅 했던 문제에서 사..