티스토리

개발 공부 공간

검색하기

블로그 홈

개발 공부 공간

d-yong.tistory.com/m

개발 공부 공간

구독자: 4

방명록 방문하기

주요 글 목록

[알고리즘 문제해결전략] ITES - 외계 신호 분석 [생각의 흐름] 1. 수열의 앞에서 부터 하나하나 더하면서 수열의 연속 된 특정 범위 내에서 K값을 찾는다. 2. 수열이 연속해야하기 때문에 맨 앞의 수열은 빼고 맨 뒤의 수열은 넣는 방법 두 가지가 있다. 3. K보다 값이 크면 맨 앞의 수열을 빼고(Pop) K보다 값이 작으면 맨 뒤에 수열을 추가한다(Push). 4. K와 값이 같으면 cnt++; * 맨 처음에는 수열(signal A)를 배열에 초기화 하여 사용하려 했으나 메모리 초과가 발생하여 그때 그때 값을 만들어 내는 방식을 택함. /* https://www.algospot.com/judge/problem/read/ITES */ #include #include #include using namespace std; const long MOD = .. 공감수 0 댓글수 0 2023. 4. 30.
[알고리즘 문제해결전략] NUMB3RS - 두니발 박사의 탈옥 [생각의 흐름] 1. 모든 경로(or 경우의수)를 완전 탐색 해본다. 2. 교도소의 인접한 마을(시작점)에서 탐색을 시작하는 경우 앞의 과정에서 계산한 확률 값이 필요하다. -> 까다로운 점 3. 시작점과 끝점을 뒤집어서 생각해 본다. 4. 끝점에서 시작해서 교됴소의 인접한 마을(시작점)으로 가는 경우만 구해서 확률을 계산한다. /* https://www.algospot.com/judge/problem/read/NUMB3RS# */ #include #include const int MAX_TOWN = 51; const int MAX_DAY = 101; int townMap[MAX_TOWN][MAX_TOWN]; double cache[MAX_DAY][MAX_TOWN]; int numOfConnectedTo.. 공감수 0 댓글수 0 2023. 4. 9.
[알고리즘 문제해결전략] POLY - 폴리오미노 [생각의 흐름] 1. 위에서 아래로 정사각형을 x개씩 채워나간다. 2. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 칸에 채우려는 사각형의 갯수를 알면 경우의 수를 구할 수 있다. ( 윗칸에서 채운 사각형의 수 + 현재 칸을 채우려는 사각형의 수 - 1) 3. 재귀함수를 통해 모든 경우의 수를 구한다. 4. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 사용할 수 있는 남은 사각형(leftBlock)의 갯수를 통해 메모이제이션이 가능하다. /* https://www.algospot.com/judge/problem/read/POLY */ #include #include const int MAX_BLOCK = 101; const int MOD = 10000000; int cache[MAX_BLOCK.. 공감수 0 댓글수 0 2023. 4. 2.
[알고리즘 문제해결전략] ASYMTILING - 비대칭 타일링 [생각의 흐름] 1. 전체 타일설치 경우의 수를 구한다. 2. 대칭인 타일설치 경우의 수를 구해서 뺀다. 3. 대칭인 타일의 경우의 수를 구하는 방법을 n이 짝수일때 홀수일때로 나눈다. 4. n이 짝수인 경우 다시 두가지 경우로 나눌 수 있는데 하나는 n/2로 대칭인 경우와 다른 하나는 전체 타일 가운데를 2x2타일을 배치한 뒤 절반으로 나누는 방법이다. (n-2)/2 n이 홀수인 경우는 자연스럽게 정가운데 타일 하나는 무조건 2x1타일을 배치해야 하기 때문에 (n-1)/2이 된다. 5. 타일의 경우의 수를 나눈 뒤 왼쪽 타일만 채워주면 모든 대칭 타일의 경우의 수를 구할 수 있다. 6. modulo연산에서 주의 할 점이 있는데 (전체 타일의 경우의 수 % MOD) - (대칭인 타일의 경우의 수 % MO.. 공감수 1 댓글수 0 2023. 2. 26.
[알고리즘 문제해결전략] SNAIL - 달팽이 [생각의 흐름] 1. 비오는날(75%)와 비가오지 않는날(25%)을 구분한다. 2. 비오는날과 비가오지 않는 날의 확률을 각각 곱하면서 목적지 (n)에 도달할 때까지 반복해 본다. => 완전탐색 3. 중복되는 경로의 확률을 메모이제이션 한다. 4. m일 안에 목적지 n에 도달했을 경우 1을 리턴하여 모든 경로의 확률을 곱하고 그렇지 않은 경우 0을 리턴하여 경우를 무효화 시킨다. 5. 절대 도달할 수 없는 경우( 예) 1000미터 우물을 100일 안에 도달)는 sol함수를 호출하지 않고 수식으로 가지치기 한다. /* https://www.algospot.com/judge/problem/read/SNAIL */ #include const int MAX_DAYS = 1001; const int MAX_MET.. 공감수 0 댓글수 0 2023. 1. 15.
[알고리즘 문제해결전략] TRIPATHCNT - 삼각형 위의 최대 경로 수 세기 [생각의 흐름] 1. 최대 경로를 먼저 cache한다. (https://d-yong.tistory.com/107 와 동일) 2. 아래로 가는 경우 / 오른쪽 아래로 가는 경우 중 최대 경로가 큰 값을 경우의 수에 추가한다.(단, 두 값이 같은 경우 두 경우의 수를 모두 더한다.) /* https://www.algospot.com/judge/problem/read/TRIPATHCNT */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; int cache[MAX_SIZE][MAX_SIZE]; int cacheCnt[MAX_SIZE][MAX_SIZE]; .. 공감수 0 댓글수 0 2023. 1. 8.
[알고리즘 문제해결전략] TILING2 - 타일 [생각의 흐름] 1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % .. 공감수 0 댓글수 0 2022. 12. 18.
[알고리즘 문제해결전략] QUANTIZE - 양자화 [생각의 흐름] 1. 주어진 입력을 정렬하면 구현이 더 편해진다. 2. 정렬한 뒤 어떠한 기준에 따라 S개로 묶는다(양자화) 3. 어떠한 기준을 정의한다. -> a번째 부터 b번째 까지의 수열에 있는 모든 자연수 중 하나를 선택하여 오차 제곱의 합이 최소가 되는 값을 구한다. (minQuan 함수) /* https://www.algospot.com/judge/problem/read/QUANTIZE */ #include #include #include #include using namespace std; const int MAX_SEQ_SIZE = 111; const int MAX_QUAN_SIZE = 11; const int INF = 987654321; int N, S; int num[MAX_SEQ_S.. 공감수 0 댓글수 0 2022. 12. 18.
[알고리즘 문제해결전략] PI - 원주율 외우기 [생각의 흐름] 1. 문자열을 3, 4, 5개로 쪼갤 수 있기 때문에 재귀함수를 통해 모든 경우의 수를 구할 수 있다. 2. 1234123인 수를 쪼개는 방법은 3, 4 혹은 4, 3이다. 즉, 12341234가 N개 있으면 시간복잡도는 2^N이 된다. => 시간초과예상 3. 재귀함수가 현재 문자열의 position에 있을때 계산이 중복된다. => 메모이제이션 가능 /* https://www.algospot.com/judge/problem/read/PI */ #include #include #include using namespace std; const int INF = 987654321; const int MAX_LEN = 10001; char PI[MAX_LEN]; int cache[MAX_LEN];.. 공감수 0 댓글수 0 2022. 11. 19.
[알고리즘 문제해결전략] JLIS - 합친 LIS [생각의 흐름] - 오답 1. 수열A와 수열B의 LIS를 구해 더한다 -> 위와 같은 로직이면 예제 {10, 20, 30, 1, 2} {10, 20, 30} 일 때 정답은 {10, 20, 30}으로 JLIS의 길이는 3이됨 (정답은 5) 2. 수열A와 수열B의 중복 된 수를 한 쪽 수열에서 제거 한 뒤 각각 LIS를 구해 더한다. -> 문제의 예제에서 정답은 나오나 코드 제출 시 오답나옴 -> 중복이 제거되어도 1과 같은 수열 케이스가 나오면 오답 [생각의 흐름] - 정답 1. 수열A와 수열B의 모든 수를 따지면서 LIS를 구한다. -> "수열A의 수를 선택하거나 수열B의 수를 선택하거나"의 부분문제로 정의한다. 2. cache사용을 위해 계산의 중복이 있는지 찾아본다. -> 예를들어 {1, 5, 9, .. 공감수 4 댓글수 1 2022. 10. 23.
[알고리즘 문제해결전략] LIS - Longest Increasing Sequence LIS 문제를 해결하는 방법은 두 가지가 있다. 1. 수열 중 LIS를 만족하는 모든 경우의 수 확인 + 메모이제이션 / 시간복잡도 (N^2) 2. LIS가 항상 순증가 한다는 특성을 활용한 방법 (길이가 i인 LIS 중 가장 유리한 LIS는 마지막 값이 최소인 LIS) / 시간복잡도 (NlogN) 1번 방식 [생각의 흐름] 1. 재귀 함수를 통해 모든 경우의 수를 구한다. 2. 부분문제로 정의 할 때 현재 수열에서(subsequence[startPosition]) LIS값을 구하는게 최적의 값 3. 메모이제이션을 통해 중복 된 계산을 제거 /* https://www.algospot.com/judge/problem/read/LIS */ #include #include #include using names.. 공감수 5 댓글수 1 2022. 10. 15.
[알고리즘 문제해결전략] TRIANGLEPATH - 삼각형 위의 최대 경로 [생각의 흐름] 1. 완전 탐색을 하게 되면 2^100이라 타임 아웃 발생 2. 동적계획법을 통해 캐싱 3. 캐싱은 cache[Y][X][sum]을 먼저 생각했으나 sum의 경우 100000 * 100이 되어 메모리 초과발생 4. cache[Y][X]가 가능한지 고민 => Y, X일 때 최대값만 구하면 된다. => 아래(Y+1, X)와 오른쪽 아래(Y+1, X+1) 의 값 중 큰 값을 선택 /* https://www.algospot.com/judge/problem/read/TRIANGLEPATH */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; .. 공감수 0 댓글수 0 2022. 10. 3.
[알고리즘 문제해결전략] WILDCARD - 와일드 카드 [생각의 흐름] 1. *을 제외하면 나머지는 그냥 넘어가면 된다(문자가 같다. ?와 '같은 문자'는 동일하게 처리) 2. *를 처리하는 방식은 두 가지로 나눌 수 있다. 1) *를 사용한다. 2) *를 버린다.(사용하지 않는다.) 3. 재귀함수를 돌 때, 와일드 카드와 파일명의 인덱스의 위치에 따라 중복 계산이 발생한다.=> 캐싱가능 /* https://www.algospot.com/judge/problem/read/WILDCARD */ #include #include #include #include #include #include using namespace std; const int MAX_STR = 111; char wildCard[MAX_STR]; char str[50][MAX_STR]; int .. 공감수 0 댓글수 0 2022. 10. 3.
[알고리즘 문제해결전략] JUMPGAME - 외발 뛰기 [생각의 흐름] 1. 완전 탐색으로 솔루션 도출 가능 (오른쪽이동 & 아래이동) 2. map의 각 포지션마다 메모이제이션 가능한 것을 파악 => 어떤 포지션이던 항상 결과는 동일 (참조적 투명성) /* https://www.algospot.com/judge/problem/read/JUMPGAME */ #include const int MAX_MAP_SIZE = 101; int n; int map[MAX_MAP_SIZE][MAX_MAP_SIZE]; int cache[MAX_MAP_SIZE][MAX_MAP_SIZE]; void init() { for (int i = 0; i < MAX_MAP_SIZE; i++) { for (int j = 0; j < MAX_MAP_SIZE; j++) { cache[i][j].. 공감수 0 댓글수 0 2022. 9. 12.
[알고리즘 문제해결전략] FENCE - 울타리 잘라내기 [생각의 흐름] 1. 모든 경우의 수 중 가장 넓은 사각형의 넓이를 구하려고 시도 => N^2으로 시간초과 발생 2. 분할정복을 시도 3. 가운데 사각형을 기준으로 1)왼쪽 전체 사각형 2)오른쪽 전체 사각형 3)가운데 포함 좌우 사각형 추가하는 세가지 경우로 나눔 4. 가운데 포함 좌우 사각형의 경우 좌,우를 선택할 때 높이가 더 높은 사각형부터 추가함 => 작은 사각형을 먼저 추가하면 최대 값을 구할 수 없는 경우가 생김 /* https://www.algospot.com/judge/problem/read/FENCE */ #include #include #include const int MAX_FENCE = 20002; using namespace std; int N; int fenceHeight[MA.. 공감수 0 댓글수 0 2022. 8. 27.
[알고리즘 문제해결전략] QUADTREE - 쿼드 트리 뒤집기 [생각의 흐름] 1. 쿼드 트리의 이해 아래 순서로 흑/백 압축을 한다. 1 2 3 4 2. 쿼드트리 상하 반전 어떻게 처리할까? -> 뭔가 규칙이 있을 것 같다 3. 문제의 example을 보니 1, 2, 3, 4 를 3, 4, 1, 2로 바꾸면 상하반전이 된다. 4. 현재 level에서 노드를 4개로 묶어서 상하반전 시키면 되겠다. 5. x는 어떻게 처리하나? -> 분할정복으로 처리하고 올라온다. /* 쿼드 트리 뒤집기 https://www.algospot.com/judge/problem/read/QUADTREE */ #include #include char str[1001]; int len; void inverseNode(int nodeStart[], int nodeEnd[]) { char tmpS.. 공감수 0 댓글수 0 2022. 8. 7.
[알고리즘 문제해결전략] CLOCKSYNC - 시계 맞추기 [생각의 흐름] 1. 모든 스위치를 무한대로 누르는건 답이 없음 2. [12, 3, 6, 9] 시간의 특성을 보면 어짜피 스위치를 4번 누르면 원래 상태로 돌아옴(한 바퀴 돔) and 한 바퀴 돌았을 때 다른 연산에 영향을 주지 않음 3. 0번째 스위치부터 0번 누르고 -> 1번째 스위치 -> .... , 1번 누르고 1번째 스위치 -> ... , 2번 누르고 1번째 스위치... 하나의 스위치당 총 4개의 경우를 통해 최소한으로 스위치를 누를 수 있는 경우의 수를 구함. 4. 시간 복잡도는 각각의 스위치가 선택할 수 있는 경우의 수는 4가지 이기 때문에 4(개)^10(개의 스위치)로 시간안에 들어올 것으로 판단 /* https://www.algospot.com/judge/problem/read/CLOCK.. 공감수 0 댓글수 0 2022. 7. 10.
[알고리즘 문제해결전략] BOARDCOVER - 게임판 덮기 [생각의 흐름] 1. 보드의 왼쪽 위에서 부터 블록을 채운다. 2. 블록 타입의 경우의수는 4개 -> 기준 점 x, y에서 블록 모양을 만들어보면 4가지 나옴 3. 왼쪽 위에서부터 가능한 모든 블록을 넣어본다. 4. 보드 범위를 넘어가지 않고 흰색이 아닌 칸을 예외처리 5. 기저사례(모든 블록이 채워지는 경우) 1을 리턴한다. /* BOARDCOVER 게임판 덮기 https://www.algospot.com/judge/problem/read/BOARDCOVER */ #include const int MAX_BOARD_SIZE = 22; const int BLOCK_TYPE = 4; char board[MAX_BOARD_SIZE][MAX_BOARD_SIZE]; int H, W; // L자 모양 블록을 회전.. 공감수 0 댓글수 0 2022. 7. 3.
[알고리즘 문제해결전략] PICNIC - 소풍 https://www.algospot.com/judge/problem/read/PICNIC [생각의 흐름] 1. 완전탐색으로 짝을 구한다. 2. 친구 관계를 2차원 vector로 추상화 한다. 3. 짝이 지어졌는지 확인하기 위해 boolean타입 isPiar배열로 체크한다. 4. (1,0) (0,1)과 같은 중복케이스를 제거하기 위해 순차적으로 짝을 정해준다 (0, 1)만 가능하게 /* 소풍 PICNIC https://www.algospot.com/judge/problem/read/PICNIC */ #include #include #include using namespace std; const int MAX_CHILDREN = 10; bool isPair[MAX_CHILDREN]; int C, n, m,.. 공감수 0 댓글수 0 2022. 6. 19.
[알고리즘 문제해결전략] BOGGLE - 보글 게임 https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com [생각의 흐름] 1. 시작 위치를 정한뒤 8방향으로 완전 탐색을 해보자 -> 완전탐색 시 timeout 발생 2. DP문제임을 고려해보고 중복되는(연산) 부분 고민 -> 단어의 현재 알파벳위치와 x, y의 값을 이용하면 캐싱 가능? -> 경우의 수는 항상 같기 때문에 캐싱 가능 -> 메모이제이션으로 시간초과 해결 /* BOGGLE 보글 게임 htt.. 공감수 0 댓글수 0 2022. 6. 19.
[무식하게 풀기 - 재귀] N개의 원소중 M개를 고르는 모든 조합 찾는 방법 골라야 할 원소의 수(M)가 입력에 따라 달라지는 경우 반복문 보다 재귀를 사용하면 유연하게 대처할 수 있다. 0부터 N-1까지의 수중에 M개를 고르는 모든 경우의 수를 구하는 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include using namespace std; int maxN, maxM; void printNumber(vector& picked) { int cnt = picked.size(); for(int i=0; i 공감수 0 댓글수 0 2020. 2. 22.
비트연산 - 비트 연산자AND 연산 a & bOR 연산 a | bXOR 연산 a ^ bNOT 연산 ~aa를 왼쪽으로 b만큼 시프트 ab - 유의할 점1) 연산자 우선 순위비트 연산자는 == , != 보다 우선순위가 낮다.그래서 if(a&b==4) 같은 코드는 주의! if((a&b)==4)처럼 무조건 괄호를 사용해주는게 좋다. 2) 64비트 오버 플로우unsinged long long a = (1 공감수 0 댓글수 0 2018. 2. 6.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.