본문 바로가기

PROGRAMMING/ALGORITHM

 (50)
[ALGORITHM] Sliding window 예제 문제 N개의 숫자 중 K개 만큼 연속된 숫자의 합이 가장 큰 것을 찾아라 N : 2 4 1 11 9 3 5 K : 3 이라고 주어질 때 조합은 2 4 1, 4 1 11 등으로 만들어 지게 되는데 합이 가장 큰 조합을 찾으면 된다. N이 5이상 100000 미만의 숫자를 가지고 K는 N이하의 숫자를 가질 때 단순하게 for문을 돌려서 k개만큼 MAX값을 찾으려 하면 N*K의 시간 복잡도를 가지게 된다. N*K의 복잡도를 N으로 최적화하는 알고리즘이 Sliding window K의 숫자가 클 수록 알고리즘 적용의 효과가 확실해진다. 알고리즘 이름대로 숫자를 배열에 저장하고 K크기의 창문을 만든다고 생각하면 된다. 0부터 K까지 합을 구해 초기화 하고 다음 단계로 창문을 옆으로 옮기면 된다. 옮기는 과정..
[ALGORITHM] Two Pointers Algorithm 예제 문제 크기가 다른 두 배열을 입력받아 두 배열을 합치고 오름차순으로 정렬된 배열을 반환하라. 일단 정렬만 해도 nlogn의 시간 복잡도가 나오는데 이를 최적화하는 알고리즘이 Two pointer algorithm 이다. 이미 정렬된 배열이 입력된다는 가정하에 크기 3인 배열 A와 크기 5인 배열 B를 입력받아 정렬된 크기 8의 배열 C를 만들어 보자. 우선 포인터(위치)를 담을 변수 p1, p2를 선언하여 p1은 A배열의 위치를 p2는 B배열의 위치를 갖게 한다. 두 값을 비교해 작은 값을 배열 C에 담고 포인터를 +1 해줌으로 비교대상을 다음으로 이동시킨다. 알고리즘 적용 전 public void solutionWithoutAlgorithm() { Scanner sc = new Scanner(Sy..
[프로그래머스] 위클리 챌린지 5주차 https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 문제 요약 A E O I U 만으로 이뤄진 사전이 있는데 input 단어가 그 사전에서 몇번째 순서에 해당하는지 찾는 문제 풀이 방법 나는 DFS 완전 탐색으로 풀이. A AA AAA ... UUUUU까지 탐색하며 input과 일치한 문자가 있으면 return한다. 총 경우의 수가 1자리 5^2 2자리 5^2 ... ..
[프로그래머스] 위클리 챌린지 4주차 https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 문제 요약 각 직군 별 스킬에 대한 점수가 있는데 내 스킬이 어느 직군에서 가장 높은 점수를 갖는지 출력하면 된다. 점수가 동일한 직군이 2개 이상일 땐 사전순으로 가장 앞에오는 직군을 출력한다. 풀이 방법 직군과 직군별 나의 스킬점수는 map으로 Input으로 받는 테이블은 Map 로 구현했다. 동점일 때 사전순으로 맨앞의 직군을 출력하는 부분은, 최고점인 직..
[백준] 9663번 N-Queen JAVA 백트래킹 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 N*N 체스판에서 퀸 N개를 배치할 수 있는 방법의 수를 구하는 문제 퀸들은 서로를 공격할 수 없는 위치에 배치되어야 한다. 풀이 방법 모든 경우의 수를 탐색하되 중간에 안 되는 수가 나오면 그 뒤는 체크하지 않는 백트래킹 문제이다. 퀸의 이동 가능 경로는 해당 열 전부와 대각선 전부이다. 고로 1열부터 하나씩 배치해보며 n개가 배치되는 경우의 수를 더해준 후 출력하면 된다. 크게 2가지 구성인데 1번..
[프로그래머스] 위클리 챌린지 2주차 https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 어떻게든 for문 2번 안 써보려 했지만 포기하고.. 최대한 명확하게 풀려고 노력했다. 문제 요약 학생이 학생에게 (본인포함) 점수를 주는데 그에 대한 평균값을 구하고 이를 학점으로 환산하는 문제이다. 풀이 방법 문제요약만 보면 매우 간단해 보이지만, 역시 예외사항이 항상 문제다. 내가 나한테 준 점수..
[프로그래머스] 위클리 챌린지 1주차 https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 문제 요약 놀이공원 이용료대비 가지고 있는 돈에서 얼마나 부족한지 구하면된다. 같거나 부족하지 않으면 0 부족하면 부족한 금액을 반환하면 된다. 단, 이용금액이 횟수와 비례하게 증가한다. 첫번째 이용료는 N이라면 두번째에는 2N이 필요하다. 풀이 방법 보자마자 팩토리얼이 생각나서 입력받은 이용횟수 만큼 1~N 합의 값을 구했다. 이 값에 처음 이용료를..
[프로그래머스] 타겟 넘버 JAVA DFS https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 요약 숫자 배열이 주어지는데 각 숫자 음양 값의 조합으로 주어지는 타겟넘버를 만들 수 있는 총경우의 수를 구하는 문제이다. 풀이 방법 전체 경우의 수를 탐색해야 한다는 건 알겠는데 정확히 어떻게 해야 할지 감이 안와 문제의 카테고리라 DFS로 찾아가며 풀이했다. 입력 배열이 20자리까지임으로 일일이 방문..

티스토리툴바