'🔥 Algorithm' 카테고리의 글 목록

2025.11.02·🔥 Algorithm/구현

문제 접근 https://school.programmers.co.kr/learn/courses/15009/lessons/121687 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도가 그렇게 어렵지 않은 구현 문제이다. 방향벡터를 구현하고 로봇의 회전에 따라 어떻게 방향을 지정해줄지 고민하고, 좌표계가 일반적인 배열에서의 구현 문제 처럼 맨 왼쪽 위 위치(인덱스)가 0, 0으로 정해져있는 것이 아니라 인덱스로 일반적인 x, y 좌표계에서 중앙인 0,0 에서 움직이는 것임을 염두해야한다. => 즉, 보통 배열에서 위쪽으로의 이동은 int[y][x]로 생각하고 y를 -1 해주는데 이 문제는 x, y 좌표계 이..

[프로그래머스] 유전법칙 (JAVA 풀이)

2025.11.01·🔥 Algorithm

문제 접근 https://school.programmers.co.kr/learn/courses/15008/lessons/121685 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 우선 시간 복잡도를 계산해봤을 때 해당 세대의 특정 번째까지 직접 찾아가는 것은 무리가 있고 결국 RR Rr Rr rr 로 부터 파생되는 부분이 눈에 들어와서 패턴을 찾는 방식으로 접근해봤다. 하지만 이를 어떻게 재귀에 적용시킬지를 찾지 못해서 풀이를 본 문제이다. 문제 풀이 위 그림과 같이 최대 16세대 (n 자세히 살펴보면 빨간색 네모칸으로 표시한 부분이 반복적으로 발생하므로 이를 재귀로 풀면 해결할 수 있을 것 같다는..

[프로그래머스] 체육대회 (JAVA 풀이)

2025.10.31·🔥 Algorithm/완전탐색

문제 접근 https://school.programmers.co.kr/learn/courses/15008/lessons/121684 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 최대 학생수가 10명이고 종목수도 최대 10개까지이므로 모든 경우를 탐색한다고하면 첫번 째 종목에서 10명중 1명을 선택하고 두번 째 종목에서 9명중 1명을 선택하고 ... 즉, O(10!)이므로 시간 초과없이 모든 능력치의 합이 최대인 구간을 구할 수 있다. 그래서 바로 완전 탐색으로 문제에 접근하였다. 문제 풀이 위에서 말한대로 각 종목당 현재 고를 수 있는 인원들 각각에 대해 모든 경우를 확인하며 종목들의 모든 인원이 채워졌을 때..

[프로그래머스] 외톨이 알파벳 (JAVA 풀이)

2025.10.29·🔥 Algorithm/구현

문제 접근 https://school.programmers.co.kr/learn/courses/15008/lessons/121683 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 처음 봤을 때 굉장히 쉽게 구현이 될 것 같았는데 생각보다 생각할게 조금 있었던 문제였다.List나 Set, Map 등 여러 자료구조들중 선택해서 하나를 사용할 수 있다면 충분히 풀 수 있는 난이도이다. 문제 풀이 input_string의 최대 길이가 2,600이므로 for문을 2번 사용해도 문제가 없을 것으로 생각해서 나이브하게 생각한 풀이를 그대로 구현했다. 우선 input_string에 있는 문자들의 종류를 알아내기 위해 inpu..

[프로그래머스] 사라지는 발판 (JAVA 풀이)

2025.10.28·🔥 Algorithm/완전탐색

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92345 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이길 수 있는 경우 최소의 턴으로 이기는 방향으로 가고 이길 수 없는 경우 최대한 오래 버틸 수 있게 하라는게 이해가 안되서 정말 어려웠던 문제였다. 이런 경우를 미니맥스 알고리즘이라고 한다는데 이런 구체적인 정보없이도 5x5 board판이므로 모든 경우를 탐색해본다는 생각을 갖고 접근한다면 똑같이 풀 수 있다. 문제 풀이 상하좌우로 움직일 수 있고 map을 벗어날 수 없으며 발판이 있는 곳으로만 이동할 수 있다는 내용을 보자마자 가장 먼..

누적 합(Prefix Sum) 이란? / [프로그래머스] 파괴되지 않은 건물 (JAVA)

2025.10.27·🔥 Algorithm

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 우선 시간 복잡도를 잘못 계산해서 완전 구현으로 풀었다가 시간초과가 발생했다.힌트를 살펴보니 누적합으로 풀이를 하면 된다는데 누적합에 대한 지식이 없어서 굉장히 고생했던 문제이다. 문제 풀이 우선 단순히 구현으로 문제를 풀이하게 되면 skill의 길이 S마다 N x M 크기의 게임 맵을 돌아야한다.즉, O(S*N*M)의 시간 복잡도를 갖게되는데 이러면 S의 최대 길이 250000과 N, M의 최대길이 1000을 계산해보면 2500억이라는 수..

[프로그래머스] 양과 늑대 (JAVA 풀이)

2025.10.26·🔥 Algorithm/완전탐색

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 처음에는 문제를 보고 든 생각은 최대 17개의 노드이므로 모든 경우를 전부 따져보면 될 것 같았음하지만, 재귀 구현 과정에서 자꾸 무한루프가 발생해서 힘들었던 문제 문제 풀이 이 문제의 핵심 포인트는 현재 노드 기반이 아니라 현재 상태(양, 늑대, 다음 방문 가능 노드 목록)으로 탐색을 진행해야된다는 것임 => 즉, 지금까지 방문한 모든 노드에 연결된 모든 자식 노드들 중에서 하나를 골라 다음으로 방문해야 무한 루프없이 문제를 제대로 풀 수 ..

[프로그래머스] 양궁대회 (JAVA 풀이)

2025.10.25·🔥 Algorithm/완전탐색

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 쏠 수 있는 화살의 점수가 0~11점까지라 완전 탐색으로 접근하면 풀 수 있을 것이라고 생각했지만 재귀 구현이 약해서 그런지 구현에 어려움을 느꼈던 문제였다. 문제 풀이 우선 총 3개의 함수로 나눠서 구현하는걸 목표로 잡고 시작했다. 1. 라이언과 어피치의 점수 차이를 반환하는 함수 2. 정답 배열 중에 누가 우선순위가 높은지를 반환하는 함수 3. 재귀를 통해 모든 경우를 탐색하는 함수 라이언과 어피치의 점수 차이를 반환하는 함수는 문제 그..

[프로그래머스] k진수에서 소수 개수 구하기 (JAVA 풀이)

2025.10.25·🔥 Algorithm/구현

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 그렇게 어려운 난이도의 문제는 아니었음 => 정말 문제에 주어진대로 구현하고 자료형을 잘 사용하면 풀 수 있음 문제 풀이 우선 진법을 바꿀 때 0이 포함되지 않는 값의 길이가 int의 최댓값을 넘는 경우가 있기 때문에 long타입 사용을 결정하고 시작했음 그 다음 크게 2가지의 구현으로 나누었는데isPrime이라는 소수인지를 판별해주는 함수와 changeNumber라는 진법을 변환하는 함수임 사실 toString을 사용하면 쉽게 진법을 바꿀 ..

[프로그래머스] 신고 결과 받기 (JAVA 풀이)

2025.10.24·🔥 Algorithm/구현

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해시를 사용하면 쉽게 해결할 수 있는 문제였다! 여러 방법이 있겠지만 가장 직관적으로 각 유저별로 누가 신고를 했는지 List의 정보를 담고있는 Map 하나와각 유저별로 처리 결과 메일을 몇 개를 받아야하는지를 기록하는 또 다른 Map 하나를 이용하여 문제를 풀이하는 방향성을 생각했다. 문제 풀이 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리되기 때문에 Set을 이용해서 이런 중복 신고를 제거해줬다. =..

[백준 2805번] 나무 자르기 (JAVA 풀이)

2025.10.24·🔥 Algorithm/이분탐색

문제 접근 https://www.acmicpc.net/problem/2805 이미 알고리즘 유형이 이분 탐색인 것을 봐버려서 혼자생각을 많이 하지 못햇던 문제이다..! 문제 풀이 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구해야하는데이분 탐색을 사용하면 O(N * logN)의 풀이를 떠올릴 수 있다 우선 가장 높은 나무의 길이를 max에 저장하고 min을 0으로 설정 후에 이분 탐색을 진행했다이 때 문제 조건 상 나무의 길이가 최대 2,000,000,000 이므로 long 타입을 사용해줘야 오버플로우가 발생하지 않는다! 정석대로 중간값을 구하면서 전체 나무를 잘라보면서 만약 현재 위치에서 나무들을 잘랐을 때 M미터를 넘길 수 있으면 (문제 조건에 맞으면) mi..

[프로그래머스] 단속카메라 (JAVA 풀이)

2025.10.21·🔥 Algorithm/그리디

문제 접근 https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 고속도로에서 가장 적게 카메라를 설치하는 경우를 찾아야하는 문제인데 문제를 보면 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주한다는 힌트를 찾아볼 수 있다. 차량의 진입 지점, 진출 지점이 담긴 routes 배열을 진출 지점을 기준으로 오름차순 정렬한 후 순차적으로 routes 배열을 돌면서 진출 지점에 카메라를 설치하고 현재 진출 지점이 다음 차량의 이동 지점에 포함되는지를 확인하고 만약 포함된다면 해당 카메라..

티스토리툴바