알고리즘(Algorihtm) (5) 썸네일형 리스트형 [알고리즘] 투 포인터와 부분합 투포인터란? "정렬된" 리스트 상에서 두 개의 포인터(= index 좌표) 를 사용하여 순차적으로 접근하면서 구간의 값이 목표 값과 같을 때까지 포인터를 조작하며 원하는 부분합과 구간을 구할 수 있는 알고리즘 기법입니다. 투 포인터는 주로 1차원 배열 상에서 부분합 등을 구할 때 주로 사용하게 되는데요. 이때 무조건 1차원 배열이라고 해서 투포인터를 사용할 수 있는 것은 아니며, 배열이 정리되어 있지 않다면 정렬된 상태로 만들어 주어야 합니다. 투포인터는 O(N)의 시간 복잡도를 가집니다. 알고리즘 설명 정렬된 값을 가지는 1차원 배열이 주어지고, K라는 값을 가지는 배열 속 숫자들의 부분합을 구한다고 가정해보겠습니다. 이 경우 투포인터를 사용하면 아래와 같이 포인터의 이동을 표현할 수 있는데요. 배열의.. [PGR] 2023 KAKAO BLIND RECRUITMENT - 표 병합 📌 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 정사각형의 2차원 배열 속 좌표를 갖는 표의 셀의 병합과, 병합 해제, 값 변경 등의 구현을 해야하는 문제였습니다. 문제의 설명 중, 인접하지 않은 두 셀에 대해서도 병합이 가능하다는 설명이 있고, 두 점에 대하여 병합한다는 점에서 Union-Find 알고리즘 즉 서로소 집합 알고리즘이 적용될 수 있는 문제였습니다. 제약조건 1 ≤ commands의 길이 ≤ 1,000 c.. [PGR] 2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정 📌 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 고객에게 호텔 방 번호를 배정할 때, 이에 최적화된 알고리즘을 통해 시간 복잡도를 개선해야 통과할 수 있는 문제였습니다. 이번 문제에서 '최대 방번호'를 찾기 위해 사용한 알고리즘은 서로소 집합, 즉 유니온 파인드 알고리즘을 사용했습니다. 소스 코드 자체는 코드량이 적어 간단한 편이나, 그 원리에 대해 설명해보도록 하겠습니다. 문제에서 주어지는 파라미터는 두 종류 입니다. .. [백준 4335] 숫자 맞추기 https://www.acmicpc.net/problem/4335 4335번: 숫자 맞추기 스탠과 올리는 정수 맞추기 게임을 하고 있다. 스탠은 1과 10사이의 정수 하나를 생각하고, 올리는 스탠이 생각한 수를 맞춰야 한다. 올리가 수를 말할 때마다 스탠은 올리가 말한 수가 큰지, 작 www.acmicpc.net 풀이 설명 스탠이 거짓말을 하는지 판별하는 알고리즘입니다. 스탠의 발언(?)을 스택에 저장하고 스택에서 값을 꺼내서 그중 거짓이 있는지 판별합니다. 스탠의 발언은 크다(too high), 작다(too low), 같다(right on) 세가지입니다.그래서 정답보다 큰 수를 위한 스택 하나, 작은 수를 위한 스택 하나를 총 두개의 스택으로 거짓말을 판별합니다.자세한 로직은 아래의 소스코드 참고 im.. [백준 2828] 사과 담기 게임 https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M 바구니의 오른쪽 끝 좌표가 사과의 낙하 위치보다 크거나 같다면 - 2.2. 그렇지 않을 경우에는 오른쪽 끝 좌표가 사과의 낙하 좌표가 될 때까지 움직입니다. - 3. 사과의 낙하 위치가 기준점보다 작다면(왼쪽이라면), 사과의 낙하 위치까지 이동해야 합니다. (바구니를 돌리거나 할 수 없으므로) - 위의 조건에서 1번과 2.1.번의 조건을 제외하고는 바구니의 이동거리를 계산해야 합니다. - 이 때, 바구니가 이동한 거리를 distance, 사과의 낙하 위치를 x, -.. 이전 1 다음
