Posts

LeetCode 86. Partition List 🗓️ Daily LeetCoding Challenge August, Day 15 Linked List Linked List 문제는 처음 풀어본다. 간접적으로 array을 이용해서 비슷하게는 풀어봤지만, linked list 자체를 사용해본건 이번이 처음. 문제에서 떡하니 ListNode가 정의되어 있어서 많이 당황했다. 어떻게 값을 불러오는지조차 망설이게 되었다. 예제를 이용해서 실제 linked list을 그리면서 풀어보니까 이해가 잘 되었다. 나의 풀이 Linked List는 목걸이처럼 각 Node가 꼬리에 꼬리를 무는 형태의 자료구조이다. array와는 다르게 index가 정해지지 않고 각 Node는 val 데이터 필드와 다음 Node를 가리키는 *next 링크 필드를 가진다. 비엔나소시지처럼 줄줄이 엮어내면 linked list가 완성된다. index 고려를 크게 하지 않아도 돼서 비교적 간단하게 풀어낼 수 있다. ...

백준 2309번 문제 바로가기 bruteforce #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> snowWhite; int total = 0; int height = 0; bool check = false; for (int i=0; i<9; i++){ cin >> height; total += height; snowWhite.push_back(height); } sort(snowWhite.begin(), snowWhite.end()); for (int i=0; i<9; i++){ for (int j=i+1; j<9; j++){ if (snowWhite[i] + snowWhite[j] == total - 100){ check = true; for (int k=0; k<9; k++){ if (k == i || k == j){ continue; } cout << snowWhite[k] << endl; } break; } } if (check) break; } return 0; } Review bruteforce을 이용하면 간단하게 풀어낼 수 있는 문제 다만, 이중 for문을 사용하기에 break 처리에 유의해야 한다. 내부 for문만 break하고 외부 for문은 break하지 않으면, 모든 경우의 수를 출력하기 때문에 틀렸습니다가 발생할 수 있다.

프로그래머스 정수를 나선형으로 배치하기 문제 바로가기 아니 이게 Lv.0 문제라고?! DFS에 나올법한 꽤나 난이도 있는 문제였다. 일일히 구현하는것도 쉬운 문제는 아니었다. 예전에 python에서 graph관련 알고리즘 문제를 풀었던 기억이 있어서 C++로도 풀이해보았다. 내 풀이 dx, dy를 vector로 지정해서 다음 움직임의 방향을 지정해주었다. mode에 따라서 dx[mode]처럼 불러와서 다음 위치를 알아낼 수 있다. 다음 위치에 이미 부여한 숫자가 있거나(0이 아니거나), 주어진 범위에 넘어가면 안되기에 예외 처리를 해주었다. 알맞게 구현한 것 같은데 자꾸만 segmentation fault 오류가 발생해서 알아보니 mode가 4를 넘어가면 dx,dy의 index를 초과하기에 발생하는 에러였다. 따라서 mode를 4로 나눈 나머지로 (mod 4) 설정하면 오류에서 벗어날 수 있다. #include <string> #include <vector> #include <iostream> using namespace std; vector<vector<int>> solution(int n) { vector<vector<int>> answer(n, vector<int>(n, 0)); vector<int> dx = {1,0,-1,0}; vector<int> dy = {0,1,0,-1}; int x=0; int y=0; int mode = 0; for (int i=1; i<=n*n; i++){ answer[y][x] = i; int x_next = x+dx[mode]; int y_next = y+dy[mode]; bool a = (x_next<0 || x_next>=n); bool b = (y_next<0 || y_next>=n); bool c = (answer[y_next][x_next] != 0); if (a || b || c){ mode = (mode + 1)%4; }; x += dx[mode]; y += dy[mode]; } return answer; }

프로그래머스에서 제공하는 코딩 기초 트레이닝 문제들을 모두 해결했다!! Level 0 Basic 문제들을 클리어했더니 킹받게 생긴 머쓱이 스탬프를 쾅! 찍어준다 ㅋㅋ (귀여우니까 봐준다) C++ 공부를 8월 1일에 시작했으니까 기본 문법 익히는데 일주일, 기본 문제들 모두 해결하는데 일주일이 걸렸다. 아무래도 python에서 익혀온 코딩 경험치가 있다보니 금방 익힐 수 있었던 것 같다. 생각보다 C++가 어렵진 않았고, 다만 Standard Template Library (일명 STL)을 익히기 위해서는 앞으로 더 노력해야겠다는 생각이 든다. 변수 선언하고 사용해야한다는 점은 생각보다 직접 사용해보니 까다롭진 않았다. 물론 세미콜론(;) 붙이는건 귀찮긴 하지만(…) 손에 익어서 괜찮다;;; ...

백준 27295번 문제 바로가기 나의 풀이 문제 자체는 그리 어렵지 않다. x의 합=X, (b-y)의 합=Y라고 두면, 결국엔 $ a * X + Y = 0 $ 방정식을 푸는 것에 불과하기 때문이다. for 반복문으로 x와 y값의 합을 구해준 뒤에 조건에 따라 x_sum=0인 경우, 정수꼴, 분수꼴로 나눠주면 된다. 주의할 점은 주어진 정수의 값이 꽤 크기 때문이다. $ -10^{9} <= x,y <= 10^{9} $ 이고 $ 1 <= n <= 10^{5} $ 이므로 곱하다보면 최대 $ 10^{14} $ 가 되어 int 자료형으로는 overflow가 발생할 수 있다. int / long은 4 byte로, -2,147,483,648 ~ 2,147,483,647 범위를 가지기 때문이다. 따라서 p와 q, divider의 경우 long long 정수 자료형을 사용해서 overflow가 발생하지 않도록 방지해야 한다. ...