알고리즘 부수기

문제링크 : https://codeforces.com/contest/1099/problem/B 원하는 개수의 사각형을 만들기 위해 자를 재고 그려야하는 선의 개수의 최소값을 찾는 문제이다. 우선 이해하기 쉽게 문제를 설명해보면, 위 그림에서 빨강색 선은 자를 이용해서 그려야 하는 부분, 검정색은 자 없이도 그릴 수 있는 부분이다. 왜 검정색은 자 없이 그릴 수 있는 부분인가? 이미 같은 x 와 (x+1) 혹은 같은 y와 (y+1)을 이은 선이 존재하기 때문이다. 즉, a'은 a로 인해 자 없이 그릴 수 있고, b'은 b로 인해 자 없이 그릴 수 있게 된다. 마찬가지로 사각형 2개를 만들기 위해서는 아래 그림과 같이 구성되어야 한다. 사각형 2개를 만들기 위해서는 3개의 빨강 선이 필요하게 된다. 이제, ..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT&categoryId=AWS2h6AKBCoDFAVT&categoryType=CODE 이 문제는 산의 높이를 순서대로 저장한 배열에서 극대값을 찾는 문제이다. 산의 높이는 10^9까지 가지만 산의 개수가 50,000개 이하이므로 long long을 사용하지 않았다.(산의 높이를 더하는 문제였으면 long long을 사용해야 한다.) 기본적인 아이디어부터 살펴보자. 극대값이 있고 그 주변을 감쌀 수 있는 범위의 개수를 찾는 문제이다. 순서대로 증가한 값이 극대값 앞에 2개 있고 순서대로 감소한 값이 극대값 뒤에 2개가 있다면..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWd7sgDatsMDFAUh&categoryId=AWd7sgDatsMDFAUh&categoryType=CODE 강의의 수 n과 들을 수 있는 강의의 수 k가 주어진다. ( k 사용한 방법은 강의의 최대 효율이 10000이므로 효율에 따라 배열을 만들어서 n개의 강의를 입력받을 때마다 해당 효율의 count를 늘려준다.-> 앞에서부터 탐색하며 전부 스택에 넣는다.-> 새로운 스택에 k개만큼 pop하여 push한다. 2. 만들어진 stack을 pop하며 result에 더하고 2로 나눈다. * 강의의 개수가 적기 때문에 편의를 위해 새로운 stack에 ..

2018년 마지막 코포(Good Bye 2018)를 끝냈습니다. 그린으로 떨어져서 마지막 코포에서 민트 만들고 끝내고 싶었는데.. 같은 문제에서 1시간 10분동안 10번 제출해도 같은 곳에서 계속 틀렸습니다. 결국 맞은 다음에 알고 보니 long long으로 선언해놓고 %d로 계속 출력.. 이런 실수도 못 찾아내는거 보면 아직 멀었네요T^T 너무나 멘붕이 와서 이번에 푼 문제는 올리지 않는걸로.. 흑 (이렇게 점수 깎여놓고 Rating 2점 내려가는거 보니 너무 아쉽.. 만약이란 없지만 맞췄으면 떡상..) 2019년에는 반드시 블루로 올라가겠습니다 !!!

문제링크 : https://www.acmicpc.net/problem/1008 간단한 문제지만 확실히 알아야하는 문제이다. Codeforces 라운드에서 많이 틀렸던 유형이기도 하다. 정수형의 수들은 알고리즘 문제를 해결하며 많이 다뤄보지만 소수점은 많이 다뤄보지 않는다. 그래서 확실하게 알아놓지 않으면 갑작스럽게 문제가 생겼을 때 당황하기 쉽다. 먼저, 오답이다. - 소스 코드(오답) - #includeusing namespace std;int main(void) {float a, b;cin >> a >> b;float c = a / b;printf("%.9f", c);} 소수점을 계산하기 위해 float으로 입력을 받았다. 그리고 10^-9 이하의 오차만 허용하므로 .9f를 사용해 아홉번 째 자리까지..

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/C 입력으로 특정 각도가 주어진다. 이 때, 정다각형 내부에서 위와 같이 3개의 점을 연결해서 주어진 각도를 만들 수 있는 정n각형들 중 최소인 n을 찾는 문제이다. 우선, 수학적으로 알아야할 개념이 있다. 정n각형의 내각의 총 합 : 180 * (n-2) 위의 공식을 따라 (180 * (n-2)) / n 을 통해 정n각형의 한 각의 크기를 알 수 있다. 다음으로 알아야할 내용은 정n각형의 특징이다. 정사각형을 생각해보자. 정사각형에서 한 점에 대해 위 그림과 같이 추가적으로 이어줄 수 있는 점은 양 옆을 제외한 나머지 1개의 점( n-2 )이다. 이어줄 경우 정사각형의 한 각의 크기인 90도를 정확히 1..

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/B 이번 코포는 자료형과 관련된 것들을 제대로 다룰줄 모르면 헤맬 수 밖에 없었다. 이 문제에 대한 설명부터 하자면 최소 2개 이상의 문자로 구성된 string이 왔을 때, substring을 빼서 한 글자만 남아있거나 아무 것도 없게 만드는 경우의 수를 구하는 것이다. 얼핏 보면 "전체 다 따져야하나?"라는 생각이 들지만 substring이라는 것을 기억해야 한다. substring은 부분 문자열이다. 즉, 연결되어 있는 문자열 1개를 제거한다는 뜻이다. 그럼 이제 문제를 다시 보자. 우리는 특정 1종류의 문자만 남도록 혹은 하나도 남지 않도록 만들어야 한다. 크게 3가지 경우로 나눌 수 있다. i) 앞..

D번) 문제 링크 : http://codeforces.com/contest/1095/problem/D n개의 노드가 존재한다. 이 때, 순서에 상관없이 각 노드마다 자기 다음에 있는 노드 2개를 알려준다. ex) 입력을 해석해보면1번 노드의 뒤에는 3과 5가 오고2번 노드의 뒤에는 1과 43번 노드의 뒤에는 2와 44번 노드의 뒤에는 1과 55번 노드의 뒤에는 2와 3이 온다. 이 때, 이 정보를 바탕으로 올바른 순서를 찾으면 되는 문제이다. 접근 방법은 단순하다. node라는 구조체를 만들어서 다음 값 2개를 저장한다.그리고 set함수와 값을 하나 줬을 때 다음 값 2개 중 해당 값이 있는지를 확인하는 함수를 만든다. 다음으로 출력하는 순서는 상관없다고 했으므로 1번 노드부터 시작해서 다음 1번노드가 ..