투 포인터 썸네일형 리스트형 백준 2473 세 용액 바로 이전에 푼 문제보다 조금 쉬운 문제이다. 저번 문제는 3명의 합이 0인 개수를 구하는 문제였고, 이번에는 합의 절대값이 최소인 것만 찾으면 된다. 정말 간단하다. 투 포인터 방향은 쉽게 잡았다. 문제도 유사해서 문제에서 제공하는 테스트케이스는 돌아가게 쉽게 만들었다. 문제는, 악마는 디테일에 있다는 것. 생각없이 int로 만든것을 보고 long long으로 바꿨다. 그래도 특정 %에서 틀렸습니다가 나왔다. 문제질문 보면 다양한 사례가 있더라. int - long long 범위 문제도 많았고, 중간에 특성값 계산할때 절대값 연산을 하는게 편한데 그때 abs() 함수에서 문제가 발생한 사례도 있었다. 컴파일러 구현체마다 std::abs가 아닌 그냥 abs를 int abs(int , int) 이렇게 받을.. 더보기 백준 3151 합이 0 오늘은 좀 쉬운거 잡고 오전에 다른거 해야지 했는데 예상보다 날 많이 괴롭혔다 이 문제가. 투 포인터를 사용하는 나쁘지 않은 편한 문제이다. 처음 보았을 때 정렬을 해두고 어떤 한 원소를 고정해두고 나머지 원소들을 투 포인터로 탐색하며 조합을 찾으면 좋겠다고 생각했다. 처음에는 선정한 한 개를 빼고 나머지들에서 투 포인터 탐색을 구현했다. 그렇게 되니 막 중복으로 찾고 난리가 나더라. 다시 생각해보니 어떤 원소 하나를 정하고 그 다음것부터 마지막까지만 계산하면 되는 문제였다. 그렇게 짜고 나니, 같은 값의 원소가 많이 있을 수 있다는 점이 걸렸다. L과 R이 가르키는 원소가 조합을 만족할 때, 우리는 두가지 상황에 빠진다. 하나는 두 원소가 값이 같을 경우. 이 때는 해당 값이 몇개 있는지 확인하고, k.. 더보기 백준 14572 스터디 그룹 조건에 맞는 학생들의 조합을 찾는 문제이다. 각 학생은 3개의 데이터를 가지고 있다. 실력, 알고 있는 알고리즘 수, 알고리즘 종류들. 여기서 데이터 표현을 좀 따져봐야 하는것은 알고리즘 종류이다. 각 학생별로 최대 30개의 알고리즘을 알 수 있는데, 이걸 Vector로 하나하나 저장하자니 나중에 그룹별로 어떻게 아는지 확인하기에 좋지 않다. 그렇다고 bool 배열 만들자니 뭔가 정신없고. 나는 이걸 Bitmask로 표현했다. int 형 변수가 32비트니까 30개까지의 알고리즘을 알고/모르고를 전부 표현할 수 있다. 그 외에는 투 포인터를 사용해 그룹을 탐색하는것은 똑같다. L, R을 가지고 R을 늘리며 탐색하다가, 조건에 안맞으면 L을 하나 늘리고, 빠진 원소에 대한 연산을 한다. 여기에 더해, 그룹 .. 더보기 백준 16161 가장 긴 증가하는 팰린드롬 부분수열 이름이 참 길다. 그리고 그 이름이 내용을 전부 말해준다. 팰린드롬 수열은, 앞에서부터 읽을때와 뒤에서부터 읽을 때 모두 같은 수열을 말한다. 한때 유행어였던, 내이름은 이효리 거꾸로해도 이효리 의 숫자 버전이라고 할 수 있다. 근데 또 이 수열이 증가해야한다. 팰린드롬 수열의 중간(반복되기 시작하는 지점)까지 계속 수가 늘어나야 한다. 같아도 안된다. 주어진 수열에서 해당 조건에 맞는 가장 긴 수열의 길이를 구하는 문제이다. 처음, 모든 수열의 체크할 수는 없고, 무조건 연속되어야 하니 투 포인터를 사용해 접근했다. 투 포인터에 대한 자세한 설명은 여기 되어있다. L과 R을 하나씩 움직이며 수열을 체크했다. 우리의 L과 R은 처음에 모두 0으로 설정되어있다. 이때, 현재 R과 그 다음이 연속적으로 계속.. 더보기 백준 1644 소수의 연속합 소수들의 연속합을 구하는 문제이다. 어떤 수를 입력으로 받아, 그 수를 소수의 연속합으로 어떻게 표현할 수 있는지 개수를 출력해주면 된다. 문제 제목이 너무 문제 내용이다... 일단 소수의 리스트를 가지고 있어야 하므로, 에라토스테네스의 체를 사용해 N의 최대범위 안의 모든 소수를 구한다. 소수의 리스트를 완성한 후, 투 포인터 알고리즘을 사용해 연속합을 구해가며 자연수 N을 찾는다. 소수가 들어있는 배열이 있고, 그 배열의 원소를 가르키는 Right(R) 인덱스와, Left(L) 인덱스를 만든다. 두 인덱스는 첫번째 원소를 가르킨다. 여기에, 현재 합을 저장하는 sum 변수를 만들어 주면 연산할 준비가 되었다. 만약, sum이 우리가 찾는 N 보다 작으면 R을 한칸 증가시킨다. R을 증가시키고, R이 .. 더보기 이전 1 다음
