개발/알고리즘

A . Floor Number 방 번호가 주어지고, 해당 방이 몇 층에 있는지 구하는 문제이다. 보이는대로 풀면 된다. 다만 1층에 2개의 방이 있다고 (n-2)/x 를 하면 안 된다. x 가 5이고 2층에 3번 ~ 7번 방이 존재한다면 (7-2)/5 = 1 이기 때문이다. #include using namespace std; int main(void) { int t, n, x; cin>>t; while(t--) { cin>>n>>x; if(nv11>>v12>>v21>>v22; if(v12 == v21) flag = true; } if(m%2) flag = false; if(flag) coutn; checkCount(1); coutn; for(int i=0; i>a[i]; for(int i=0; i>b[..

문제 접근 저번에 '백준 5052번 : 전화번호 목록' 풀고, 트라이 알고리즘을 익히려고 문제를 찾던 중 이 문제를 풀게 되었다. 처음에문제를 보고 set 을 사용하면 될 것 같아서 구조 잡다가 map 로 풀면 안 되는지 아주 잠깐 고민했다. 그런데 이미 주제를 알고있어서 그런지 트라이로 풀어야되는거면 당연히 안 되겠다 싶어서 5052번 코드 가져와서 수정했다. 공백과 특수문자가 포함되는 경우도 있다고 해서, 아스키 코드값 기준 32~126 까지 사용 가능하도록 했다. 종결되는 시점에서 count 값을 1 증가시키고, find 함수를 통해 종결되는 시점의 count 값을 가져오도록 구현했다. 시간 복잡도는 O(문자열의 개수 * 문자열의 최대 길이) 로 O(1,000,000*30) 이다. 다 풀고, 다른 ..

문제 접근 문자열 알고리즘을 아는게 거의 없어서 고민을 많이 했다. 처음에는 큰 것부터 정렬해서 /10 으로 자릿수 낮춰가며 하나씩 확인하면 되는지 시간 복잡도 계산해보니까 O(1,000,000,000) 이어서 안 될 거 같았다. 알고리즘 분류를 보니 트라이를 사용할 수 있다고 해서 '알고리즘 문제해결전략' 책과 다른 사람 코드를 보면서 구현했다. 트라이 구조체를 만들고 phoneNum 배열에 전화번호를 넣은 뒤 하나씩 find 했을때, phoneNum[i] 탐색이 끝나기 전에 해당 노드의 terminal ( 트라이의 종료 노드라면 true, 아니라면 false. default 값은 false. ) 이 true 라면 1을 반환하여 다른 전화번호의 접두사라는 것을 알린다. 문제 코드 #include usi..

문제 접근 처음에는 입력 문자열에서 폭발 문자열을 찾은 뒤 삭제하고 삭제한 위치의 전부터 다시 탐색하는 방법으로 O(입력 문자열 길이) 로 풀려고 했는데 문자열을 삭제하는데 시간이 더 오래 걸려 좋은 방법이 아니라고 생각했다. 문자열 알고리즘을 찾아보던 중 보이어-무어 알고리즘에 대해 알게 되어 이 알고리즘의 접근 방법을 살짝 이용했다. 보이어-무어 알고리즘은 문자열을 오른쪽에서 왼쪽으로 비교하고, 이동은 왼쪽에서 오른쪽으로 하는 방식인데 오른쪽 끝의 문자가 일치하지 않고, 끝 문자가 비교 문자열에 존재하지 않으면 비교 문자열 길이만큼 이동하는 알고리즘이다. 끝 문자가 비교 문자열 내에 존재하는 것까지 확인할 필요는 없어보였고, 스택에 넣다가 끝 문자와 같은 문자가 나오면 앞 문자열을 비교한 뒤 비교 문..

문제 접근 이분 탐색으로 풀면 되는 문제다. 되게 간단한 문제인데 이분 탐색의 세부적인 구조를 제대로 구현하지 못해서 삽질을 많이 했다. 그냥 ans 변수 하나 만들어서 대입해주면 되는건데.. 그래도 이런 저런 테스트 케이스 만들어보는 연습도 되었고, 탐색 구조를 생각해보게 되어 나쁘지만은 않았다. 랜선이 N 개가 되려면 K 개 랜선의 총 길이 / N 보다는 작거나 같아야 하기에 total/N 까지 탐색했다. 간단하게 lgN 번 동안 K 개의 랜선으로 길이가 mid 인 랜선을 얼마나 만들 수 있는지 확인하고, N 개 만큼 만들지 못하면 mid 보다 작은 길이를 탐색, N 개 이상 만든다면 ans 에 mid 를 저장하고 mid 보다 긴 길이를 탐색한다. 왜 이걸 못해서 그렇게 틀렸지.. 코드를 재설계하기보..

문제 접근 C(n) = (2-1)*C(n-2) + C(n-1) = C(n-2) + C(n-1) 이라는 점화식이 나온다. 이유는 C(n-2) 블럭에 2개짜리를 붙이는 경우와, C(n-1) 블럭에 1개짜리를 붙이는 경우를 더한 것에 중복을 제거한 게 C(n) 이기 때문이다. 중복은 2개짜리를 붙일 때 가로 2개와 세로 2개를 붙일 수 있는데 세로 2개는 1개를 붙이는 경우와 중복되기에 2개를 붙일 때 2가지 경우 중 하나는 제외한다. 따라서 위와 같은 점화식이 나오는 것이다. 문제 코드 #include #include using namespace std; int cache[1000]; int dp(int n) { int& res = cache[n]; if(n>n; cout

문제 접근 서문이 굉장히 길었다. 입력부터 읽고 구현하면 된다. vector lib 에 포켓몬의 이름과 번호를 push 하고, 복사한 뒤 sort 해서 문자를 입력 받는다면 binary_search 로 찾았고, 숫자를 입력하면 그냥 바로 출력하도록 구현했다. 문제 코드 #include #include #include #include using namespace std; vector lib; vector sorted_lib; int binary_search(string name, int begin, int end) { int mid = (begin+end)/2; if(name.compare(sorted_lib[mid].first) == 0) return mid; else if(name.compare(sor..

문제 접근 count 가 최소가 되도록 DP 로 구현했다. return 할 때, 1 + ( 세 가지 연산의 각 경우 중 최솟값 ) 을 반환하기에 cache[n] 에는 숫자 n 이 1 로 되는 최소 연산 횟수가 저장되어있고, 이를 통해 중복을 빠르게 처리하여 답을 구할 수 있다. 문제 코드 #include #include #include using namespace std; int cache[1000001]; int count(int n) { int& ret = cache[n]; if(ret != -1) return ret; if(n == 1) return ret=0; int d3,d2,m1; d3=d2=m1=1000001; if(n % 3 == 0 && n > 2) d3 = count(n/3); if(n..