본문 바로가기

알고리즘

백준 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이 .. 더보기
백준 9527 1의 개수 세기 두 수를 입력받아 두 수 사이의 모든 수를 2진수로 표현했을때 1의 개수를 구하는 문제이다. 일단, 문제 접근을 1 부터 어떤 숫자까지의 범위에서 1의 개수를 구하는 것으로 생각하고 시작했다. MSB가 2^k일때, 그 이진수 숫자가 표현할 수 있는 모든 숫자의 1의 수를 d[k]라고 하자. (k 는 0부터 시작) d[k]는 d[k-1] + d[k-1] + 2^k로 표현 가능하다. 첫번째 d[k - 1]는 k번째 bit 꺼져있을때 밑 자리 애들의 합이고, 두번째 d[k - 1]은 k 번째 bit가 켜져있을때 밑 자리 애들의 합이다. 그 뒤 2^k는 k번째 bit가 켜졌을 때의 개수를 합하였다. 이 방식으로, d[k] 배열을 만들 수 있다. 이 배열을 완성시키고 나서 1 ~ 입력한 수 까지의 1 개수를 구하.. 더보기
백준 1987 알파벳 DFS로 탐색하는 문제이다. 일단 쭈우욱 탐색을 하는 중에는, 이미 지나온 알파벳이 중복으로 나타날 수 없다. 가장 길게 이을 수 있는 칸 수를 구하면 된다. DFS함수는 상하좌우 픽셀의 탐색가능여부를 확인 후, 다른 픽셀로 넘어가기 전에 현재 알파벳 방문을 표시한다. 이 과정이 없으면, 다음 픽셀을 탐색할때 중복되는 알파벳을 포함하므로 끝도없이 이어지게 된다.("ABBDSAAAAADDAAAAA..." 같이) 원래 Visit 배열이 아닌, 상태를 나타내는 구조체에 string으로 지금까지 방문한 문자열을 저장하고, 마지막 탐색이 막히면 그 때 string의 길이를 리턴하는 방식으로 작성했는데, 매 번 string에서 find를 해야 하고 어차피 알파벳은 개수가 정해져 있으니 배열을 만들어 인덱스로 접근하.. 더보기
백준 3109 빵집 원웅이의 범죄행위를 도와주어야 하는 문제이다. 가장 왼쪽 열에서 가장 오른쪽 열까지 우상, 우, 우하로 움직이며 경로가 몇개가 되는지 구하는 문제이다. 각 경로는 서로 겹쳐서는 안된다. 경로를 찾을때는 DFS로 탐색을 한다. 현재 픽셀에서 우상, 우, 우하로 탐색하면서 재귀로 호출한다. - 우상, 우, 우하 탐색을 했을 때 전부 true가 없으면 false를 최종적으로 리턴하게 된다. 만약 현재 픽셀이 가장 오른쪽 열이라면, true를 리턴한다. DFS를 짤 때, 재귀로 일단 생각하게 되는데 앞으로 풀어볼 때는 재귀가 아닌 코드로 한번 작성해보아야겠다. 재귀로 짤 경우 디버그가... 너무... 힘들다... Visit[][] 배열은 Map 크기와 동일하게 만들어서 각 픽셀을 방문할때마다 true로 만든다... 더보기

티스토리툴바