boj

[백준 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..

[백준 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가 홀수인 정점이 존..

[백준 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-..

[백준 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 이전에 포스팅 했던 문제에서 사..

[백준 1708] 볼록 껍질 C++

1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net Convex hull jarvis march와 graham scan 알고리즘은 그림도 없고, 설명도 많이 부족하니 다른 분들의 글을 참고해주세요 코드는 determinant를 사용한 풀이입니다 1. 문제 해결 아이디어 Convex hull 문제를 해결하기 위한 대표적인 2가지 알고리즘에는 Jarvis march(gift wrapping) 알고리즘 Graham scan 알고리즘 위 2개가 있다. Jarvis march(gift wrapping)..

[백준 17387] 선분 교차 2 C++

17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을 공부했다. 1. 문제 해결 아이디어 먼저 두 선분이 교차하는 경우를 알아보자 l1선분의 p1, p2벡터에서 l2선분의 p1으로의 방향과 p1, p2벡터에서 l2선분의 p2로의 방향이 서로 다르다면(한 점이 선분에 포함된 경우 포함) 반드시 두 선분은 교차한다. 두 선분의 직선의 방정식을 구해서 교차하는 한 점을 구하면 선분이 교차하는지 알 수 있지 않을까요? 알 수 없다 아래 두 선분을 보자 l2선분을 직선으로 만들면 l1과 교차하게된다. 하지만 l1과 l2..

[백준 2150] Strongly Connected Component C++

2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 강한 연결 요소 ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다. 1. 문제 해결 아이디어 위와 같은 그래프를 Graph라고 하자 Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다. Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기) DFS를 하면서 각 정점의 finis..

[백준 1600] 말이 되고픈 원숭이 C++

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 1. 문제 해결 아이디어 이동할 수 있는 방향이 동서남북 외에도 체스의 말(house)이 움직일 수 있는 8방향이 추가된 문제이다. 처음엔 그냥 8방향만 추가해 주고, 말이 움직이는 방향을 먼저 탐색해 주면 풀리겠지 해서 빠르게 틀렸다. [백준 14442] 벽 부수고 이동하기2 C++ 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 ..