알고리즘

# 구간 합 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합 시간 복잡도 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N) 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소 # 합 배열 합 배열 S, 배열 A S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식 S[i] = S[i-1] + A[i] 합 배열을 이용해 구간 합 구하는 공식 S[j] - S[i-1] # 관련 문제 [JAVA] 백준 q11659 - 구간 합 구하기 4 11659번: 구간 합 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 일단 A, B, C,...에 대해서 색인 번호를 줘야하니까 HashMap을 써야겠다고 생각했다. 나중에 영문자에 따라 색인 번호를 answer에 넣어주어야 하므로 HashMap의 key는 String(영단어), value는 Integer(색인 번호)로 설정했다. msg의 어디까지 체크했는지 알 수 있도록 checkIdx를 하나 두고 checkIdx가 msg 길이보다 같거나 커지면 map에 넣고 색인 번호 찾고 하는 작업들을 그만두면 되지 않을까?하고 생각한대로 코드를 짰는데 answer에 마지막 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 문제 대충 읽은 후 "{", "}" 지우고 HashSet 이용해서 중복되지 않게 숫자 걸러서 다시 int[]에 담으면 되는거 아닌가?라고 생각하고 풀었다가 바로 테스트케이스들 대부분 실패 정신 차리고 문제 다시 제대로 읽었더니 "원소의 순서가 다르면 서로 다른 튜플입니다."가 있었네,, 어떻게 풀까 고민하다가 String s에 많이 포함된 순서대로 a1, a2, ...인 것을 깨닫고 숫자 별로 작성된 개수에 따라 내림차순 정렬하면 되겠다고 생각했다. 풀이 1. "{", "}" 제거 후 "," 기준..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 도시 이름을 넣고 빼고 해야할 것 같으니까 덱을 쓰면 되지 않으려나.. 일단 cacheSize만큼 넣고 채운 이후에 포함하는지 안하는지에 따라서 나누면 될 것 같은데 => 실행 결과 : 틀렸습니다. 왜..?하면서 다시 생각해보니 "일단 cachesize만큼 넣고 채운 이후에"가 잘못된 생각이었다. cacheSize만큼 채우기 전에도 도시 이름을 포함하고 있는지 아닌지에 따라 넣고 빼야했다. 해당 부분을 수정하고 나니 통과 풀이 1. cacheSize가 0인 경우, 무조건 cachemiss가 나기 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 크기가 제일 많은 것부터 k개될 때까지 담으면 될 것 같은데 풀이 1. HashMap을 이용해 key로는 크기를, value로는 개수를 갖는 map 생성한다. 2. 생성한 map을 이용해 size(크기)와 cnt(개수)를 갖는 Tangerine 클래스를 담는 ArrayList 생성한다. 3. 생성한 ArrayList를 정렬한다. => cnt를 기준으로 내림차순 정렬됨 4. 정렬한 ArrayList를 이용해 cnt가 가장 높은 것부터 차례대로 담는다. 이때, 담은 총 개수가 k보다 크거나 같으면 b..

1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 의식의 흐름 (게임을 더하면 이긴 게임(Y)만 늘어나는게 아니라 게임 횟수(X)도 늘어나는걸 생각 못하고,,,) 1~X-Y번 이분 탐색 돌리면 되겠네 라고 했다가 7번의 "틀렸습니다"를 보고 정신차림. 혹시나 하고 end = X로 고쳤더니 바로 통과해버렸당. 근데 아직까지 왜 end = X인지 이유를 명확히 모르겠다👻 풀이 1. Z가 99%인 경우, 게임을 아무리 해도 승률이 100%가 되지 못하므로 해당 경우는 바로 처리 2. 99% 아래인 경우, 이분..

16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 의식의 흐름 A에서 B로 가면 경우의 수가 너무 많을 것 같으니까 B에서 A로 가볼까..? 일의 자리가 1이거나 짝수일 때만 연산 가능하니까 그 경우만 처리해주고 나머지는 -1이겠지! 풀이 B를 A로 만들기 도전 1. B의 일의 자리가 1인 경우 1을 없애주고, B가 짝수인 경우 2로 나누어준다. 만약, 2가지 경우 중 하나에 포함되지 않는 경우(ex. 일의 자리가 3인 경우)는 A로 만들지 못하는 경우이므로 -1 출력 2. 1번 연산을 B