본문 바로가기
반응형

알고리즘/BOJ

5014번 5014번 - 스타트 링크 간단한 BFS 문제였다. 각 층을 정점으로 위 아래로만 움직일 수 있는 간선이 존재한다고 생각하고 풀었다. dist 를 구해야했기 때문에, visited 는 따로 안쓰고 dist 로 모두 구현했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#include#includeusing namespace std;bool visited[1000001];int dist[1000001];int ans = 0;int dx[2] = { 1,-1 };int main(){ int F, S, G, U, D; cin >> F >>.. 더보기
3108번 3108번 - 로고 나는 이 문제를 연결요소의 갯수를 구하는 문제로 접근했다. 결국 DFS를 통해서 한붓그리기가 가능하면 거북이가 붓을 뗄 필요가 없기 때문이다. 그래서 처음에 makeGraph 함수를 통해서 각 점들을 정점으로 간선들을 모두 연결해줬다. 이 과정에서 음수 값들을 제거하기 위해 모든 점들에 500을 더해줬다. 그래서 모든 점을 DFS 로 순회해서 연결요소의 갯수를 풀면 된다. 단 주의해야 할 점은 , 거북이가 시작점에 있느냐 있지 않느냐의 문제이다.. 이 부분에서 계속 헤맸다.. 처음에 N==1 일 때 문제인줄 알았지만 그것도 아니었고.. 그냥 거북이의 시작점에서 처음에 시작할 수 있는가 없는가였다. 거북이의 시작점에서 시작할 수 있다면, 연결요소의 갯수에서 하나를 빼야하기 때문이다. 연.. 더보기
2186번 2186번 - 문자판 이 문제는 처음에 DFS를 통해서 완전탐색으로 풀었는데, 시간 초과가 발생 DP로 문제를 해결하였다. 찾아야하는 문자열과 같을 때 dfs를 돌렸고, 그렇게 해서 처음에 시간 초과가 났다. 중복되는 지점을 찾다보니, 어떤 점에서 find_idx 가 같으면 굳이 계산할 필요가 없다는 걸 깨달았다. D[find_idx][x][y] = x,y 에 도착했을 때 다음에 찾아야할 값이 goal[find_idx] 인 경우의 수 라고 점화식을 만들었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include using n.. 더보기
1525번 1525번 - 퍼즐 이 문제는 처음에 배열로 풀었다. 나름 머리쓴다고, 했지만 결국은 메모리 초과로 인한 런타임 오류... 그래서 STL map 을 공부해서 풀었다. 일단 map 은 정말 사용하기 좋은 template 인거 같다... 정렬도 되고, 배열처럼 사용할 수도 있고... 단 중복은 안되므로 그럴때는 multimap을 이용. 처음에 map을 배워서 map 의 인덱스 값으로 string을 이용했는데, 이 마저도 메모리 초과가 일어났다. 그래서 결국은 string 을 stoi 함수를 통해 모두 int 로 변경에서 index 로 입력했더니 AC를 받을 수 있었다. 결국 이 문제는 3 x 3 크기의 맵을 int 형 변수로 변경하고, 이를 map 을 통해 방문여부 체크하는 용도로 사용하여, bfs를 돌리면.. 더보기
1963번 1963번 - 소수 경로 문제를 보는 순간 '소수' -> 2가지 방법 ( 1. 에라토스테네스의 채. 2.루트N까지 for문으로 나눠보기) 그리고 숫자들을 정점이라고 했을 때, 변할 때 가중치가 따로 없으므로 1이라고 한다면 최단 거리를 구하기 떄문에 BFS로 풀 수 있다. 그래서 처음에 에라토스테네스의 채를 이용해서 N의 범위인 9999까지 소수를 모두 구해놓는다. 그리고 시작점을 BFS의 시작점으로 놓고, 각 자리의 수를 변화시킨다. 그때 변화된 점이 방문한 적이 없고, 소수이면 큐에 집어 넣는다. 목표로 하는 값이 나오면 while 문을 나오고 dist값을 반환해준다. 단, 내가 처음에 빠졌던 함정은 네자리 숫자이기 때문에 맨 앞에만 0이 올 수 없다는 점. 12345678910111213141516.. 더보기
10971번 10971번 - 외판원 순회2 유명한 TSP(traveling salesman problem) 인 외판원 순회다. 이 문제는 N 제한이 작기 때문에 (N 더보기
10819번 10819번 - 차이를 최대로 이 문제는 N 제한이 작기 때문에 완전탐색을 통해서 충분히 풀 수 있다. 예전에는 강의를 보고 next_permutation 으로 풀었으나, next_permutation 함수에 대한 이해가 부족해서 스스로 재귀를 통해 permutation 을 구현해서 풀어보았다. 인덱스 값을 재귀함수를 통해서 변화시켜준다. 이때, used 함수를 이용한다. 그 뒤 구한 permutation 이 N 과 일치하면 cal 함수를 통해서 최대값을 구한다. next_permutation 함수는 정렬한 뒤에 이용해야한다. 이유는 http://alhena.tistory.com/43 에서 잘 설명해주신다. 123456789101112131415161718192021222324252627282930313.. 더보기
1451번 1451번 - 직사각형으로 나누기 일단 총 여섯가지 케이스가 발생하게 된다. 그 중에서 나는 번호 매긴 것 처럼 1번과 2번은 getSumM1, getSumN1 으로 풀었다. 그리고 3,4,5,6번과 같은 경우는 선을 그은 것처럼 직사각형을 4분할 하였다.(getSum 함수) 그리고 각각 직사각형의 합을 구하였다. sum[0]~sum[3] 까지 그래서 왼쪽 상단을 0사분면, 오른쪽 상단을 1사분면, 왼쪽 하단을 2사분면, 오른쪽 하단을 3사분면이라고 한다면, 위의 3,4,5,6번 그림을 나타낼 수 있다. 그래서 이를 통해서 최대값을 구해내는 방식으로 문제를 풀었다. ##문제점## 처음에는 1번,2번 그림을 N이 1일때, M이 1일때만 가능한 그림이라고 생각하여 실수를 저질렀다. 직사각형 네개로 모든 것을.. 더보기
반응형

티스토리툴바