컴공과고씨

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 시간초과로 못풀어서 어떤식으로 풀어야하는지 처음으로 답을 참고를 했던 문제이다. 그래서 나중에 한번 더 복습이 필요할 것 같다. 아무튼 어떤식으로 풀었고 시간초과가 났으면 어떤식의 해결방법이 옳았는지 보겠다. 처음 푼 방법은 1, 11, 111, 1111이렇게 직접 n으로 나누어가면서 1의 개수를 늘려주어 나머지가 0인것을 찾으면 될거라고 생각했다. 하지만 이렇게 풀면 시간 초과가 걸리기 때문에 나머지 연산 공식을 써주어야한다. 이 문제는 나머지..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 이 문제는 어떤 식으로 접근했냐면 한 로프를 사용한다고 가정했을 때, 자기보다 많은 무게를 드는 로프는 결국 자신의 로프의 최대 들 수 있는 용량을 모두 들 수 있다는 것을 이용했다. 10 30 50 50 85 90 이라는 무게를 들 수 있는 로프가 있을 때 10로프를 이용해서 들 수 있는 최대 중량은? 10과 10보다 큰 로프의 개수를 10에 곱해주면 총 60을 들 수 있다. 30로프를..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 이 문제는 탐색 문제지만 고려해야할 것이 있다. 첫번째는 무조건 적인 탐색이 아니라 외부쪽에 있는 치즈를 전부다 방문하면 카운트 그 다음 안쪽에 있는 치즈 전부 탐색 후 카운트 이런식으로 순차적으로 가면서 카운팅을 해주어야 된다. 그래서 나는 bfs안에 기본적인 구조가 큐를 한번 쓰는 거라면 큐를 2번을 사용하여 구현을 해주었다. 일단 (0,0)에서 시작을 해서 탐색을 시작하여 1을 만났을 때는 temp큐에 넣어주고..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제 같은 경우 처음에는 계산 형식으로 고민을 하다 bfs를 써야겠다는 생각이 들었다. bfs를 쓰니 간단히 해결이 되었다. bfs 구성은 동생을 찾지 못하면 x+1, x-1, 2x를 visit에 넣어 방문했는지 검사한 후 방문을 하지 않았다면 각각을 q에 넣어주면 간단히 해결된다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이 문제는 일반 탐색문제와 거의 흡사하지만 고려해주어야 할게 하나 더 추가된 형식이다. 바로 층 수가 있다는 것이다. 보통 탐색 문제의 경우 상하좌우만 움직여 좌표를 2개만 설정해주지만 이 문제 같은 경우 층 수도 고려를 해주어야 하기 때문에 층을 고려하는 좌표를 하나 추가해주어 풀어주면 간단히 해결된다. 나는 bfs를 이용하여 큐에 x,y,z,count를 튜플로 만들어 넣어주어 문제를 해결하였다. b..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음 보면 탐색 방법으로 풀어야겠다는 생각이 딱 든다. bfs를 이용해서 풀어보자! 일단 이 문제의 핵심은 벽을 1번 부술 수 있다. 그래서 나는 bool destory 변수를 두어 벽을 부수고 온 탐색인지 아닌지를 구분해 주었다. tuple을 사용하여 x좌표, y좌표, count, destory 이렇게 4개의 변수를 저장하여 큐에 넣어주는 식으로 구현하였다. 또 실수하지..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제를 보고 분할 정복을 사용해서 풀 수 있겠다는 생각이 들었다. 일단 분할 정복 같은 경우는 큰 문제를 작은 문제로 나눠서 푸는 방법이다. 지금 같은 경우 큰 정사각형에서 크기가 4인 정사각형까지 쪼개서 풀어주면 쉽다. 큰 정사각형은 4분할 해서 4개의 정사각형을 만들 수 있다. 그리고 조건문을 사용해서 4분면 중 위 순서대로 검사를 하여 구하고자하는 위치가 어디에 속해 있는지 확인해주..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net queue를 이용하여서 풀 생각을 하였다. 해결 방식은 먼저 큐하나에는 우선 순위만 저장하고 다른 큐에는 pair를 이용하여 배열 번호와 우선 순위를 적어주었다. 그 다음 우선순위를 오름차순으로 sort를 한다. 그 후 정렬된 우선순위와 큐에 저장된 우선순위를 하나씩 비교하면서 정렬된 우선순위 보다 낮다면 뒤로 보내준다. 올바른 우선순위가 나오면 그 배열 번호를 결과 큐에 넣어준다. 결과 큐에 넣어주..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 일단 이 문제의 경우 이분 탐색을 사용하였다. 절단기를 높게 설정하면 잘리는 나무는 적어진다. 절단기를 낮게 설정하면 잘리는 나무는 커진다. 절단기 설정 높이를 이분탐색을 사용하여 구하면 된다. low는 0, high는 나무 길이의 최대값인 1,000,000으로 설정하고 이분탐색을 시작한다. 절단기의 설정 높이가 모든 나무길이보다 크게되면 의미가 없기 때문...