문제 풀이

하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다.알고리즘 문제를 많이 접해보지 못한 나로서는 하노이 탑 원판 이동 횟수 공식을 풀어보지 못해 이번 기회를 통해 정리 해보려고 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다

BEAKJOON : N-Queen아래 그림에서처럼 상하좌우, 대각선 방향으로 끝까지 공격할 수 있기 때문에 해당 경로에는 퀸을 배치할 수 없다.N-Queen 문제는 N의 크기가 작다면 DFS 방식으로 모든 경우의 수를 탐색하면 답을 찾을 수 있다. 하지만 N의 크기가

[백준]의 수 정렬하기, 수 정렬하기 2, 수 정렬하기 3 문제에 대해 Java로 해결한 방법 제시 링크 수 정렬하기 [수 정렬하기 2] (https://www.acmicpc.net/problem/2751) 수 정렬하기 3 수 정렬하기 > 첫째 줄에 수의 개수 N(

단어 정렬우선 먼저 알아야 할 개념에 대해서 정리한다.공통점이라면 Comparable과 Comparator는 모두 인터페이스다.즉, Comparable이나 Comparator를 사용하려 한다면 각 인터페이스 내에 구현된 메소드를 반드시 구현해야 한다는 것이다.Compa

차이를 최대로배열의 최대 크기가 8이기 때문에 모든 경우의 수를 구해서 최대값을 구하면 된다.핵심 알고리즘은 DFS 사용왜? -> 모든 경우의 수 탐색, 백트래킹을 사용해서 조건을 체크해 조건에 맞는 것만 탐색

랜선 자르기주어진 시간은 1초인데 N과 M의 범위가 매우 크다.그래서 완전탐색으론 해결할 수 없다.\-> 이진 탐색을 사용하자주어진 범위와 문제 형태를 보고, 이분 탐색을 사용해야 할지 구별하는 능력을 키워야 할 것 같다.이진 탐색에서도 Upper Bound를 사용해서

숫자 카드완전 탐색을 통해 해결하려고 하면 최대 (500,000 \* 20,000,000)번 탐색을 하게된다.이 경우 시간 초과가 일어나기 때문에 이분탐색을 사용해서 해결하는 것이 대표적이다.조심할 부분은 이분탐색 시에는 반드시 정렬이 되어 있어야 한다는 점이다.이분탐

랜선 자르기이 문제 또한 완전 탐색으로는 시간초과가 나는 문제이다.그래서 이분탐색으로 해결한 문제이며, 조심할 부분은 다음과 같다.이분 탐색 문제에서는 인덱스의 값을 찾는 문제가 대부분이였다.하지만 이번 문제에서는 인덱스의 각 값들을 이용해서 최대 랜선의 길이를 구하는

공유기 설치집의 좌표의 최대 크기가 10억개 이므로 완전 탐색으로 풀기엔 시간이 부족하다.\-> 이분탐색을 사용하자이 문제는 코드가 진행되는 과정을 이해해야 해결 가능한 문제였다.가장 인접한 두 공유기의 최대 거리를 구하는 문제인데max를 공유기를 설치할 수 있는 집

히오스 프로게이머이분탐색 문제를 해결하는데 있어서 참고할 자료를 찾았다.https://www.acmicpc.net/blog/view/109해당 자료를 참고하니 이분탐색 문제에 있어서 이해하기 쉬웠다.이번 문제는 시작 지점, 끝 지점을 잡는게 핵심인 문제였다.시

분할정복다소 간단한 문제로 보이지만, 2,147,483,647 범위에 시간 제한은 0.5초가 주어졌기 때문에 그냥 제곱해버리면 시간 초과가 날것이기에 다른 방법을 찾아야 한다.이번 문제는 '지수 법칙'과 '모듈러 성질'을 알고 있다면 쉽게 해결할 수 있는 문제이다.나는

색종이 만들기이 문제는 자체 문제에 소개하는 부분에 어떻게 해결해야 하는지 잘 나와있다.이 때문에 난이도에 비해 정답률이 높은듯 함...대표적인 분할정복 문제로 문제에서 제공하고 있는 그림을 보며 이해하면 쉽게 이해 가능했다.이 문제에서는 분할 정복 문제가 나오면 구현

히스토그램에서 가장 큰 직사각형https://st-lab.tistory.com/255막히면 항상 찾아보는 블로그.. 오늘도 감사합니다!이번 문제에 해결 방법에는 크게 2가지가 있었다.분할정복과 스택 자료구조를 이용한 풀이방식이다.(나중에 세그먼트 트리에 대해

가장 가까운 두 점참고 블로그 - 오늘도 감사합니다..https://st-lab.tistory.com/256이번 문제는 생각해줄 부분이 상당히 많았다.처음부터 끝까지 블로그를 참고했다고 해도 될 정도였다..히스토그램에서 가장 큰 직사각형 이 문제와 풀이 방법은

스택이번 문제는 스택의 기본중에 기본인 문제였다.구현 방법은 다양하지만 이번 문제의 시간 제한은 0.5초라서, 구현도 쉽고 시간도 빠른 배열로 구현했다.코드만 보고도 쉽게 이해할 수 있을 정도로 간단한 문제였다.

괄호이번 문제는 스택을 활용한 문제 중 대표적인 문제였다.여는 괄호에 대응해서 닫은 괄호가 있는지 체크해주면 해결되는 문제였다.막혔던 부분이라면 자바의 StringTokenizer가 문자열에서 문자 하나하나씩 분리해 줄거라 생각했다.하지만 예상처럼 들어가지 않았고, 문

괄호의 값우선 전에도 비슷한 문제를 해결해 봤기 때문에 스택으로 접근했다.하지만, 아무리 생각해도 어떻게 해결해야 할지 떠오르지 않아서 다른 분들의 풀이를 보고 이해했다.해결의 중요한 부분은 '분배 법칙'을 이용한다는 것이다.위의 예시의 문제를 보자$$(()\[\[]]

탑참고 블로그 https://coding-factory.tistory.com/601스택이 비어있다면 0을 출력하고, 현재 탑을 스택에 push한다.스택이 비어있지않다면2-1. 스택에 peek한 탑의 높이가 현재 탑의 높이보다 높다면, peek한 탑의 번호를 출

카드 2이번 문제는 자료구조 중 '큐'에 대한 기본적인 내용을 묻는 문제였다.자바 언어에서 Collection 프레임워크에서 지원해주는 Queue를 사용하면 쉽게 해결가능한 문제였다.기본적인 FIFO(선입선출) 구조로 Stack과 반대로 생각하면 된다.

요세푸스 문제 0이번 문제도 큐의 기본적인 활용을 묻는 문제였다.요세푸스 순열을 구하는 방법은 k 번째 사람을 제거하고, 그 자리에서 k 번째 사람을 계속 제거해 나감으로써 제거되는 순서를 출력하면 되는 간단한 문제였다.큐를 사용하면 쉽게 해결할 수 있었다.이제 백준의

뱀우리가 잘 알고있는 지렁이 게임(?)을 구현해보는 문제였다.시뮬레이션 문제는 처음 풀어봤는데, 생각보다 쉽지 않았다.하지만, 유형만 잘 이해해 놓는다면 다음엔 조금 더 쉽게 풀수 있을 것 같았다.!문제에서 주어진 규칙을 차근차근 읽고 구체적으로 구현해야 했다.이 문제

최대 힙이번엔 자료 구조인 최대 힙을 구현하는 문제였다.우선 먼저 알고 있어야 할 지식으로힙 (Heap)완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다.최대 값, 최소 값 찾기에 효과적이다.우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다

가운데를 말해요숫자가 주어질 때 마다 숫자들의 중간 값을 구해야 한다.처음에 접근을 PriorityQueue를 다시 구현해야 하나? 아니면 Comparator를 오버라이딩 해야되나? 고민했다.그렇기엔 너무 복잡했다. 결국 다른 분들의 풀이를 보고 왼쪽은 maxHeap으

절댓값 힙이번 문제는 PriorityQueue의 정렬을 간단하게 변경해보는 문제였다.comapreTo 메서드를 오버라이딩해서 두 값의 절대값이 같을 때는 오름차순으로 정렬해주고, 다를 때는 절대값의 크기 순으로 정렬해주는 간단한 문제였다.참고 블로그 : https&#x

철도 풀이 방법 우선 좌표가 (-100,000,000 ~ 100,000,000) 이기 때문에 그냥 무작정 찾아버리면 시간초과에 걸리기 마련이다. 그래서 시간복잡도가 $O(logN)$ 인 우선순위 큐를 사용해서 탐색을 진행한다. 내 구현을 크게 표현하면 시작을

트리 순회이번 문제는 이진 트리의 3가지 순회 방법을 구현하는 문제였다.트리의 기본 지식은 알기 때문에 설명은 생략했다.이진 트리는 '모든 노드의 최대 차수를 2로 제한한 것' 이다.전위, 중위, 후위 순회의 특징만 안다면 쉽게 구현할 수 있다.잘 정리된 블로그를 참고

DFS와 BFS그래프 탐색의 가장 대표적인 DFS와 BFS를 구현하는 문제였다.구현 방법은 정점을 인접 행렬에 저장하고 DFS는 재귀를 통해 쉽게 구현했고, BFS는 Queue를 이용해서 구현했다.다른 블로그를 찾아봐도 이렇게 구현하는 것이 대표적인 구현 방법 인 것

이진 검색 트리전에 풀어봤던 트리 순회의 변형 문제 같은 느낌이였다. '트리 순회' 문제에서 트리 구조를 확실히 이해하고 넘어왔기 때문에 이번 문제는 상당히 쉬웠다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노

최소 스패닝 트리우선 기본 지식을 알아 보겠다.원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 함.(간선들이 사이클을 이루지 않아야 함.)주어진 그래프의 모든 정점들을 연결하는 부분 그

트리의 부모 찾기이번 문제는 DFS를 약간 변형하는 문제였다.DFS를 정확히 알고있다면 간단한 문제였다.DFS는 깊이 우선 탐색으로 루트 노드에서부터 순차적으로 탐색에 들어가는데, 재귀 함수로 구현된 DFS에서 자식 노드로 탐색에 들어가기 전에 부모 노드를 저장해주면

이분 그래프이분 그래프를 구현하는 문제였다.우선 이분 그래프가 무엇인지 이해해야 한다.참고 블로그 (이해를 위한 설명과 사진 참조)https://www.ksakosmos.com/post/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%

유기농 배추이 문제는 백준을 접한지 얼마 안됐을 때, 무작정 풀려고 했다가 실패한 문제였다.이제와서 보니 그래프 탐색 문제였고, 좌표 또한 이용해야 했다.시뮬레이션 문제, 그래프 탐색 문제도 접해봤기에 좀더 쉽게 접근할 수 있던 문제였다.최종 풀이 방법은DFS를 이용했

아침 산책이번 문제는 다음과 같이 서브태스크 문제로 총 200점을 달성해야 해결되는 문제이다.먼저 108점으로 실패한 풀이를 설명하고 200점으로 성공한 풀이를 설명하겠다..먼저 문제 예제를 먼저 살펴봤다.1 - 3,43 - 1,44 - 1,3,55 - 4이렇게 총 8

연산자 끼워넣기대표적인 백트래킹 문제였다.숫자와 연산자를 배열에 저장해서 dfs로 완전탐색 하면 되는 간단한 문제였다.물론 나는 고민해도 생각이 나지않아서 여러 블로그를 참고해서 이해한 경우이다..코드를 디버깅으로 하나하나 어떻게 동작하는지 파악해서 백트래킹을 이해했다

빙산머리로는 어떻게 구현할지 쉽게 생각한 문제였다.먼저주어진 빙산이 두 덩어리로 분리되는지 확인한 덩어리라면 녹인다(1년 지남).만약 두 덩어리로 나누어지면 녹인 횟수를 출력.끝까지 나누어지지 않는 경우라면 0을 출력중요한 알고리즘은 DFS를 통해 이웃한 빙산을 탐색을

미로 탐색대표적인 BFS문제 미로 탐색 문제였다.dx, dy를 통해서 좌표 접근을 하고, BFS로 최단 거리를 탐색하면 된다.살짝 막혔던 부분이 있었는데,최단 거리를 어떻게 계산할까 되게 복잡하게 생각하고 있었다.근데 풀이 방법은 간단하게 다음 이동 경로에 기존의 값에

특정 거리의 도시 찾기BFS 를 이용한 최단 경로 찾기 문제 중 가장 기본 문제인 것 같았다.최단 경로 찾기에서 딱히 추가 옵션이 없어서 간단하게 구현 가능했다.최단 경로 찾기 문제에서는 이전 거리에서 경로의 비용을 더해준다고 생각하는게 중요하다.물론 이 문제는 다익스

최소비용 구하기다익스트라 알고리즘의 기본 방법을 사용하는 문제였다.다익스트라(Dijstra) 알고리즘은그래프의 최단 경로를 구하는 알고리즘하나의 정점에서 다른 모든 정점까지의 최단 거리를 구해준다.음수 가중치는 처리하지 않는다.PriorityQueue를 사용하면 시간

설탕 배달최근 프로젝트 + 토스 캠프 라는 핑계로.. 백준 문제 풀기를 소홀히 하고 있었다.그래서 쉬워보이는 문제로 기억을 찾으려 했지만, 생각보다 쉽지 않았던 문제였다 ㅠㅠ문제의 풀이 자체는 간단하게 5kg, 3kg 봉지를 사용해서 정해진 설탕을 최대한 적은 봉지로

좌표 압축처음에 제목이 좌표 압축이라 무슨 문제지 싶었지만, 숫자 배열에서 우선 순위를 매기면 되는 문제였다.정말 예전에 비슷한 문제를 풀어본 것 같았는데 이번 문제는 $-10^9 ≤ Xi ≤ 10^9$ 이라서 시간 초과가 났었다. Map을 써야겠다는 생각이 들었지만,

나이 순 정렬이러한 정렬 문제는 예전에 풀어본 경험이 있어서 쉽게 해결했다.이번엔 toString()이나 StringBuiler에 대해 새로운 사용법이 있어서 기록을 남긴다.sort에서 Comparator의 compare 메서드를 Override해서 사용했는데,lamd

나는야 포켓몬 마스터 이다솜이 문제는 HashMap을 사용해서 Key값이 들어왔을 때는 Value값을, Value값이 들어왔을 때는 Key값을 반환해줘야 하는 문제였다.처음 쉽게 코드를 작성해서 정답 비율에 비해 생각보다 쉽네? 라고 생각했는데,바로 시간초과가 나버렸다

풀이 과정 이 문제는 짧은 시간제한으로 모든 연산이 O(1)의 시간 복잡도를 가지게 구현해야 한다. 1. `LinkedList`를 사용해서 구현 `LinkedList`를 선택한 이유는 체인처럼 관리하기 때문에 삽입/삭제에 유리하기에 이번 문제에서 사용하기 적합하다

알고리즘 분류는 그리디 알고리즘인데, 내가 푼 방법은 다르게 풀었었다.55-50+40 이라는 입력이 들어오면55-(50+40) 이렇게 묶어서 최소 값인 -35가 되는 문제였다.내가 푼 풀이는 -기호를 만나면 뒤에 모든 숫자의 부호가 -가 된다는 법칙을 발견해서 해결했다

풀이 방법 내가 선택한 해결 방법은

올림픽오랜만에 풀었던 서브태스크 문제였다.그래서 그런가 처음부터 바로 100점을 맞지 못했다.. 내가 푼 방법은입력값을 묶을 Medal class 생성Comparable class를 implements해 compareTo 메서드 overridelist 값들을 차례대로

덩치굉장히 쉬운 문제였지만, 처음 접근법을 잘못잡아서 삽질을 많이 한 문제였다..처음엔 내가한 접근으로는덩치 순으로 내림차순 정렬list를 돌면서 rank를 결정다시 원래 순서로 정렬본인 rank 출력 물론 이 방법은 틀린 방법이다.백준에 제출을 하니 IllegalA

비밀번호 발음하기간단하게 문자를 다루는 문제였다.자바 List의 contains 메서드를 이용해서 해결하면 편하게 할 수 있을 것 같아서 써보려했지만, 여러가지 문제로 삽질만 했다..List의 contains 메서드는 String 값에서만 동작한다.그렇기에 String

등수 구하기무서운 정답률에 비해선 매우 쉬운 문제였다.코드의 주석을 확인하면 쉽게 이해할 수 있을 것이다.자주 풀어본 문제라 구현에선 얼마 안걸렸지만, 97~98%에서 RunTimeError가 떠버렸다!문제의 원인은보다시피 예제 4번에서는 입력받는 값 n이 0이기에 2

스위치 켜고 끄기 풀이 방법 문제 자체는 정답률에 비해 쉬운 문제였다. 이번 문제는 틀린 부분이 2가지 있었다. 인덱스 범위 넘어갔을때 처리 출력 값 설정 1번 문제는 쉽게 찾아서 처리해줄 수 있었고, 출력 값 설정 또한 문제를 대충 읽어서 생긴 문제였다.

크로스 컨트리이번 문제는 너무 생각을 많이 해서 오히려 빙빙 돌아서 접근한 문제였다.브루트포스로 돌려버려도 시간초과가 나지 않기에어떤 자료구조를 사용해서 효율적인 처리를 할 것인가를 생각하면 될 문제였다.처음에는 List를 사용하기로 결정했다.등수에 따라 점수가 부여되

어두운 굴다리브루트포스로 푼다면 100,000 \* 100,000 이기에 시간초과가 나는 것은 알고있었다.하지만, 아직 알고리즘은 잘 몰라서 어떤 것을 써야하는지 몰랐다.그래서 나는 가로등이 하나일 때와, 2개 이상일 때 상황을 나눠서 해결하려 했다.하나일때는가로등을

주유소처음에 접근을 잘못해서 10분 날려먹은 문제다..리터당 주유 비용의 최소값을 찾아서 이후 나오는 모든 경로에 대해 적용해주면 된다고 생각했다.주어진 예제만 보고 다른 상황은 고려하지 못했었다.가령처럼 2 -> 5 까지 가는 길에는 2의 비용으로 모든 기름을 사야하

영단어 암기는 괴로워자주풀던 정렬문제, List의 sort 메서드의 Comparator를 오버라이딩해서 내가 원하는대로 정렬해주면 되는 문제였다.전에 사용했던 Map의 getOrDefault 메서드를 통해 해당 단어가 몇 개 있는지 쉽게 확인할 수 있었다.(역시 많이

예산오늘도 여전히 뻘짓을 한 번 했다.. ㅎㅎ문제 해결 방법먼저 설명해보자면, 순서가 중요하지 않기 때문에 정렬을 해서 푸는게 유리하다.내가 아는 지식으로 봤을 때 정렬이 되있는 경우라면 이분탐색 알고리즘을 사용하는게 가장 적합하다고 생각했다.풀이는 굉장히 간단하다~여

블로그문제를 읽고, 컴퓨터 구조 시간에 배운 TCP 쪽에 윈도우가 생각났다.무턱대고 2중 for문으로 구현했다가 아니나 다를까 시간초과 문제가 나버렸다..틀린 로직여기서 처음을 시작으로 잡고, x 범위만큼의 값을 더하면서 최대값인지 아닌지 확인해주는 로직이였다.이제보니

https://school.programmers.co.kr/learn/courses/30/lessons/42839간단하다. 문자열로 주어지는 numbers 배열에서 주어지는 숫자들로 모든 경우의 수를 탐색해 소수가 되는 숫자가 몇 개인지 반환하는 문제이다.최대

오랜만에 DP 문제를 풀어봤다.확실히 DP 문제는 그림을 그려서 각 자리에서의 최대값을 어떻게 구할지 생각해보면 답이 눈에 보이는 것 같다.여기서는 2열짜리 2차원배열로 주어지는데, 각 자리의 스티커를 뗐을 때 최대값을 구하면 된다.계산을 쉽게 하기 위해서 0번째 자리

이런식으로 0과 1로 정사각형 배열이 주어지면 1/4 씩 계속해서 탐색하면서 각 모든 값들이 0이나 1로 통일되는지 확인하고, 된다면 개수를 늘려주는 방식으로 구현하면 된다.$2^n \* 2^n$ 크기의 배열이며, n의 최대 크기는 10이기 때문에 dfs를 통한 완전

오랜만에 문제 풀이 블로깅인 것 같다.이번엔 2022 KAKAO TECH INTERNSHIP > 두 큐 합 같게 만들기 문제를 풀어보았다.문제를 읽어보면 알겠지만, 대놓고 Queue를 써보라고 유혹하고 있다.하지만, 이 문제는 투 포인터로 해결이 가능했다.종료 조건을

2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 행렬 테두리 회전하기 문제(https://school.programmers.co.kr/learn/courses/30/lessons/77485이처럼 정해진 사각형 안의 테두리를 시계방향으로 회전하면

2021 카카오 채용연계형 인턴십 > 거리두기 확인하기 문제(https://school.programmers.co.kr/learn/courses/30/lessons/81302간단한 dfs 문제로 depth 처리를 깔끔하게 해주면 해결되는 문제였다.5x5 고정