Java/Java 알고리즘 (37) 썸네일형 리스트형 자바 필수 메서드 # String과 StringBuilder indexOf() 메서드와 substring() 메서드 while((pos=str.indexOf(' '))!=-1) { String tmp = str.substring(0, pos); int len=tmp.length(); if(len>=m) { m=len; answer=tmp; } str=str.substring(pos+1); 1. tmp에 ' '전까지 잘라서 넣는다. 2. str에 자른 부분 나머지 부분을 넣는다. 3. 길이가 m보다 큰 부분을 정답으로 한다. import java.util.Scanner; public class Main { public String solution(String str) { String answer=" "; int m=Inte.. [알고리즘] 3-1-2. 조합 예제 (2) 080 ~ 083 # 조합 점화식 dim[i][j] = dim[i-1][j] + dim[i-1][j-1] 문제 080. 조약돌 꺼내기 문제 081. 순열의 순서 구하기 문제 082. 사전 찾기 문제 083. 선물 전달하기 [알고리즘] 3-1-1. 조합 예제 (1) 076 ~ 079 # 조합 점화식 dim[i][j] = dim[i-1][j] + dim[i-1][j-1] 문제 076. 이항계수 구하기1 문제 077. 이항계수 구하기2 문제 078. 부녀회장이 될 테야 문제 079. 다리 놓기 [알고리즘] 3-1. 조합 : dim[i][j] = dim[i-1][j] + dim[i-1][j-1] 1. 순열과 조합 nPr : n개의 숫자 중 r개를 순서를 고려해 나열하는 경우의수 nCr : n개의 숫자에서 r개를 순서없이 뽑는 경우의 수 (1) 순열 : 5개 중 2개를 골라 순서대로 나열하는 경우의 수 [ n개 중 r개를 골라 순서대로 나열하는 경우의 수 = n! / (n-r)!] -> 5! / (5 - 2)! -> 5! / 3! = 5 *4 : 순서가 존재하므로, 뽑힌 숫자가 달라도 뽑는 순서가 다르면 다르다 (2) 조합 : 5개 중 2개를 뽑는 경우의 수 [ n개 중 r개를 뽑는 경우의 수 = n! / (n-r)! * r!] -> 5! / (5 - 2)! * 2! -> 5! / 3! = 5 *4 / 2 : 순서가 존재하지 않으므로, 뽑힌 숫자가 같으면 같으므로, r!를 나눈다 [r!만큼 같은 .. [알고리즘] 2-4. 슬라이딩 윈도우 # [+deque 데크 자료구조] 1. 슬라이딩 윈도우 : 2개의 포인터의 범위에서 범위를 유지한 채, 이동하면서 조건에 맞는 경우를 찾는 알고리즘 문제 09. DNA 비밀번호 평소 문자열을 이용해 노는 것을 좋아하는 민호는 DNA 문자열을 알게 됐다. DNA 문자열은 모든 문자열에 등장하는 문자가 {'A'，'C'，'G'，'T'}인 문자열을 말한다. 예를 들어 "ACKA"는 DNA 문자열이 아니지만，"ACCA"는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을만들고 만들어진 DNA 문자열의 부분 문자열을 비 밀번호로 사용하기로 마음먹었다. 하지만 민호는 이 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분 문자열을 뽑았을 때 "AAAA"와 같이 보안에 취약한 비밀번호가 만들어질 .. [알고리즘] 02-3. 투 포인터 1. 투 포인터 : 2개의 포인터로 구하는 알고리즘 -> end_index가 끝에 도달할 때까지 반복 문제 06. 연속된 자연수의 합 구하기 어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(l 투 포인트 알고리즘을 사용해 시작 인덱스와 종료 인덱스를 지정해 연속된 수를 표현한다. 2단계. 손으로 풀어보기 입력받은 값을 N에 저장한 후 코드에서 사용할 변수를 모두 초기화 -> count를 1로 초기화할 경우 N이 결괏값과 같은 경우를 미리 넣은 걸로 가정 포인터를 이동시키면서, 배열을 끝까지 탐색하고 합이 N이 될경우를 구한다. #투 포인터 이동 원칙 sum > N : sum = sum - start_index; start_index++; sum n) { sum.. [알고리즘] 2-2. 구간 합 [경우의 수 구하기 (순열과 조합 이용)] 1. 구간 합 : 합 배열을 이용해 시간 복잡도를 더 줄이기 위한 알고리즘 (1) 구현 과정 먼저 합 배열을 구한다 -> 미리 구해둘 경우, 일정 범위의 합을 구하는 시간 복잡도가 감소 [O(1)] 합배열 공식 : sum[i] = sum[i-1] + arr[i] 구간합 공식 : sum[j]-sum[i-1] //i에서 j까지의 구간 합 # arr[2] ~ arr[5] 구간 합을 합 배열로 구하는 과정 sum[5] = arr[0] + arr[1] + arr[2]+ arr[3]+ arr[4]+ arr[5] sum[1] = arr[0] + arr[1] sum[5] - sum[1] = arr[2] + arr[3] + arr[4] + arr[5] //sum[5]-sum[1]은 arr[2] ~ arr[5]까지의 구간.. [알고리즘] 2-1. 배열과 리스트 1. 배열과 리스트 (1) 배열 인덱스를 통해 값에 바로 접근 새로운 값의 추가나, 특정 위치의 값이 삭제가 어렵다 -> 직접 이동시켜서 넣어야한다. [우측 시프트 연산] 배열의 크기를 변경 불가능하다. (2) 리스트 값과 포인터를 묶은 노드를, 포인터로 연결한 자료구조 인덱스가 없다 -> 순서대로 접근 -> 조회가 느림 포인터로 연결되어있어서, 데이터 삽입과 삭제가 빠름 크기 별도 지정없이, 데이터 추가 및 삭제 가능 포인터 저장 공간이 필요 문제 1. 숫자의 합 구하기 N개의 숫자가 공백 없이 써 있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오. 입력 1번째 줄에 숫자의 개수 N(1 순서대로 숫자형으로 변환해 더한다 2단계. 손으로 풀어보기 숫자의 개수만큼 입력받은 값을 String 형으로.. 이전 1 2 3 4 5 다음
