본문 바로가기
반응형

알고리즘/BOJ

2581번 2581번 - 소수 에라토스테네스의 체로 풀 수 있다. 소수값들을 구하고, 범위 안의 소수들의 합과 최소 소수를 구하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include#includeusing namespace std; bool prime[10001];void era(){ for (int i = 2; i*i n >> m; memset(prime, true, sizeof(prime)); prime[1] = false; era(); int sum = 0, k; for (int i = m; i >= n; i--) { if (prime[i]) { k = i; sum += i; } } if (su.. 더보기
1743번 1743번 - 음식물 피하기 단순히 DFS를 돌려서, 가장 많이 인접한 값을 찾는 문제. 매번 void 형 함수를 썼는데, 리턴값을 int 로 하는 연습도 할 겸 문제를 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#includeusing namespace std; bool check[101][101];char map[101][101];int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 }; int n, m, k, ans;int dfs(int x, int y){ int ret = 1; .. 더보기
2617번 2617번 - 구슬 찾기 DFS 알고리즘 분류 문제로 풀었는데, 이전에 플로이드로 풀었던 문제랑 비슷했다. 만약 DFS나 BFS로 풀려면 , 한 노드당 두번씩 돌려서 작은 구슬, 큰 구슬의 갯수를 구해주면 된다. 구슬의 크기가 중간일 확률이 아예 없으려면, 큰 구술이 과반이 넘거나, 작은 구슬이 과반이 넘어야 한다. 처음에 나는 이전에 풀었던 문제와 비슷하게, 큰구슬+작은구슬이 과반이 넘어가면 정답으로 체크했는데, 이 문제에서는 틀리다. 딱 중간에 있는 구슬의 경우 큰구슬+작은구슬이 과반을 넘지만, 중간이기 때문이다. 또한 짝수든 홀수든 (n/2)+1 이 반절이 된다. 만약 1 2 3 4 네개의 구슬일 경우 2,3 모두 중간이기 때문이다. 따라서 플로이드 값을 비교하면서, small 배열과 big 배열을.. 더보기
2668번 2668번 - 숫자고르기 결국 문제에서 핵심은, 입력값이 노드와 그 노드에 연결되는 노드라고 했을 때 싸이클의 갯수와 싸이클에 포함되는 노드들을 모두 구하면 된다. 싸이클을 구하는 방법은 discoverd 배열과 finished 배열을 이용해서 역방향 간선을 구하면 된다. 어떠한 정점이 발견됐을 때, 이미 발견된 정점이지만 finished 가 false 이면 역방향 간선이 된다.(나의 참고자료에 내 필기가 있음) 이렇게 역방향 간선이 이루어지는 경우, 싸이클을 이루게 된다. 처음에 고민했던 점은 A->B->C->D->B 이런 싸이클이 있을 때, BCD만 어떻게 뽑아낼 것인가를 고민했는데, 그냥 재귀함수가 끝나는 시점에서 싸이클의 시작점을 체크하는 방법으로 문제를 풀 수 있었다. 12345678910111.. 더보기
1325번 1325번 - 효율적인 해킹 A가 B를 신뢰하면, B를 해킹 했을 때 A를 해킹할 수 있다. 따라서 A노드와 B노드를 만들고 B->A로 가는 간선을 추가한 뒤, 모든 노드들에 대해서 DFS를 탐색한다. 그래서 방문할 수 있는 노드가 가장 많은 시작점이 답이 된다. 따라서 간선을 설정하고, 모든 노드를 방문하면서 DFS를 돌린다. 그 후에 가장 방문을 많이 한 지점을 찾아서 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#includeusing namespace std; bool check[10001];.. 더보기
11058번 11058번 - 크리보드 이 문제에 대한 해결을 못봐서 다른 분들의 코드를 봤다. 내가 생각하기에 가장 핵심은, 점화식 D[n] = n번 눌렀을 때, 출력되는 최대값 이라고 했을 때, D[1]=1,D[2]=2,...D[6]=6 이라는 점을 알아차리는 것이다. 이 점을 알아차린다는 것은 결국 N이 7이상일 때 2,3,4 번만을 작동해야 한다는 것을 깨닫는 것과 같다. 따라서 기저 조건으로 N이 1~6까지만 알아낸다면 그 다음은 쉽게 풀 수 있다. N자리 일때, 맨 마지막이 ACV 인 경우, ACVV인 경우, ACVVV인 경우로 나누면 된다. ACVVVV 는 결국 ACVACV 보다 작게 되기 때문에 3가지 경우만으로 계산을 수행하면 된다. 따라서 1. ACV 인 경우, D[N-3]의 2배 값을 갖게 된다.(.. 더보기
2239번 2239번 - 스도쿠 2580번 스도쿠랑 똑같은 문제이다. 다만 입력을 2580은 int 타입으로 받았지만, 이 문제는 char 형으로 받아서 변환하면서 문제를 풀었다. 동일한 로직으로 가로, 세로, 구역의 true,false 를 따져가면서 문제를 풀었다. 또한 정답이 여러개일 경우 작은 81자리의 수가 작은 경우로 하라고 했는데, 재귀함수의 for문이 1부터 시작하기 때문에 문제가 될 것이 없다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091.. 더보기
1405번 1405번 - 미친 로봇 처음에 문제를 제대로 안 읽고, 단순하지 않은 경로를 구하다 보니 시간초과가 발생했다. 근데 단순한 경로를 구하니까, 시간초과 없이 AC를 받았다. 나는 그냥 N제한이 최대 14이기 때문에, 60x60 의 충분히 큰 맵을 만들었다. 그리고 그냥 25,25를 시작으로 움직이도록 설정하였다. 그래서 다음에 방문할 지점이 한번도 방문하지 않은 곳 일때만 로봇이 움직이도록 구현했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include#.. 더보기
반응형

티스토리툴바