데이터 탐색 방법 1) 순차탐색 : 순차적으로 하나씩 확인하여 탐색 2) 이분탐색 : 범위를 반씩 좁혀가면서 데이터 빠르게 탐색 왜 필요한가? 일반적인 O(n)탐색이 불가능할때 값을 찾는 시간이 굉장히 오래걸릴때! 이분탐색 알고리즘 : 데이터의 범위를 추측해서 탐색 - 배열(벡터 )정렬 - left(최소), right(최대)를 지정 - mid = (left+right)/2 - mid와 찾는값 (key)비교 mid key라면, right = mid-1로 갱신 -반복문 /재귀 종료 조건 mid ==key: key값을 찾은경우 left>right :배열에 key값이 존재하지 않는경우 1~2^63 : left : right mid 값의 제곱이 찾는 값이..

1. 색종이 만들기 알고리즘 문제를 풀때 nxn의 격자판을 가지는 그림이 있다라면 알고리즘 좌표계에서는 1,1에서 오른쪽으로 가면 y값 증가 1,1에서 아래쪽으로 가면 x값 증가로 좌표계가 표현되어 마지막에 n,n 2. 종이의 개수 9개로 나누므로, 한 종이의 길이는 len/3 return문이 있어야 계속반복하는것을 막음 3. 쿼드트리 한가지의 숫자로 이루어져있지 않고 4등분 할때 괄호가 열림 4등분으로 나눈거를 다 보고나면 괄호 닫힘 %1d 는 한자릿수의 입력을 받아 구분 추가적으로 만약 23:59 형식으로 받아야 하는게 정해져있다면 scanf가 알아서 : 기준으로 구분됨 scanf("%d:%d") 4. Z문제 1초에 for문 1억번 걸리는 연산이 1억번 걸린다 : 1초 근데 이 문제의 조건은 n은 1..

큰 문제를 작은 문제로 쪼개서 해결하는것 1) 큰문제를 작은문제로 분할 2) 문제가 조건을 만족하거나 더이상 나눠지지 않으면 문제해결 3) 작은문제들의 해답을 통합하여 큰 문제를 해결 ex) 2630번 색종이 만들기 1. 같은색으로 칠해져있는지 확인한다 1.1 같은색으로 칠해져있지 않다면 나눈다 #include #include using namespace std; int N; int arr[256][256]; int color[3]; void go(int size, int Y, int X) { if (size == 1) { color[arr[Y][X]]++; return; } int check = arr[Y][X]; for (int i = Y; i < Y + size; i++) { for (int j =..

완전탐색과 재귀함수 1. 완전탐색 영어로 브루투 포스 혹은 전수조사 라고함. 모든 경우의 수를 확인하는 방법 알고리즘은 아님 - 장점 :상대적으로 구현이 쉽고, 모든 문제에 대한 접근이 가능 - 단점: 모든 경우의 수를 확인해야 하므로 시간이 많이 듦 1) 사전식 순열 / 중복을 제거한 사전식 순열 - 주어진 숫자들로만들수 있는 모든 사전식 순열 확인하기/ 중복을 제거한 모든 사전식 순열 확인하기 2) 백 트래킹 -가지치기를 하면서 문제를 해결하는 알고리즘 3) BFS/DFS - 그래프의 모든 정점을 탐색하는 완전 탐색 알고리즘 ex)) 최댓값 9개의 수에 대해 전부 확인하며 최댓값을 갱신해 출력하는 문제 ex))문서검색 문서의 모든 인덱스에 대해 확인하는 문제 ex)) 일곱 난쟁이 9명중에서 2명을 제..

16504 종이접기 : 10818 sort(v.begin(),b.end()) 오름차순이라서 인덱스 처음과 마지막이 최소, 최대임 2750 콘테스트 5576 오름차순 한다음에 (reverse)내림차순 각각해서 인덱스 0,1,2 더하면되겠네.. ATM 11399 17262 난쟁이 11728 배열합치기 콘도선정 1181 11650 배운걸 써먹자.. pair라던가,,ㅎ 1026 5648

6550, 부분문자열 13 14 15 16 너무 어려운걸?

오타맨 고창영 2711번 3 4번 하얀칸 1716번 암호 6번 아니 다 보면 .. 답의 언저리에는 가는데 끝이 안나는 편이네 나는 ㅋㅋ 7번 문자메시지 8 Go Latin 어우 이거 노가다네.. 10 팰린 드로미터 엥 이거 인터넷에있는거랑 똑같다..그분이신가

다차원 배열 - 이차원 배열 : 배열의 요소로 1차원 배열을 가지는 배열 행의 길이는 입력하는 만큼 자동으로 설정됨 열의 길이는 반드시 명시해야함 명시된 열의 길이만큼 초기화하지 않을 경우 0으로 자동초기화 ex) 하얀 칸 문제 2차원 벡터 - 벡터의 요소로 또 다른 벡터를 가지는 벡터를 의미한다. -각 행에 일차원 벡터가 삽입이 되는 벡터 행에 추가 벡터이름.push_back(삽입할 일차원 벡터); 열에 추가 벡터이름[row].push_back(지정된 행 벡터에 삽입할 값); empty() 벡터이름.empty() 벡터이름[row].empty() size() 벡터이름.size() 벡터이름[row].size() 2차원배열과 2차원 벡터의 차이점 행마다 열의 크기가 다를 수 있다 : 벡터 행은 크기가 선언안..

10093은 longlong 으로 하는이유가 10^15가 int의 범위를 벗어나서임 45479' 방문배열에 추가 스위치

01 벡터 요소가 추가,삭제될때마다 자동으로 메모리를 재 할당하여 크기를 동적으로 변경할 수 있는 시퀀스 컨테이너 vector 객체이름 (초기크기): -빈칸 만들고싶을때 초기크기 0 - vector 헤더파일 필수 - 자동으로 메모리 할당되는 배열 - 인덱스를 이용한 요소접근가능 vector 객체이름 : 비어있는 벡터생성 vector 객체이름 (크기,값) :명시된 값을 명시된 크기만큼 갖는 벡터 생성 vector 객체이름 (벡터): 명시된 벡터를 복사해서 생성 벡터 멤버함수 객체이름.함수() push_back(값) - 현재 벡터의 마지막 위치에 새로운 원소삽입 - 벡터 크기 1증가 pop_back() -벡터의 마지막 원소 제거 - 벡터 비어있을 경우 오류 size() - empty() - 벡터에 원소가 존..