Little Jay

조금은 까다로웠던 구현 문제였다. 함수 이름을 BFS라고 써놨는데 그냥 check정도가 적당할 것 같다. 입력으로 X가 들어올때 vector에 집어 넣고, 이 vector 컨테이너 안에 있는 시작점들을 바탕으로 탐색을 시작하면 되는 문제였다. 오목이기 때문에 상하좌우 뿐만이 아니라 대각선으로도 이동할 수 있다는 것까지 고려해야 한다. 특이한점은 X가 5개로 연결되는 경우가 정답이 아니라 X가 4개 있고, 하나의 바둑돌을 놓을 수 있어야 정답이 된다. #include #define endl '\n' #define pii pair using namespace std; const int m = 10; char arr[m][m]; vector v; const int dx[8] = { 1, 1, 1, 0, 0, ..

문자열 문제 중 대표적인 문제인 팰린드롬 문제이다. 단순히 문자열이 팰린드롬인지 확인하는 것이 아니라, 재귀적으로 left와 right로 나누어서 팰린드롬을 확인해줘야 했던 문제이다. 종료조건은 문자열의 size가 1일때 return해주면 된다. 여타 팰린드롬 문제가 그러하듯 항상 문자열의 size가 홀수일때와 짝수일때를 구분해주면 된다. #include #define endl '\n' using namespace std; string s; bool palindrome(string a) { if (a.size() == 1) return true; string left, right; int size = a.size() / 2; for (int i = 0; i < size; i++) { left += a[i..

파티션을 활용한 브루트포스 문제 #include #define endl '\n' using namespace std; int n; int arr[11]; int calc(int start, int end) { int x = 1; for (int i = start; i > n; for (int i = 1; i > arr[i]; } int temp, ans = 0; for (int i = 1; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { temp = calc(1, i) + calc(i + 1, j) + calc(j + 1, k) + calc(k + 1, n); ans = max(ans, temp); } } ..

인접행렬로 문제를 푸는 것을 선호하는데, 이렇게 인접 리스트로 푸는게 오랜만이라 시간이 좀 걸렸다. 항상 느끼는 거지만 인접행렬이 더 편한 것 같다. #include #define endl '\n' #define MAX 100005 using namespace std; int n, m, init; vector v[MAX]; bool visited[MAX]; int solve() { int cnt = 0; queue q; q.push(init); visited[init] = true; while (!q.empty()) { auto current = q.front(); q.pop(); if (!v[current].size()) { return cnt; } if (visited[v[current][0]]) b..

입력받는것을 계속 int로 받다가 실패했다. 띄어쓰기가 없는 것은 char이나 string으로 받아야 하는 것에 유의하자. n-1일때 return true 해야하는데 m-1로 계속 써서 실패했다. 항상 조건을 잘 보도록 하자. #include #define endl '\n' using namespace std; int n, m; int board[1005][1005]; bool visited[1005][1005]; const int dx[4] = { 1, -1, 0, 0 }; const int dy[4] = { 0, 0, 1, -1 }; bool bfs(int y, int x) { visited[y][x] = true; queue q; q.push({ y, x }); while (!q.empty()) {..

Status Register CPU에는 Status Register, PSW라는 아주 작은 레지스터를 지니고 있다. 이는 CPU의 current status를 저장하기 위한 레지스터이다. CPU는 이 레지스터를 통해 코드의 flow를 Control하게 된다. Status Register는 인텔 x86 아키텍쳐에서는 Condition Code를 저장한다고 한다. Condition Code는 Single Bit으로서 이를 통해 flag를 저장한다. 이 Flags들은 operation의 결과에 따라 set된다. 일반적으로 많이 알려진 Condition Code에는 CF Carry Flag ZF Zero Flag SF Sign Flag OF Overflow Flag 등이 존재한다. 앞선 포스팅에 나와있는 레지스..

greedy한 문제였다 단순히 닭이 소의 시간 안에 들어있는지 아닌지를 파악해주면 되는 문제라 쉬워보였지만, 소를 priority queue로 정렬하는데에 있어서 시작시간만을 기준으로 정렬하면 틀리는 문제였다. priority queue의 정렬 함수를 구현하는 것이 결국 관건이었던 문제이다 #include #define endl '\n' using namespace std; int c, n; struct comp { bool operator()(pair a, pair b) { if (a.second != b.second) return a.second > b.second; return a.first > b.first; } }; vector chicken; priority_queue cow; int main..

진법 계산을 요구하는 Brute Force 문제 #include #define endl '\n' using namespace std; const int numbers[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; bool check(int dec, int hex, int doz) { return (dec == hex && hex == doz); } int dozen_calc(int n) { int doz_num = 0; int temp = n; while (temp) { doz_num += numbers[temp % 12]; temp /= 12; } return doz_num; } int hex_calc(int n) { int hex_num..

Data Size 먼저 앞서서 간단하게 살펴본 Data Size를 짚고 넘어가자. b: 1Byte - Byte w: 2Byte - Word l: 4Byte - Double word q: 8Byte - Quad word assembly 코드를 읽을 때 이 suffix를 잘 파악해야 몇 바이트 단위로 끊어서 해석해야하는지 알 수 있기 때문에 이를 잘 숙지해야한다. Mov Instruction 이전 포스팅에서 간단하게 mov instruction에 대해서 언급했었는데 이를 조금 더 자세히 살펴보고자 한다. mov가 그러하듯 다른 instruction에서 suffix로 Data Size를 붙이게 되면 그 만큼의 Data를 저장할 수 있다. 하지만 또 때에 따라서는 이 Data Size를 생략하고 쓸 수 있기 때..

BFS로 구현했다. (DFS 싫어) #include #define endl '\n' using namespace std; bool arr[51][51]; bool visited[51][51]; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; const int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; int w, h; int bfs(int x, int y) { if (arr[x][y] == 0) return 0; if (visited[x][y]) return 0; queue q; q.push({ x, y }); visited[x][y] = 1; while (!q.empty()) { auto current = q.front(); q.pop();..