본문 바로가기

전체 글

백준 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 개수를 구하.. 더보기
라인 카카오 코테 와=후 털리고 왔다. 코테 공부 시작한지 얼마 되지도 않았고, 문제만 보고 오자... 라고 말도 했고 마음도 먹었는데, 쥐꼬리만큼 기대한건 어쩔 수 없다... 기대한만큼 살짝 실망을 했다... 그래도 공부 안하고 있다가 봤다면 이만큼 풀지도 못했겠지. 카카오 코테에서 풀던 문제 진짜 코드 한줄만 넣었으면 통관데 아깝다. 마지막 10초 전까지 코드 수정하다가 채점결과 뜨면서 테스트가 종료되었습니다 뜨더라... 으악~ 꾸준히 공부하자... 그냥 어제보다 나은 오늘, 어제의 나보다 조금이라도 나은 내가 되는 것에 목표를 두어야지. 더보기
백준 1987 알파벳 DFS로 탐색하는 문제이다. 일단 쭈우욱 탐색을 하는 중에는, 이미 지나온 알파벳이 중복으로 나타날 수 없다. 가장 길게 이을 수 있는 칸 수를 구하면 된다. DFS함수는 상하좌우 픽셀의 탐색가능여부를 확인 후, 다른 픽셀로 넘어가기 전에 현재 알파벳 방문을 표시한다. 이 과정이 없으면, 다음 픽셀을 탐색할때 중복되는 알파벳을 포함하므로 끝도없이 이어지게 된다.("ABBDSAAAAADDAAAAA..." 같이) 원래 Visit 배열이 아닌, 상태를 나타내는 구조체에 string으로 지금까지 방문한 문자열을 저장하고, 마지막 탐색이 막히면 그 때 string의 길이를 리턴하는 방식으로 작성했는데, 매 번 string에서 find를 해야 하고 어차피 알파벳은 개수가 정해져 있으니 배열을 만들어 인덱스로 접근하.. 더보기
백준 3109 빵집 원웅이의 범죄행위를 도와주어야 하는 문제이다. 가장 왼쪽 열에서 가장 오른쪽 열까지 우상, 우, 우하로 움직이며 경로가 몇개가 되는지 구하는 문제이다. 각 경로는 서로 겹쳐서는 안된다. 경로를 찾을때는 DFS로 탐색을 한다. 현재 픽셀에서 우상, 우, 우하로 탐색하면서 재귀로 호출한다. - 우상, 우, 우하 탐색을 했을 때 전부 true가 없으면 false를 최종적으로 리턴하게 된다. 만약 현재 픽셀이 가장 오른쪽 열이라면, true를 리턴한다. DFS를 짤 때, 재귀로 일단 생각하게 되는데 앞으로 풀어볼 때는 재귀가 아닌 코드로 한번 작성해보아야겠다. 재귀로 짤 경우 디버그가... 너무... 힘들다... Visit[][] 배열은 Map 크기와 동일하게 만들어서 각 픽셀을 방문할때마다 true로 만든다... 더보기
백준 1167 트리의 지름 트리를 받아. 트리에서 나올 수 있는 가장 긴 거리(트리의 지름)를 구하는 문제이다. 원래 구현은 각 노드에서 DFS를 해 그 중에서 가장 긴 값을 구하는 코드를 작성했다. 우왕 탐색코드만 짜고 돌기만 하면 되네! 했는데 당연하게도 타임아웃이 떴다. 가장 긴 길이를 더 빠르게 구할 방법이 없을까 했는데 질문들을 보니 2번이면 계산이 가능하다고 한다. 머리로 여러번 생각해봤는데, 도저히 답이 안나와서 한걸음 떨어져서 생각해보니 그래프와 트리를 막 섞어서 생각하고 있었다. 트리의 경우, 무조건 어느 노드는 말단이 있다. 일단 아무 노드에서 가장 먼 노드를 구하고, 거기서부터 가장 먼 거리를 구하면 그게 바로 트리에서 나올 수 있는 가장 긴 거리이다. 그러면 2번만에 된다는 말이 맞다. 첫번째는 가장 멀리 있.. 더보기

티스토리툴바