티스토리

KMS_studio programming
검색하기

블로그 홈

KMS_studio programming

kms-program.tistory.com/m

this is the signature project which made by KMS studio if you find error about my program, please give E-mail to tomskang@naver.com

구독자
0
방명록 방문하기
공지 저의 이전 블로그를 소개합니다. 모두보기

주요 글 목록

  • 백준 1202 보석 도둑 (boj/1202.cpp) 그리디, 이진탐색을 엮은 문제입니다. union-find의 find알고리즘을 조금 차용하여 구현했습니다. 보석이 들어갈 수 있는 가장 작은 가방을 찾은 다음, 그 가방보다 크기가 크거나 같고 && 비어있는 가방을 찾습니다. 이때 비어있다의 조건은 nxt[cur]==cur입니다. #include #include #include using namespace std; int N, K; vector J; vector nxt; vector B; int find(int cur){ if(cur>=K || nxt[cur]==cur){ return cur; } return nxt[cur]=find(nxt[cur]); } void put(int cur){ if(cur>=K){ ret.. 공감수 0 댓글수 0 2024. 1. 30.
  • 백준 7469번 K번째 수 (boj/7469.c) * 글을 잘못읽어서 오버스펙인 코드를 만들어버렸다..... 배열에 "서로 다른" 수 N개라 했는데..... 왜 수가 같은 경우를 상정했는지.... 어휴 세그먼트 트리를 조금 새롭게 응용하는 문제입니다. 세그먼트 트리 + 부분정렬 + 특수이진탐색을 사용합니다. 어떤 범위에서 수 A가 K번째 수라는 의미는, 그 범위에서 A보다 작거나 같은 수가 K-1개 있다는 뜻입니다. 더 정확하게 들어가보자면, 어떤 범위에서 A보다 작은 수가 omin개, A보다 작거나 같은 수가 omax개 있다면, 수 A는 범위에서 omin+1번째 ~ omax번째 수가 됩니다. 이때 omin+1 공감수 0 댓글수 1 2024. 1. 23.
  • 백준 6987번 월드컵 (boj/6987.c) 비트마스킹을 사용합니다. 8진법 마스킹, 3진법 마스킹을 사용하는데요, 설명보다 코드를 보는 편이 더 이해가 빠르실겁니다. 시간복잡도는 정확하게는 잘 모르겠으나 얼마 안 나옵니다. 팀의 수 n=6에서 대략 350번? 쯤 for문을 돕니다. #include #include typedef long long lint; int co_game(int game){ return 2-game; } int solve(lint mask, int num){ lint lim, calc; lint new_mask; int game[3] = { 0, }; int temp[3] = { 0, }; int val, cnt, sft; int res=0; if(!num){ return mask?0:1; } game[2]=mask>>6&0.. 공감수 0 댓글수 0 2024. 1. 23.
  • 백준 1310번 달리기 코스 (boj/1310.cpp) Convex Hull Algorithm을 사용합니다. 알고리즘으로 외곽껍질을 구한 다음, 그 껍질을 돌면서 값을 찾습니다. 그냥 동적계획법 두 번 쓴거라 생각하면 마음이 편합니다. 공간복잡도는 N, 시간복잡도는 NlogN이 되겠습니다. #include #include #include #include #define INF 110000 using namespace std; vector > coor; vector > pq; vector cha; double dst(pair fir, pair sec){ return sqrt(pow(fir.first-sec.first, 2) + pow(fir.second-sec.secon.. 공감수 0 댓글수 1 2024. 1. 22.
  • 백준 13977번 이항 계수와 쿼리 (boj/13977.c) 확장유클라디안 알고리즘으과 메모이제이션을 사용하는 문제입니다. 모든 팩토리얼에 대해 normal modular와 inverse modular를 계산한 뒤, 입력값에 따라 처리합니다. 시간복잡도는 N의 최대값을 N, 제수를 M이라 할 때 O(NlogM)입니다. #include #include #define MOD_N 1000000007 #define MAX_N 4000000 typedef long long lint; int mem[MAX_N+1] = { 0, }; int inv[MAX_N+1] = { 0, }; int EEA(int i, int m){ int Q, Q1, Q2; int S, S1, S2; int T, T1, T2; int M; Q1=i; Q2=m; S1=T2=1; S2=T1=0; for(;.. 공감수 0 댓글수 1 2024. 1. 21.
  • 백준 1786번 찾기 (boj/1786.c) KMP 알고리즘 문제입니다. #include #include #define MAX_N 1000002 char T[MAX_N] = { 0, }; char P[MAX_N] = { 0, }; int pi[MAX_N] = { 0, }; int res[MAX_N]; int main(void){ int lenT, lenP; int cur, loc, cnt; fgets(T, MAX_N, stdin); fgets(P, MAX_N, stdin); lenT=strlen(T); lenP=strlen(P); lenT--; lenP--; T[lenT]=P[lenP]=0; pi[0] = -1; for(int i=1;i 공감수 0 댓글수 0 2024. 1. 18.
  • 백준 3015번 오아시스 재결합 (boj/3015.c) 조금 새로운 이진탐색 문제입니다. 직관적으로는 스택을 사용해서 풀 수 있지만 그렇게 풀면 시간복잡도가 N^2이 되버리므로 나락을 가버립니다. 스택에 들어가는 값이 항상 정렬되있다는 사실을 활용, 이진탐색으로 시간복잡도를 NlogN까지 올릴 수 있습니다. #include int stk[500000] = { 0, }; int srcs(int val, int sze){ int lft=0, rht=sze-1, mid; for(mid=(lft+rht)/2;lft 공감수 0 댓글수 0 2024. 1. 15.
  • 백준 2618번 경찰차 (boj/2618.c) DP문제입니다. 공간복잡도 O(W^2), 시간복잡도 O(W^2)으로 해결가능합니다. 또한 각 사건마다 할당된 경찰관을 묻고 있기 때문에 간단한 자취 남기기 기법을 응용합니다. DP의 구성은 아래와 같습니다. 회색 영역은 초기화 때 계산됩니다. 빗금 영역에 있는 값 중 최소의 값을 문제의 답으로 결정합니다. 한 번에 계산되는 양은 아래와 같습니다. 코드는 아래와 같습니다. #include #include #define SZE 1000 int dp[SZE+1][SZE+1]; int idx[SZE+1][2]; int giv[SZE+1] = { 0, }; typedef struct _p{ int row; int col; }point; point loc[SZE+1]; int get_dst(point p1, poi.. 공감수 0 댓글수 0 2024. 1. 14.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.