컴공과고씨

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 읽었을 때 사용해야할 알고리즘이 떠오른것은 그래프 탐색이였다. 그 중 나는 넓이 우선 탐색 bfs를 선택해서 풀었다. 전체적인 풀이 방법은 배추가 있는 한 곳에 지렁이를 풀어준다. 그리고 그 지렁이가 인접해 있는 배추를 탐색하기 시작 한다. 이때 지렁이가 지나간 곳은 bool visit로 해서 방문했다는 표시를 해준다. 그리고 bfs가 끝나고 다른 배추 위치를 bfs에 넣어 지렁이를 다시 푸는데 이때 ..

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/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제를 보면 카드가 FIFO 처음 들어간것이 먼저 나오는 구조를 가지고 있기 때문에 큐를 사용했다. 처음에는 POP을 사용하고 그 후 그 다음 숫자를 뒤로 넣어주는 구조로 구현 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; int main(){ int n;..

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!

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문자열 길이가 50이 넘지 않는다를 보고 생각한 것은 그럼 크기 50짜리 벡터 배열 만들어서 길이에 따라 저장해주는 것을 생각 예를 들면 이런 식으로 1번에는 길이가 1인 문자를 넣어주고 2에는 길이가 2인 문자열만 넣어주는 방법. 그런 후 벡터 sort를 이용하여 각 배열안에 있는 벡터들을 사전순으로 정리 후 중복되는 단어들을 제거 해줌. 그 후 순서대로 출력해주면 단어가 정렬 되어짐..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 보고 일단 w로 시작하는 정답 1개 b로 시작 하는 정답 1개로 나눌 수 있다고 생각함. ex) wbwbwbwbwb , bwbwbwbwb 이런식으로. 그리고 입력으로 받은 체스판에서 위 정답과 하나씩 비교하여 틀린 만큼 카운트를 한 후 2정답 중 최소 값을 저장하는 방식으로 구성해야 겠다는 생각으로 코드를 만듬. 만든 코드