본문 바로가기
반응형

알고리즘

14890번 14890번 - 경사로 저번 하반기에 SW역량평가에서 나왔던 문제이다.. 그때도 결국 예제는 다 맞았는데, 집와서 생각해보니 실수한 부분이 있었다. 시뮬레이션 문제이기 떄문에, 생각하고 푸는게 중요한 것 같다. 다시 풀어보는데, 충분히 생각을 먼저하고 풀지 않아서, 의식의 흐름대로 풀다보니 디버그에서도 뭐가 뭔지 헷갈렸다. 나는 재귀함수를 이용해서 왼쪽에서 오른쪽으로 검사하는 countPath1, 위에서 아래로 검사하는 countPath2 를 구현했다. 두 함수는 배열의 인덱스 값만 뒤바꿔주면 사실은 같은 함수가 된다. 로직은 다음칸이 나랑 같으면 같은 칸이 몇칸 축적됐는지 알려주는 c값을 저장했다. ( 단 처음에 1로 초기화) 그리고 경사로를 설치하기 위해서는 결국 1칸이 높던지, 1칸이 낮아야 하므로.. 더보기
3967번 3967번 - 매직 스타 백트래킹 문제로 사용하지 않은 알파벳을 A부터 L까지 전부 사용하면서 문제를 풀었다. 6곳을 모두 체크해야하는데, 그냥 이차원 배열로 체크하도록 선언을 미리 했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include#includeusing namespace std; char map[5][9];int dx[6][4] = { {1,1,1,1},{3,3,3,3},{0,1,2,3},{0,1,2,3},{1,2,3,4},{1,2,3,4} };.. 더보기
1813번 1813번 - 마지막 한마디 로직은 간단하게, 정확하게 2개의 말만 참이다 라고 했으면, 정확하게 2개의 말만 참이다 라는 문장이 딱 2번 나와야한다. 더 나오면 2개보다 크기 때문에 거짓이 되고, 적으면 작기 때문에 거짓이 된다. 즉 n 이란 값이 참이 되려면 n 이 n번 나와야 한다는 말이다. 따라서 나는 그냥 입력받은 값을 sort 하고 upper_bound 와 lower_bound 를 이용하여 값이 몇개 존재하는지를 카운트 헀다. 주의할 점은 모순이 생길 때 인데, 모순은 모든 값들이 다 거짓이고, 주어진 입력으로 0이 들어올 때이다. 0은 한번이라도 등장하면 모순이 된다. 0이 0번 있어야 하는데, 입력으로 들어오는 순간 0보다 커지기 떄문이다. 따라서 모순일 때만 따로 체크해주면 된다. 123.. 더보기
2206번 2206번 - 벽 부수고 이동하기 기본적인 BFS에 한차원을 더 늘려서 문제를 풀면 된다. 어떤 지점에 도달했을 때, 벽을 하나 부수고 이동한 상태인지/ 벽을 부수지 않고 이동한 상태인지 를 나눴다. dist[x][y][0] 은 x,y 좌표에 도달했을 때 벽을 부수지 않고 도달한 경우, dist[x][y][1] 은 x,y 좌표에 도달했을 때 벽을 한번 부수고 도달한 경우 이를 이용해서 큐에 값을 넣을 때 벽을 부술 수 있는지? -> 벽인지/벽이 아닌지 + 방문한적이 있는지? -> 계산해서 큐에 넣기 이런과정을 통해서 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 더보기
2589번 2589번 - 보물섬 모든 육지에 대해서 BFS를 실행한다. 가장 멀리 떨어진 값을 ans 변수에 넣는다. 각 육지에서 가장 떨어진 값을 찾으면 되기 때문에, 각 점에서 마다 BFS를 실행시킨다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include#includeusing namespace std;int n, m;int ans = -1;char map[51][51];int dx[4] = { 0,0,1,-1 };int dy[4] = { 1,-1,0,0 }; void bfs(int x,.. 더보기
7562번 7562번 - 나이트의 이동 나이트가 한번에 이동할 수 있는 경로를 모두 체크하는 dx,dy 배열을 만들고 BFS를 사용하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include#includeusing namespace std; int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };int dy[8] = { -2,-1,1,2,2,1,-1,-2 }; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; for (int t = 1; t > n >> sx >> sy >> ex >> e.. 더보기
1244. 최대 상금 1244. 최대 상금 이 문제는 두가지 방식으로 풀 수 있었다. 첫번째는 캐시를 이용해서 푸는 방법이다, 완전탐색으로 진행하되, D[n] 은 n번 교환했을 때 최대값 을 저장했다. 따라서 똑같은 n번 교환했을 때 값이 작다면, return 을 해서 돌아가도록 만들었다. 사실 근데 D의 배열을 몇까지 해야할지, 즉 최대교환 횟수가 문제에 주어지지 않아서 처음에 생각을 못했다. 근데 그냥 좀 크게해서 문제를 푸니까 이 문제는 풀 수 있었다. 두번째는 그리디적인 방법으로 풀었다. 결국 앞에 올수록 큰 수가 와야 한다, 따라서 맨 앞자리 부터 가장 큰 수로 채우는 방법이다. 가장 왼쪽 자리부터 시작해서 가장 큰 값을 찾는다, 만약 가장 큰 값이 자기 자신이면 그 다음으로 이동한다. 근데 만약 가장 크지 않다면 .. 더보기
3503. 초보자를 위한 점프대 배치하기 3503. 초보자를 위한 점프대 배치하기 로직은 우선 점프대를 오름차순으로 정렬한다. 그리고 가장 낮은 점프대(0번째)를 가운데에 넣고, 양 옆으로 번갈아 가면서 오름차순의 점프대를 넣어주면 된다. 양옆으로 넣어줘야 하기 때문에 deque 를 사용해서 문제를 풀었다. 이렇게 푼 이유는 만약 점프대가 오름차순으로 있다면, 원형이기 때문에 결국 가장 큰 점프대와 가장 낮은 점프대의 차이가 답으로 나올 것이다. 하지만 가장 낮은값을 가운데에 넣고, 그 앞뒤로 순차적으로 삽입을 하면, 평균적인 차이가 가장 낮게 나올 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657.. 더보기
반응형

티스토리툴바