알고리즘 & 문제

문제 https://school.programmers.co.kr/learn/courses/30/lessons/172928 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 class Solution { public int[] solution(String[] park, String[] routes) { int[] answer = new int[2]; // 시작 좌표 찾기 for (int i = 0; i = 0) { answer[0] ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/169198 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 import java.util.ArrayList; import java.util.List; class Solution { public int[] solution(int m, int n, int startX, int startY, int[][] balls) { int[] answer = new int[balls.length]; Point start = new Point(startX..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/178871?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 class Solution { public String[] solution(String[] players, String[] callings) { for (String call : callings) { for (int i = 0; i < players.length; i++) { if (call.equals(players[i])) { String tmp = ..

기수 정렬의 핵심 이론 기수 정렬(radix sort)은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다. 수행 방식 기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.

병합 정렬의 핵심 이론 병합 정렬(merge sort)은 분할 정복(divide and conquer)방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도는 O(nlogn)이다. 수행 방식 부분 그룹은 setN으로 표시했다. 그림을 보면 최초에는 8개의 그룹으로 나뉜다. 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬한다. 이런 방식으로 병합 정렬 과정을 거치면 전체를 오름차순으로 정렬할 수 있다. 병합 정렬은 코딩 테스트의 정렬 관련 문제에 자주 등장한다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 한다. 2개의 그룹을 병합하는 과정 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결..

투 포인터 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 문제 풀기 백준 알고리즘 2018번 문제 '연속된 자연수의 합 구하기' 풀이 [문제] 자연수 N(1이상 10,000,000이하)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 예를 들어 N = 10은 10, 1+2+3+4 2가지로 출력이 2가 나와야 한다. 이 문제는 시간 복잡도를 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간은 2초이다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인..