컴공과고씨

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/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net stack은 LIFO를 가지고 있기 때문에 이 규칙을 지켜서 문제 맞게 수행 해주면 된다. 내가 풀이 방법은 일단 스택이 있고 이 스택에는 미리 저장해놓은 원하는 수열 원소 크기와 비교해가면서 숫자를 순서대로 넣기 시작한다. 일단 원하는 원소 크기가 스택 top에 있는 숫자보다 크다면 원소 크기가 될때까지 숫자를 넣..

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으로 설정하고 이분탐색을 시작한다. 절단기의 설정 높이가 모든 나무길이보다 크게되면 의미가 없기 때문...

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술 평균은 처음에 float를 썼는데 오류가 나서 double로 바꿔주니 잘 되었다. double 훨씬 더 정확하기 때문에 정확성 문제로 오류를 발생 시키는 것 같았다. 중앙값은 그냥 sort해서 (n-1) 후 2로 나눠주면 나왔고 범위도 마찬가지로 sort 후 최대 - 최소 해주면 쉽게 나왔다. 최빈값 같은 경우 처음에 문제를 제대로 읽지 않아 "정수의 절댓값은 4,000을 넘지 않는다" 이 부분을 놓쳐 조..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 처음 생각했던 방법은 전부 랜선을 합쳐서 k개의 랜선으로 나눈 후 나온 값을 이용해 각 랜선의 길이 만큼 비교하여 조건에 맞을 때까지 1씩 줄여가는 방법을 써보았지만 당연히 시간초과에 걸렸다. 그래서 시간을 줄이기 위해 이분 탐색을 이용하여 반 씩 나누어 가며 잘라야할 길이를 찾음. 사용 알고리즘 : 이분탐색 yea!