DGOS

[백준] 5525번 IOIOI - C++

문자열

문제 5525번 IOIOI 풀이 처음에는 string의 substr 함수를 이용해서 제출했지만 결과는 시간 초과였다. 굳이 서브 스트링을 매번 만들어서 비교할 필요 없이 더 간단하고 빠르게 푸는 방법이 있었다. 반복문으로 앞에서부터 스트링 S를 확인하며 ‘I’가 나오면 while 문을 통해 IOI가 나올때마다 k에 +1 해준다. k =...

Posted by dongjune on September 27, 2020

[백준] 1992번 쿼드트리 - C++

분할정복, 재귀

문제 1992번 쿼드트리 풀이 분할 정복으로 풀 수 있는 문제이다. 우선 처음에 NxN 크기의 배열을 탐색하며 가장 왼쪽 위의 수와 다른 수가 나오면 (N/2)x(N/2)크기로 4등분하여 재귀 함수를 호출하는 형식으로 구현했다. 4개의 재귀함수를 호출하기 전과 후에 각각 ‘(‘ 와 ‘)’을 출력하여 출력형식을 맞춘다. 코드를 보며 확인해보자. ...

Posted by dongjune on September 27, 2020

[백준] 18870번 좌표 압축 - C++

vector, unique함수

문제 18870번 좌표압축 풀이 algorithm 헤더의 unique 함수를 통해 쉽게 풀 수 있는 문제이다. unique 함수 unique 함수는 연속으로 중복 되는 원소 를 vector의 제일 뒷부분으로 쓰레기 값으로 보낸다. 즉 다시 말해 중복 되지 않는 원소들 만을 앞에서 부터 채운다. 이때 주의할 점은 연속으로 중복 되는 원소만을 없...

Posted by dongjune on September 26, 2020

[Algorithm] 이분탐색 - C++

binary search (이분 탐색)

이분탐색 우리는 배열 {2,3,6,8,10,12,13} 에서 13을 찾고자 한다. 일반적인 탐색 기법으로는 앞에서부터 배열의 요소를 순차적으로 탐색하기 때문에 시간복잡도는 데이터의 개수 만큼이 된다. 즉 O(n) 이 된다. 만일 데이터의 개수가 무수히 많아진다면 굉장히 비효율적인 알고리즘이 된다. 하지만 이분탐색을 사용하면 O(log n) 의 시간복...

Posted by dongjune on September 26, 2020

[백준] 11723번 집합 - C++

비트마스크

문제 11723번 집합 비트마스크 비트마스크에 대해서 처음 알게 된 문제다. 이전에 1«n 은 사용해서 제곱을 구현해본적은 있었지만 &,|와 같은 다양한 연산을 사용할 수 있다는 것을 알았다. 비트 마스크는 알고리즘이라기 보다는 bit를 활용한 테크닉이다. And 연산 (&): 대응하는 두 비트가 모두 1이면 1 반환 101...

Posted by dongjune on September 24, 2020

[백준] 7662번 이중 우선순위 큐 - C++

Multiset

문제 백준 7662번 multiset multiset을 사용하면 쉽게 풀 수 있는 문제이다. 처음으로 set에 대한 개념을 알게 된 문제였다. multiset은 c++의 STL이며 set container와 달리 key가 중복 가능한 set을 구현할 수 있다. multiset헤더가 아닌 set헤더를 통해 사용하는 것을 주의하자. 1 2 3 #...

Posted by dongjune on September 24, 2020

[백준] 2630번 색종이만들기 - C++

분할정복, 재귀

문제 백준 2630번 색종이만들기 풀이 저번에 풀었던 분할정복 문제와 유사하다. 백준 1074번 Z 풀이 재귀 함수를 이용하여 분할정복을 구현했다. 재귀 함수의 인자인 y,x는 현재 탐색하고자 하는 사분면의 가장 왼쪽 위의 좌표이며, size는 사분면의 한 변의 길이이다. 1 2 void solve(int y, int x, int size) ...

Posted by dongjune on September 23, 2020

[백준] 1074번 Z - C++

분할정복, 재귀

문제 1074번 Z 풀이 평소 dp, 그래프탐색, greedy 위주로 문제를 풀다가 거의 처음 마주한 분할정복 문제였다. 감조차 잡히지 않아서 다른 블로그들을 참고하여 이해했다. c++코드 참조한 JeongHyeon님 블로그 개념설명 잘 된 마이구미님 블로그 (이 코드에서 사용한 사분면의 순서는 편의상 수학에서 사용하는 사분면의 순...

Posted by dongjune on September 22, 2020

[백준] 5525번 IOIOI - C++

문자열

[백준] 1992번 쿼드트리 - C++

분할정복, 재귀

[백준] 18870번 좌표 압축 - C++

vector, unique함수

[Algorithm] 이분탐색 - C++

binary search (이분 탐색)

[백준] 11723번 집합 - C++

비트마스크

[백준] 7662번 이중 우선순위 큐 - C++

Multiset

[백준] 2630번 색종이만들기 - C++

분할정복, 재귀

[백준] 1074번 Z - C++

분할정복, 재귀

FEATURED TAGS

ABOUT ME