728x90 Algorithm - Java39 [Programmers - Lv. 2] 두 큐 합 같게 만들기 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr전형적인 투포인터를 사용해야 하는 문제.최단 횟수라서 BFS를 떠올릴 수도 있지만조건만 보더라도 무조건 터질 거라는 예상이 온다.문제 특성 상 큐 두개를 사용하기에두 배열을 합쳐 하나의 원 배열이라고 생각하면 편하다.[문제 설명]길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.큐는 먼저 집어넣은.. 2025. 6. 14. [How to] 슬라이딩 윈도우(Sliding Window) 프로그래밍 문제를 풀다 보면,부분 배열의 최대합, 최대 길이와 같은특정 조건을 만족하는 구간 찾기와 같은 문제들을 자주 만나게 된다.이런 문제들을 단순 반복문으로 풀면 시간 복잡도가 O(N²) 이상으로 커지는 경우가 많은데이때 쓰이는 것이 바로 슬라이딩 윈도우(Sliding Window)이다.말 그대로 고정된 크기의 창(윈도우)을 왼쪽에서 오른쪽으로 한 칸씩 밀어가며 배열이나 문자열을 탐색한다.전체 데이터를 순회하지 않으면서 탐색하기에 시간복잡도와 공간복잡도 모두 효율적으로 사용할 수 있다.예제1: 최대 연속 부분합 구하기[문제 설명]길이 N의 정수 배열 arr와 정수 k가 주어진다. 이때, 연속된 k개의 원소를 선택했을 때의 합 중에서 가장 큰 값을 구하시오. [제한 사항] 1 ≤ N ≤ 100,000.. 2025. 5. 13. [How to] 제한 조건에 따른 시간복잡도 고려 코딩테스트 문제를 접하다 보면 언제나 보게 되는 제약 조건.주로 시간과 메모리, 그리고 입력 조건에 따라 천차만별이다.구현한 코드가 어떤 시간/공간 복잡도를 가지냐에 따라분명 답은 찾지만 시간 초과나 메모리 초과가 발생할 수 있고,언제나 최적의 알고리즘을 쓸 수 있어야 좋은 개발자가 될 수 있을 것이다. 시간 복잡도(Time Complexity)- 코드의 실행 시간은 실행 환경에 따라 달라진다. 언어, 하드웨어, 운영체제 등 다양한 환경에서 실행되기에 같은 코드라도 실행시간은 다를 수 있다.- 그렇기에 실행 시간이 아닌 연산의 실행 횟수를 카운트한다. 이를 입력 데이터의 크기에 관한 함수로 나타내고, 이를 점근적 표기법으로 나타낸다.- 점근적 표기법은 O, Ω, Θ 등의 표기가 있다. 상대적으로 가장 간.. 2025. 5. 12. [How to] 최대 연속 부분 합 구하기 (Kadane's Algorithm) 최대 연속 부분 합 문제란한 배열에서 어떤 인덱스 i부터 이후의 한 인덱스 j까지 값들을 더했을 때그 값이 최대가 되는 영역을 구하는 문제이다. 즉, 정수 배열에서 연속된 구간의 합 중에서 가장 큰 값을 찾는 것!최대 합을 찾는 문제이기에 구간은 고정 길이가 아닌 가변 길이이다.기본 풀이법1. O(N³)int answer = 0;for(int i = 0; i - 시작 인덱스와 끝 인덱스를 각각 반복문을 통해 구하고 구간 별로 반복문을 통해 구간 합을 구한 후에 비교하여 최댓값을 구한다.- 코드 작성 시에는 쉽게 생각나지만 삼중 반복인 만큼 당연히 시간복잡도 면에서 효율적이지 못 함. 2. O(N²)int answer = 0;for(int i = 0; i - 시작인덱스 지정 후 누적합 방식으로 sum을 누.. 2025. 5. 9. [Programmers - Lv. 3] 디스크 컨트롤러 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krSJF 스케줄링에 대한 우선순위 큐 문제정렬 시 같은 값을 가진 요소는먼저 넣은 순으로 우선도를 가진다는 점이 핵심이었다.큐 두개로 구현했다가 이후 다른 사람 풀이에서한 분의 풀이에 감명받아서 나도 그렇게 했다. [문제 설명]하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두.. 2025. 2. 26. [Programmers - Lv. 3] 길 찾기 게임 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr트리를 공부하면서 푼 문제문제 자체가 정렬과 이진트리 구현을 동시에 내는 문제라생각할 부분이 많았다.구현에 있어서트리를 따로 만들지 않고 그냥 바로 Node클래스에insert를 넣어서 해결. [문제 설명]전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 .. 2025. 2. 26. [Programmers - Lv. 3] 다단계 칫솔 판매 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr간만에 돌아왔습니다... ㅎㅎ졸업이랑 시험준비랑 이것저것한다고 바빴다.코테를 손을 대긴했는데 올릴 정도인 문제가 없거나어려운 건 내가 못풀고 있어서 올리지 못했다.트리와 그래프 탐색이 특히 약해서 입문하다 발견한 문제.풀이는 크게 어려운게 없었는데재귀함수 오버헤드 감소에 대해 알게되어 글을 씁니다.[문제 설명]너무 길어서 일부 발췌.민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의.. 2025. 2. 25. [Programmers - Lv. 3] 단어 변환 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr간단하게 풀 수 있는 BFS!난이도 상 안올려도 될 것 같지만Pair 클래스도 쓰고 나름 Lv.3이니까 올림한번 BFS와 DFS에 익숙해지면 관련 문제는 다 할 만한 것 같다. [문제 설명]두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.2. words에 있는 단어로만 변환할 수 있습니다.예를 들어 begin이 "hit", target가 "cog", words가 ["hot",.. 2025. 2. 18. [Programmers - Lv. 3] 등굣길 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krDP 문제. 대놓고 dp긴한데 BFS로는 왜 안되지 하고 BFS로 구현해보고 DP로 했다.당연히 BFS는 시간초과남..최단 경로 개수를 1,000,000,007로 나누라길래그렇게 커질 일이 있나?했는데 진짜 이게 문제였음[문제 설명]계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.아래 그림은 m = 4, n = 3 인 경우입니다.가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳.. 2025. 2. 18. 이전 1 2 3 4 5 다음 728x90
