백준 2477번 문제 바로가기 문제에 대한 첫 인상 처음엔 도대체 어떻게 풀어야하지 고민하다가, 하룻밤 자고 나서야(ㅋㅋ) 해결책을 생각해냈다. 방향을 일일히 고려하는것은 어렵기 때문에 일반화해서 풀어내기로 했다. 가장 긴 두 변이 0, 1번째 인덱스가 되도록 하는 숫자를 찾는 것을 목표로 했다. “동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.“라고 했기 때문에, ㄱ자 형태의 경우 423131방향의 이동을 찾아내면 되고, 다른 형태의 경우도 314242 142323 231414 처럼 패턴을 구하면 된다. 그 인덱스를 기준으로 $ l(j)*l(j+1) - l(j+3)*l(j+4) $ 를 구하면 원하는 식을 얻어낼 수 있다. ...

백준 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; } 디버깅하는 과정에서 반례가 도움이 많이 되었는데, 유용한 반례를 몇 가지 적어본다. ...