알고리즘48 [BOJ] 15829. Hashing 백준 온라인 저지에 있는 15829번 Hashing 문제 풀이입니다. 문제: https://www.acmicpc.net/problem/15829 처음에는 31^i를 구하는 부분에서 pow(31, i)를 썼더니 부분 점수를 받았습니다. L이 커졌을 때 pow(31, i) 부분 때문에 시간복잡도가 엄청나게 커졌나봐요. 31^i는 1, 31, 31*31, 31*31*31 ... 이라서 이전 31^i에 31을 한번 더 곱하기만 하면 되는데 괜히 필요없는 함수를 호출하면서 시간복잡도를 크게 만들어버렸어요... 그래서 아래와 같이 바꿨더니 전체 정답이 되었습니다! 중복되는 부분, 생략할 수 있는 부분을 고민하면서 짜야하는데 나름 신경쓰다가도 생각없이 짤 때가 있네요... 반성해야겠습니다. 🤧 ❗️중복되는 부분, 생.. 2020. 5. 1. [BOJ] 11050. 이항 계수 1 백준 온라인 저지에 있는 11050번 이항 계수 1 문제 풀이입니다. 주어지는 자연수 N과 K에 대한 이항 계수를 구하는 문제입니다. 이항 계수란 N개의 수 중에서 K개를 고르는 경우의 수로 아래와 같이 구하면 되는데요. 딱 보고 떠오르는 생각은 각각의 팩토리얼을 구해서 계산하면 되겠네~ 였습니다. 여기서❗️ 줄일 수 있는 중복되는 부분이 있는데요. 팩토리얼이 1부터 N까지를 차례대로 곱한 수이잖아요. 그리고 n-k와 k는 둘다 N보다 작을 것이구요. 그럼 둘중에 하나는 계산을 생략하고 n!에 바로 나눠줬다고 생각하면 중복되는 부분이 줄어들겠더라구요. 글로 이해가 잘 안가실수도 있어서 예제에 있는 숫자로 예를 들어보면 N=5, K=2의 이항계수는 5*4*3*2*1 / (3*2*1)*(2*1) 이런식이 됩.. 2020. 5. 1. [SWEA] 7087. 문제 제목 붙이기 알파벳 등장 유무를 관리하기 위해 map 자료 구조를 이용하여 알파벳을 key로, 등장 유무를 value로 관리하였습니다. 시작할때 map의 A~Z까지의 key에 대한 value를 false로 삽입하였습니다. 그리고 제목을 입력받으며 첫글자를 key 값으로 가지는 value를 true로 변경하였습니다. 입력이 끝난 후 map을 돌며 value가 true인 경우 result를 증가시키고, false인 경우 그 뒤의 알파벳은 사용하지 않으므로 result를 리턴하였습니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWkIdD46A5EDFAXC&categoryId=AWkIdD46A5EDFAXC&categoryTyp.. 2020. 3. 19. [SWEA] 8673. 코딩 토너먼트1 모든 사람들의 코딩 실력을 입력받고 대진표에 따라 경기를 치르는 두 코딩 실력 중 더 높은 숫자(다음 라운드에 출전할)만 vnext 벡터에 넣었습니다. 경기를 치르는 두 코딩 실력의 차를 result에 더했습니다. vnext의 사이즈가 1이 되면 최종 승자가 결정되었으므로 토너먼트가 종료되고, result를 반환하여 출력합니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW2Jldrqlo4DFASu&categoryId=AW2Jldrqlo4DFASu&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacade.. 2020. 3. 17. 이전 1 2 3 4 ··· 12 다음
