백준 11758번 문제 바로가기 세 점이 순서대로 주어지고 CCW(Counter-ClockWise; 반시계방향)인지 CW(ClockWise; 시계방향)인지 알아내느 문제. 보자마자 두 개의 벡터로 표현하면 편하겠다고 생각했다. 예전에 비슷한 문제를 풀어본 기억이 있기에 바로 외적을 떠올렸다. (기울기로 풀다가 엄청 고생했던 기억이…허허) 내 풀이 처음으로 struct 기능을 사용해보았다. 좌표(coordinate; cdn)에 x,y 좌표가 있으므로 struct cdn { int x,y; }; 처럼 작성하면 dot operator(.)로 접근할 수 있다. 함수 안에서는 int나 char 변수를 선언하듯이 cdn을 선언하고 사용하면 된다. 좌표나 특정 의미가 있는 값이 들어올 때 struct을 이용하면 코드가 간결해진다. ...
백준 13305번 문제 바로가기 문제에 대한 첫 인상 보통 문제에 최소 비용 이라는 표현이 들어가면 greedy 알고리즘으로 풀어내는 경우가 많은 것 같다. 이 문제도 각 주유소에서 비용을 최소로 한 것이 전체 비용도 최소가 되도록 한다. 나의 풀이 솔직히 마지막 주유소의 price는 필요 없는 정보였다. 앞에서부터 차례대로 주유소를 지나오면서 이전까지의 기름의 최솟값보다 더 저렴하면 prev에 새로운 기름값을 저장하고, 비용을 구해나가면 된다. 시간-비용 그래프를 그려보면 점차 하강하는 계단식의 그래프 형태를 띈다. #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { int N; // 주유소 갯수 vector<long long> distance; // 주유소 사이 거리 vector<long long> price; // 주유소별 리터당 가격 long long cost = 0; // 총 비용 long long prev = 1000000000; // 전 주유소 비용 long long temp; cin >> N; for (int i=0; i<N-1; i++){ cin >> temp; distance.push_back(temp); } for (int i=0; i<N; i++){ cin >> temp; price.push_back(temp); } for (int i=0; i<N-1; i++){ prev = min(prev, price[i]); cost += prev*distance[i]; } cout << cost; return 0; }
백준 19941번 문제 바로가기 문제에 대한 첫인상 처음에는 deque을 이용해서 풀어보려고 했다. H의 인덱스를 모아놓고 P를 기준으로 K범위에 H 인덱스가 포함되어있으면 pop하고 count을 1 늘리는 방식으로 구현했다. 하지만 사람보다 뒤에 있는 햄버거를 먹지 못하는(?) 알 수 없는 버그가 생겨서 갈아엎고 처음부터 다시 코드를 작성했다. 그냥 greedy하게 이중 for문을 돌려가며 만족하는 (H,P) 쌍이 있을 경우 H을 다른 문자(e.g ‘Y’)로 바꾸고 count을 1 늘리는 방식을 택했다. #include <iostream> #include <string> using namespace std; int main() { int N, K, count=0; string hp; cin >> N >> K; cin >> hp; for (int i=0; i<N; i++){ if (hp[i] == 'P'){ for (int j=i-K; j<i+K+1; j++){ if (hp[j] == 'H'){ hp[j] = 'Y'; count += 1; break; } } } } cout << count; return 0; }
프로그래머스 둘만의 암호 문제 바로가기 문제에 대한 첫 인상 char을 다루는 문제였기에 ASCII 아스키 코드가 바로 떠올랐다. s의 각 알파벳별로 index만큼 이동하면서 skip할 문자를 고려해주면 된다. 처음엔 되게 간단한 문제라고 생각했지만, ‘z’을 넘어가 다시 ‘a’부터 시작할 때에 (1) 또 다시 skip문자를 고려해줘야하고 (2) 다시 ‘z’을 넘어가버리는 케이스도 고려해줘야한다는 점이 까다로웠다. while문을 통해서 이를 확인하고 ‘z’ 넘어가는 경우 알파벳 숫자만큼(26) 빼주는 방식으로 구현했다. #include <string> #include <vector> #include <algorithm> using namespace std; string solution(string s, string skip, int index) { string answer = s; for (char& c: answer){ for (int i=0; i<index; i++){ c++; if (c > 122){ c -= 26; } while (skip.find(c) != string::npos){ c++; if (c > 122){ c -= 26; } } } } return answer; } 디버깅하는 과정에서 반례가 도움이 많이 되었는데, 유용한 반례를 몇 가지 적어본다. ...
백준 1064번 문제 바로가기 내 풀이 삼각형의 각 변의 길이를 구하고, 이를 통해서 만들어낸 평행사변형의 둘레의 (최댓값-최솟값)을 구하는 문제. 예제를 이상없이 모두 통과했지만, 실제로 제출해보니 틀렸습니다 에러가 발생해서 많이 당황했다. 크게 바꾼 부분은 다음 두가지다. 세 점이 한 직선상에 있는지 파악하기 세 점이 한 직선상에 있다면 평행사변형을 만들지 못하므로 -1을 출력해야 한다. 제2코사인 법칙을 이용해도 되고, CCW을 이용해서 풀어도 된다. 계산의 정확도 소숫점 자릿수를 고려해줘야하는 문제였다. 오차 범위가 $ < 10^{-9} $ 이므로 double을 사용하고 cout으로 출력하기 전에 cout.precision(20)와 같이 정확도를 우선 지정해주어야 한다. 자꾸만 틀렸던 이유가 바로 여기에 있었다… #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { double a1, a2, b1, b2, c1, c2; cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2; double x, y, z; x = sqrt(pow(b2-a2, 2) + pow(b1-a1, 2)); y = sqrt(pow(c2-b2, 2) + pow(c1-b1, 2)); z = sqrt(pow(a2-c2, 2) + pow(a1-c1, 2)); vector<double> vec = {2*(x+y), 2*(y+z), 2*(z+x)}; // using CCW if three dots are on a single line if ((b1-a1)*(c2-a2) == (c1-a1)*(b2-a2)){ cout << -1; return 0; } double ans; ans = *max_element(vec.begin(), vec.end()) - *min_element(vec.begin(), vec.end()); cout.precision(20); cout << ans; return 0; }