분류 전체보기 (106) 썸네일형 리스트형 200124 - 백준 100문제를 풀고 느낀 점 IT회사(카카오,네이버,라인) 입사를 목표로 달리기 시작한지 한 달도 안되었다. 학교 조교일 + 오픽 때문에 한달동안 100문제밖에 풀지 못했다. PS가 입사준비의 전부는 아니겠지만 일단 겨울방학때 내가 할 수 있는 최선이다. 여름 인턴을 목표로!! 1. 난 아직 ㅈ밥이다. 2. 알면 알수록 풀면 풀수록 많이 보이는 PS의 세계. 3. 못풀겠는 문제는 10분이상 생각해보고 안되면 바로 AC받은 코드보자.(그래야 공부의 속도가 난다.) 4. 이정도 푸니까 입사문제 중에 쉬운 문제들을 풀 수 있는 기초가 생긴듯. 만약 완전탐색까지 공부를 어느정도 끝낸다면, 점점 속도감 있게 공부가 가능할 것이라고 (감히) 예상 5. dp와 dfs bfs 문제들이 진짜 양도 많고 중요도도 높은듯. 입출력 DP1 그래프(dfs.. 백준 1780 종이의 개수 - 분할정복 - C++ https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 전형적인 분할정복 알고리즘이다. n*n짜리 배열에서 같은 숫자가 나오면 패스고, 다른 숫자가 검출이 되면 n/3*n/3짜리 배열 9개.. 알고리즘 PS에 유용한 STL 블로그 링크 - upper_bound, lower_bound upper bound는 key값을 초과하는 가장 첫번째 원소의 위치. lower bound는 key값 이상(같아도됨)인 수가 처음으로 등장하는 원소의 위치. https://blockdmask.tistory.com/168 - next_permutation : 벡터의 순열을 다 구해줌. 벡터에 123 이 있으면 321까지 6개. https://twpower.github.io/82-next_permutation-and-prev_permutation -substr : 어떤 문자열의 substring을 처리하는 stl. 알아두면 문자열 처리하는 데있어서 시간을 많이 세이브 할 수 있을 것 같다. https://modoocode.com/235 백준 2110 공유기 설치 - 이분탐색 C++ https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net main 함수의 이분탐색 방식은 똑같고, 어떤 interval을 두고 공유기를 설치할수 있냐 없냐를 판단 하는 여부가 조금 까다로운 부분이지 않았나 싶었다. 13번째 줄에 current_x를 current_x+interval로 두지 않고 x[i]로 두어야 하는 부분을 조심하자. 어떤 인터벌을 두고 공유기를 n개 이상 설.. 백준 2805 나무자르기 - 이분탐색 C++ (미완) https://www.acmicpc.net/problem/2805 불러오는 중입니다... 이 문제도 이분탐색을 물어보는 문제였다. 랜선자르기 문제(1654번)과 거의 동일한 구조이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include using namespace std; int N; long long meter_of_tree; long long tree[1000001]; bool ispossible(int height){ long long count=0; for(int i=0; iheight) count+=tr.. 백준 1654 랜선자르기(이분탐색)-C++ https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 오늘부터 이분탐색 문제를 풀기 시작했다. 이분탐색 알고리즘은 간단하다. 찾고자 하는 값을 정렬시킨다음에(여기서는 자르려는 길이이므로 정렬할 필요가 없음) 제일 큰값 제일 작은값의 중간을 탐색. 그것보다 크냐 작냐를 가지고 최댓값 또.. 백준 9663 N-Queen (백트래킹(가지치기), 재귀함수) - C++ https://www.acmicpc.net/problem/9663 재귀함수 문제이다. 맨 처음에 자료구조였나,, 이문제를 들었던 적이 있는데 그때는 나한테 너무나도 어렵게 느껴졌었는데 지금은 어떻게 풀어야하는 아이디어가 대략 있으니까 어렵지 않게 구현한 것 같다. col[i] 는 우선 i번째 열의 행 값이다.(위에서부터 몇번째 행에 있는지) 1열부터 해서 값을 설정한 다음에, 그 다음열부터 이전 열들에 위치한 행값을 비교하면서 N번째까지 갔을 경우 1증가, 아닐시 false를 반환하고 끝내면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include using namespace s.. C++ STL::Deque deque에 대해서 처음 알았을때 vector보다 편한 containor임을 보고 느꼈다. 우선 성능적으로도 vector는 새로운 원소가 들어오면 메모리를 재할당해서 이전 원소를 복사하지만 deque는 메모리가 부족할때마다 여러개의 메모리 블록을 할당하므로 이전 원소를 복사할 필요가 없는 구조이다. 가장 그리고 (PS를 풀면서 필요하다고 느낀) pop_front 같은 기능이 있다는 것이다!!(처음 알았다.) 왜냐면 vector에는 없기 때문에.. 여러모로 vector의 상위호환 구조라고 생각이 든다. deque의 선언은 deque dq; 꼴임. deque name; deque값의 삭제같은 것은 밑의 iterator를 활용해야 한다. 활용방법은 나중에 수정해서 올리겠다. 1 2 3 4 5 6 7 8 9 1.. 이전 1 ··· 9 10 11 12 13 14 다음
