걸음마코딩기

와.. 이름만 보고 풀기로 마음먹었는데 예상외로 비트연산을 이용해야하는 문제라 애 좀 먹었다.. (다 까먹어서.. 멍충) 그냥 배열로 순회하면서 구현했을때는 시간초과가 나서, 기억 저편에 있던 비트연산을 다시 공부하며 풀었다. (참고) - https://velog.io/@surpiz/C15787%EB%B2%88-%EA%B8%B0%EC%B0%A8%EA%B0%80-%EC%96%B4%EB%91%A0%EC%9D%84-%ED%97%A4%EC%B9%98%EA%B3%A0 챗지피티한테 이것저것 물어보면서 이해했는데 이 똥멍청이가 자꾸 자기가 한말을 번복해서 이해하는데 엄청 오래 걸렸다.. (사실 내가 똥멍청이) 아무튼.. 코드를 작성하며 이해가 잘 안간 비트 연산들을 필기해놓은 것들을 같이 첨부한다. 부디 나처럼 헤매..

트리와 3가지 순회를 구현해보는 문제이다. 사실 처음엔 vector를 이용해서 구현해보려고 했는데, (멍청) 생각해보니 노드를 찾으려면 모든 vector를 순회해야 하므로 복잡도가 엄청 들게 생겼다.. 그래서, unordered_map을 이용하기로 했다. hash특성상 키에 접근하는 시간이 O(1) 상수시간이므로 빠르게 접근이 가능하다. 다만, 정렬은 필요없으므로 unordered를 사용했다. #include #include #include using namespace std; unordered_map tree; //root-left-right void preOrder(const string& node) { //node가 .이면 자식이 없으므로 return if(node == ".") return; c..

전형적인 bfs 문제로, 목표지점을 기준으로 각 좌표들의 최단거리를 구해주면 된다. queue를 이용해 각 좌표들의 visited 처리와 함께 거리를 구해주었다. #include #include using namespace std; int n, m, r, c; int graph[1001][1001] = {0,}; int visited[1001][1001] = {0,}; //각 좌표의 상,하,좌,우를 탐색해준다. int dir_n[4] = {-1,1,0,0}; int dir_m[4] = {0,0,-1,1}; //목표좌표를 기준으로 시작된다. void bfs(int x, int y) { queueq; q.push(make_pair(x,y)); visited[x][y] = 1; while(!q.empty())..

전형적인 dp문제이다. 각 돌에 도달하기 위한 값들을 잘 정리하면 풀 수 있다. #include #include #include using namespace std; #define MAX 999999; /* three jumps plus 1 (no skip) plus 2 (1 skip) plus 3 (2 skips) -> just one time & k energy */ int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,k; cin >> n; pair energy[21]; for(int i=1; i> x >> y; energy[i] = make_pair(x,y); } cin >> k; /* dp[i][0]은..

그리디 문제이다. 2+1으로 3개중 가장 작은 값을 무료로 해주기 때문에 가능한 큰 숫자들끼리 묶어서 가장 작더라도 전체에서는 큰 숫자를 무료로 받도록 코드를 짰다. 내림차순으로 정렬 3개씩 묶어서 마지막 값은 sum에 포함 안해준다. (인덱스가 0부터 시작하므로 i%3이 2가 아니면 다 더해줌) #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; vector c; cin >> N; for(int i=0; i> t; c.push_back(t); } sort(c.begin(), c.end(), greater ()); long..

공통된 숫자를 이용하여 가장 큰 수를 만들어주는 문제이다. string solution(string X, string Y) { string answer = ""; vector num(10,0); vector result; for(int i=0; i

priority queue pair로 구현했다. pair로 구성한 우선순위 큐는 첫번째 원소를 기준으로 정렬하기 때문에, pair의 첫번째 값에는 절댓값을 넣어주고 두번째 값에 원래 값을 넣어줬다. 또한, 내림차순이 기본이기 때문에 오름차순으로 바꿔주었다. #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; priority_queue pq; cin >> N; while(N--) { int x; cin >> x; if(x==0) { if (pq.empty()) cout

후위 표기식? 제일 뒤에 입력된 것끼리 연산하는 방식으로, 대표적인 스택 문제이다. [ 입력 예시 ] 입력 = ABC*+DE/- 첫번째 연산자 ➡️ 연산자 * ➡️ 스택 상황 A B C 1 2 3 ➡️ 연산 B * C = 2 * 3 = 6 ❗️연산 순서 주의 ❗️ 덧셈,곱셈에서는 문제가 되지 않지만 뺄셈,나눗셈에서는 문제발생한다. 첫번째 pop한 원소를 두번째 연산자로 정하고, 두번째 pop한 원소를 첫번째 연산자로 정해준다. ➡️ 연산 후 스택 상황 A B*C = F 1 6 두번째 연산자 ➡️ 연산자 + ➡️ 스택 상황 : 위 연산 후 스택 상황 ➡️ 연산 A + F = 1 + 6 = 7 ➡️ 연산 후 스택 상황 A + F = G 7 ... 이런식으로 연산을 진행한다. 마지막까지 연산을 진행하면 스택의..

#include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //1~N 순서대로 카드, 제일 위부터 pop => Queue queue card; int N; cin >> N; for(int i=1; i 1) { //card 한장 남을때까지 반복 card.pop(); int temp = card.front(); card.pop(); card.push(temp); } cout

문제풀이 처음에는 연결리스트 사용해서 circular queue를 사용해야겠다고 생각했다. 하지만 복잡하기 때문에 그냥 단순하게 필요한 순번의 번호가 나올때까지 뽑아서 다시 Queue 뒤에 저장하는 방식으로 야매 circular queue를 구현했다. Queue에 N만큼의 정수를 저장해준다. K-1번째까지의 원소를 pop해서 Queue 뒤에 push해준다. K번째의 원소를 pop해준다. Queue에 원소가 1개 남을때까지 반복해준다. (출력 형식때문에) 마지막원소를 출력해주고 마무리한다. 코드 #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int..