Algorithm

겪은 문제 (멍청)7 74 2 11 1 1 1 1 1 11 0 0 0 1 0 11 0 1 1 0 0 11 0 0 0 0 1 11 0 0 1 0 0 11 0 0 0 0 0 11 1 1 1 1 1 1>> 답 11위 케이스에서 답이 11이 나와야 했는데 9가 나왔다. 🔍 문제의 원인게시판을 돌다보니 나처럼 해당 케이스에서 어려움을 겪는 사람이 있었고, 해결사가 댓글에 루트를 달아주었는데, 이런!!! 나랑 영 다른 길을 간다...알고보니 멍청한 실수를 했다. 방향이 1~4가 아니라 0~3 인데, 나는 1 베이스를 제로베이스로 만든다고 dir을 -1한 뒤 시작했다...🥹... 코드이해하기 쉬우라고 일부러 주석을 안지웠다.#include #include #include #include using namespac..

어떻게 풀까 막연히 생각해보면,테이블 블록을 bfs로 찾고 (A)게임 보드의 빈공간을 bfs로 찾아서 (B)A와 B가 같은 모양일 때 블록 칸 수를 answer에 더해주면 되겠는데? 크게 보면 간단한데, 같은 모양을 판별하는데 시간이 오래걸렸다.회전을 시킬 수 있기 때문이다...  그래서 같은 모양 판별을 하기 위해서 아래 작업들을 해줬다. 1. 같은 모양이더라도 누군 (2,4)부터 그려지고, 누군 (3,8)부터 그려지고.. 하면 비교가 어려우므로 각 블록들의 좌표를 0-base로 만들어줬다. 그리고 좌표를 시계방향으로 돌리다 보니까 규칙을 발견했다!!!현재 좌표를 x, y 라고 하고, 90도 시계방향 회전한 좌표를 x', y'라고 하면 아래 공식이 성립된다.x' = yy' = (돌리기 전 height ..

풀이 (비효율적 주의)#include #include #include #include #include #include using namespace std;int solution(string numbers) { map m; set s; const int limit = pow(10, numbers.length()) - 1; // 넘버 미리 맵에 넣어두기 for (int i=0; i v(limit+1); for (int i=2; i copyM; copyM.insert(m.begin(), m.end()); if (v[i] != -1) { // 소수면서 int num = i; bool is..

BOJ 11659 : 배열이 주어지고, 여러 번의 구간합을 구하는 문제.구간합을 매번 직접 계산하면 O(n*m)시간 복잡도가 발생한다.누적합을 이용하면 O(1)로 구간합을 구할 수 있다.배열의 각 위치까지 누적합을 미리 계산해두고, 구간 합을 빠르게 구하는 기법예를 들어 3부터 5까지의 합이면, 5까지의 누적합 - 2까지의 누적합 하면 되니까 빠르게 계산 가능!const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');const [n, m] = input[0].split(' ').map(Number);input.shift();let list = input[0].split(' ').map(..

최대 공약수유클리드 호제법큰 수를 작은 수로 나눠 나머지를 구한다.그 작은 수와 나머지로 다시 나눈다나머지가 0이 될 때 작은 수가 최대공약수다.예시 gcd(48, 18)48 / 18 = 몫이 2, 나머지가 12gcd(18, 12)18 / 12 = 몫이 1, 나머지가 6gcd(12, 6)12 / 6 = 몫이 2, 나머지가 0나머지가 0이 나왔으니, 작은 수인 6이 최대공약수!function gcd(a,b) { if (b == 0) return a; return a > b ? gcd(b, a % b) : gcd(a, b % a);}최소공배수최소 공배수와 최대 공약수의 관계를 이용한다.두 숫자를 곱한 값을 최대공약수로 나누면 최소공배수가 나온다.function lcm(a, b) { return (a *..

string 조작할 때 일반적인 for문으로 전체 순회를 했었다.추가로 알게된 범위 기반 반복문에서 js에서 for in 과 같은 반복문을 사용하는데, 정리하고 되새기려고 기록한다.#include #include using namespace std;int main() { string s = "example"; // 1. 일반 for 루프 for (int i = 0; i

charisalpha(ch) : ch가 알파벳 캐릭터인지 판단isupper(ch) : ch가 대문자인지 판단islower(ch) : ch가 소문자인지 판단isalnum(ch) : ch가 문자 혹은 숫자인지 판단isspace(ch) : ch가 공백문자인지 판단ch = toupper(ch) : ch를 대문자로 변환ch = tolower(ch) : ch를 소문자로 변환stringstr.erase(시작, 개수) : str에서 시작부터 개수만큼의 문자를 지움.이터레이터로 하면 시작~끝으로 지정 가능. 인자 하나만 주면 해당 문자만 지움.str.insert(위치, 문자) : str에서 특정 위치에 문자를 삽입remove(str.begin(), str.end(), 문자) : 범위에서 특정 문자를 제외한 문자들을 앞쪽..

1. 선택 정렬 ( O(n^2) ) : 배열을 차례대로 탐색하며 탐색하는 항 우측의 항 중 최솟값을 찾아서 위치 변경. int i=0;j=0,min=0,index=0,temp=0; int array[10]={1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for(i=0;ij){ temp=data[j]; data[j]=data[key]; data[key]=temp; }else{ //엇갈리지 않았으면 찾은 i와 j 교체. temp=data[j]; data[j]=data[i]; data[i]=temp; } } quickSort(data,start,j-1); //왼쪽 파티션 quickSort(data, j+1, end); //오른쪽 파티션 }