분류 전체보기
-
비트마스킹(BitMasking) 정리알고리즘/개념 정리 2020. 12. 27. 14:56
비트마스킹(BitMasking) 정리 목차 비트마스킹이란? 비트 켜고 끄기 활용 방법 비트마스킹이란? 비트 마스킹이란, 어떤 정수 값을 비트를 이용해 이진수로 표현하는 방법을 말합니다. 예시를 하나 들어보겠습니다. 책상 5개가 일렬로 있는데 ( . . . . . ) 여기에 사람을 앉히는 경우는 (OXXXXX, OOXXX) 등등 2^5 가지가 있겠죠 이 상태를 모두 표현하여 가지고 있고 싶은데 이 때 활용할 수 있는 방법이 비트마스킹입니다. ex) OOOXX > 이 경우에는 11100(2) == 28 OXXXXO > 이 경우에는 10001(2) == 17 등등 이런식으로 상태를 저장하여 활용하는 방식입니다. 비트마스킹의 이점은 더 적은 메모리로 많은 상태를 표현할 수 있다는 것입니다. 비트 켜고 끄기 비트..
-
LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘알고리즘/개념 정리 2020. 12. 27. 01:26
LCA(Lowest Common Ancestor) / 최소 공유 조상 목차 1. LCA란? 2. O(N) LCA 알고리즘 3. O(logN) LCA 알고리즘 LCA란? LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다. O(N) LCA 알고리즘 자 그러면 이제 LCA 알고리즘을 구현해 봅시다. LCA 구현을 위해 3가지 단계가 필요합니다. 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이)) LCA를 구하려는 두 노드 중 더 깊은 노드의 dep..
-
[DAY10] 말은 누구나 하지카테고리 없음 2020. 12. 25. 22:57
오늘 크리스마스인데, 낮에 내내 대학 동아리 사람들하고 롤하다가 오늘 너무일찍일어나서 저녁먹고 7시에 기절해서 잠들었다 지금일어남 ㅠ 이거 완전 장난으로 24일에자서 26일에 일어나겠다 세미 버전이자나 한달쓰기 놓칠뻔 했다가 간신히 안놓치고 쓴다 내 티스토리 피드에 있었던 분의 글이다 이 분 블로그를 왜 구독했는지는 기억이 잘 안나는데.. 아무튼 "어떤 사람인지를 보려면 그 사람이 그동안 했던 행동와 선택을 봐야한다"는 말이 너무 와닿았다 말은 쉽다. 하지만 그걸 실천으로 옮기는 사람은 많지 않다. 나부터 말보다 선택과 행동으로 보여줄 수 있는 사람이 되길
-
[Oracle] ORA-01747: 열명을 올바르게 지정해 주십시오Programming/SQL ( Oracle ) 2020. 12. 21. 15:28
ORA-01747: 열명을 올바르게 지정해 주십시오 이 에러가 뜨는 이유는, 문구 그대로 열 명을 정확하게 하지 않아서이다. 완전 단순히 문법 오류. 예를들어, UPDATE STUDENT A SET A.NAME = 'KUMA' , A.UPD_DATE = SYSDATE , WHERE A.USER_ID = '1234' 이 SQL의 3번째 줄처럼 , 가 들어가면 안됬는데 들어갔을 경우 발생한다!
-
[백준] 1025 :: 제곱수 찾기알고리즘/BOJ(C++) 2020. 12. 21. 00:11
www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 : 문제 설명 세상 난해해.. 자, 차분히 이해를 해 봅시다. 문제를 읽어보면 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열 이라는 문구가 나옵니다. 이게 무슨 뜻이냐 하면 map[i][j] 이렇게 있을 때 (i,j)의 숫자를 뽑는겁니다. 차례로 (x1,y1) , (x2,y2) , (x3, y3) 뭐이런식으로 뽑아 나가겠죠. 이때 x를 나열했을 때도 등차수열, y를 나열했을..
-
[백준] 4458 :: 첫 글자를 대문자로 ( C++ 한 줄 입력받기, getline 함수 , cin.ignore())알고리즘/BOJ(C++) 2020. 12. 19. 16:50
www.acmicpc.net/problem/4458 4458번: 첫 글자를 대문자로 첫째 줄에 줄의 수 N이 주어진다. 다음 N개의 줄에는 문장이 주어진다. 각 문장에 들어있는 글자의 수는 30을 넘지 않는다. 모든 줄의 첫 번째 글자는 알파벳이다. www.acmicpc.net 원래 이 문제는 너무 간단해보여서 포스팅 안하려다가 딱 하나 정리하려고 쓴다. 테스트 케이스 만큼 한 줄 씩 입력받아야하는데, cin>> 이렇게 쓰면 공백을 기준으로 변수가 저장된다. 그래서 "You are lovely" 이런 문장을 쓰게 되면 You 까지만 입력이 된다. 한 줄을 통째로 입력 받으려면 getline을 써야한다. ex) getline(cin,str) 이렇게 쓰게 되면 '\n'을 기준으로 구분하여 입력을 받을 수 있..
-
[백준] 10250 :: ACM 호텔알고리즘/BOJ(C++) 2020. 12. 19. 16:43
www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제 : 거창한 설명 다 지우고나면 결국, y값이 가장 작고, 그 다음으로 x값이 가장 작을 수 있는 남은 방을 손님에게 배정해라 풀이 : 예를 들어 6, 12, 10 이라면 101 201 301 401 501 601 >>>>>> 102 ... 602 >>>>>>> 103 203 303 403 이런식으로 채워지게 된다. 결국 다음 호수 (1호 다음 2호) 층수만큼 한바퀴를 돌아와야한다는 뜻 그래서 ..
-
[백준] 2583 :: 영역 구하기알고리즘/BOJ(C++) 2020. 12. 19. 16:37
www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 : 영역에 직사각형 그려진 부분 제외하면, 분리 된 부분이 총 몇개 인지, 각 분리된 부분의 영역의 크기는 얼마인지 구해라 풀이 : - MAP에 직사각형이 존재하는 부분 표시 - MAP의 0,0 ~ M,N까지 탐색하면서 색칠되지 않은곳(직사각형이 존재하지 않거나, 이미 탐색되지 않은 곳)이 발견된다면 전체 분리된 개수(ans)에 추가하고, 그 위치에서 BFS 돌리기 - BFS 탐색하면서..