Algorithm

백준 1316번 Java 풀이

숫자맨 처음에는 그냥 쉽게 생각하고 풀었는데 테스트케이스만 보고 예외를 생각을 안해서 살짝 헤맸었다.이 문제에서 테스트케이스만으로 해결 할 수 없는 문제는 총 세가지였다.두 정수 A, B의 대소관계에 대한 말이 없음A, B가 같을 수 있다는 사실서브태스크의 2번 조건

에디터문제에서 요구하는 동작은 간단하게 4가지이다.커서를 왼쪽으로 옮기기커서를 오른쪽으로 옮기기커서 왼쪽의 문자 삭제커서 왼쪽에 문자 삽입간단하게 LinkedList로 구현하기로 하고 index를 선언 후 해당 Index를 가지고 커서의 위치를 판별하는 식으로 진행했다

N과 M(4)백트래킹과 그래프 탐색을 사용하여 숫자 두개를 입력받은 후 중복조합을 고르는 문제이다.이 문제에서는 비내림차순 이라는 것만 잘 고려하면 풀 수 있었다.

평범한 배낭 문제는 배낭 문제(knap sack)으로 많이 알려진 문제이다.

N과 M(9)여러 N과 M 문제 중 이번 문제가 가지는 특징은 중복되는 수열을 여러 번 출력하면 안되는 조건이 있다는 점이다.다른 문제들도 같은 조건이 있지만 이번 문제의 예제 입력을 보면 주어지는 수열에 중복되는 숫자들이 있다는 점을 유의하면 된다.

곱셈문제를 보자마자 알 수 있겠지만 일반적인 방법으로 곱해서는 절대 풀 수 없는 문제이다. 시간 제한도 0.5초 이고 숫자도 int 의 최대범위 이하의 자연수로 되어있다.

절댓값 힙우선순위 큐를 사용하여 자료구조를 구현하는 문제이다.큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

플로이드문제에서도 알 수 있다시피 플로이드-워셜 알고리즘을 사용하여 푸는 문제이다.플로이드-워셜 알고리즘 은 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘이다.다익스트라 알고리즘과는 다르게 그래프에 음수 사

벽 부수고 이동하기문제를 읽으면서 그래프 탐색이라는 것은 바로 알 수 있을 거고 이 문제가 가지는 특징은 한 개의 벽을 부수고 이동하는 것이 가능하다는 점이다.

트리 순회 문제 문제 설명 트리를 순회하는 세가지 방법 전위 순회(Preorder) 루트 -> 왼쪽 -> 오른쪽 중위 순회(Inorder) 왼쪽 -> 루트 -> 오른쪽 후위 순회(Postorder) 왼쪽 -> 오른쪽 -> 루트 이 세가지 방법으로 트리를

최소비용 구하기며칠전에 풀었던 플로이드 문제와 같은 정점부터 정점까지의 최소 경로를 구하는 문제이다.플로이드 문제와 다른 점은 이번 문제에서는 출발점에서 도착점까지의 최소경로만 구하면 되는 것이다.

숨바꼭질 3한 수직선 상 위에 수빈이의 위치 N과 동생이 있는 위치 K가 주어지고 수빈이의 위치가 X때 이동가능한 곳은 X-1, X+1, 2X가 가능하다고 할 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.이 문제는 BFS로 접근하면 풀 수 있다.

쉬운 계단 수N이 주어질 때, N자리 수 중 계단 수 라는 것을 구하는 문제이다.여기서 계단 수란 인접한 모든 자리의 차이가 1인 수를 뜻한다.사실 이 문제를 처음 보자마자 DP로 풀겠다고 떠올리기는 힘들었지만 요즘 동적계획법에 있는 문제들을 풀고 있어서 DP로

포도주 시식 포도주의 순서와 양이 주어졌을 때, 연속으로 3잔을 마실 수 없다는 조건 하에 가장 많은 포도주를 먹었을 때를 구하는 문제이다. 최근 DP 문제를 풀었다면 계단오르기 문제와 비슷하다고 생각하겠지만 조건이 조금은 다르다.

가장 긴 바이토닉 부분 수열가장 긴 바이토닉 부분 수열을 구하는 문제이다.바이토닉 부분 수열이란 연속적으로 계속 증가하거나, 계속 감소하거나, 증가하다가 감소하는 수열을 말한다.문제에서 예를 든것 처럼 {10, 20, 30, 40, 50} , {10, 20, 30, 2

안전 영역건물들의 높이가 주어진 좌표 내에서 수면의 높이에 따른 안전지대 구역 개수의 최대값을 구하는 문제이다.그래서 그냥 그래프를 DFS 로 돌면서 다 해보는 방법으로 해보기로 했다.일단 건물들의 높이를 입력받으면서 최대 건물의 높이를 파악을 한 후 해당 높이까지만큼

섬의 개수여러 개의 테스트 케이스가 주어지고 너비 w와 높이 h가 주어졌을 때 상하좌우, 또는 대각선으로 이어진 섬의 개수를 출력하는 문제이다.따로 예외처리할 사항은 없고 그냥 문제조건에 맞게 DFS를 해주면 풀리는 문제였다.일반적인 다른 그래프 문제와 다른 점이라면

나이트의 이동체스의 나이트의 초기 위치와 목적 위치가 주어졌을 때 나이트가 최소 몇 번 만에 이동할 수 있는지를 구하는 문제이다.최소거리를 구해야하니 이번엔 BFS를 사용해서 구현하기로 하였다.BFS로 구하면 최단거리를 정확하게 계산할 수 있다.BFS 에서는 Queue

영역 구하기모눈종이와 안에 들어갈 사각형들의 왼쪽 아래와 오른쪽 위 꼭짓점의 x, y 좌표값이 주어졌을 때 사각형이 아닌 영역들의 개수와 넓이를 구하는 문제이다.최소거리를 구하는 것이 아니기 때문에 DFS를 사용해서 완전 탐색을 해서 풀어야한다.문제에서의 x,y 좌표는

도키도키 간식드리미 일단 문제 길이가 굉장히 길어서 어려워보이지만 그냥 간단하게 생각하면 줄이 있고 그 줄을 다른 공간에 집어넣으면서 과연 순서대로 간식을 받을 수 있는지 푸는 문제이다. 다른 공간에 집어넣었다가 나오는 순서는 들어간 역순으로 나

기울어진 직사각형n X n 크기의 격자가 주어졌을 때 직사각형으로 순회를 하였을 때 합이 최대가 되는 값을 구하는 문제이다.일단 모든 방식을 다 확인해야하기 때문에 브루트포스 와 DFS를 사용하였다.문제를 풀면서 생각한점은 과연 몇중 for문을 써야지 문제가 풀릴까였다

노드들에 대한 정보가 주어졌을 때 BFS를 사용했을 때 정점의 방문 순서를 오름차순으로 출력하는 문제이다.노드들의 정보를 저장하기 위해 ArrayList 를 담을 배열을 선언하고 해당 정보에 양방향 간선에 대한 정보를 저장해주었다.그리고 이번 문제에서 인접 정점을 오름

로봇청소기로봇 청소기의 좌표 r,c 가 주어지고 방의 크기와 방의 정보가 주어지면 로봇청소기의 청소 순서에 따라 청소를 하고 청소를 할 수 없을 때까지 청소한 칸의 개수를 세는 문제이다.로봇청소기의 조건은 아래와 같다.처음 빈칸은 청소되어 있지 않다.현재 칸의 주변 4

주유소도시의 개수가 주어지고 각 도시의 기름 가격과 다음 도시까지의 거리가 주어졌을 때 마지막 도시까지 어떻게 기름을 최소비용으로 해서 도달할 수 있는지를 물어보는 문제이다.일단 이 문제는 Greedy Algorithm을 사용한다. 그리디 알고리즘은 아래와 같은 특성을

부분합수열이 주어지고 수열의 연속 합이 입력에서 주어지는 S 이상이 되는 최소의 길이를 구하는 문제이다.일단 문제에서 부분합이라고 했으니 부분합을 구해주고 2중 for 문으로 문제를 풀려고 했다.문제에서 주어지는 기본 배열을 저장할 arr 배열과 누적합을 구해줄 pre

알파벳R X C 로 이루어진 보드에 알파벳들이 적혀있는데 전부 다른 알파벳으로 그래프를 순회했을 때 최대 몇 칸을 지날 수 있는지 구하는 문제이다.일단 최단거리를 구하는 것이 아니기 때문에 BFS가 아닌 DFS를 사용해야 하고 여러 경로 중 비교를 해야하니 백트래킹을

알고리즘 수업 - 깊이 우선 탐색 6시작 정점 R이주어졌을 때 DFS로 정점들을 방문하였을 때 방문된 노드들에 대하여 i번 노드의 깊이 배열 d 와 i번 노드의 방문순서 t 에 대하여 di × ti 값의 합을 구하는 문제이다.인접 정점을 내림차순으로 방문한다는 점에 유

문제그래프의 정점과 간선의 정보가 주어졌을 때 트리의 개수를 세는 문제이다.이 문제에서 유의해야할 점은 싸이클 발생 여부이므로 유니온 파인드로 풀기로 하였다.주어진 간선들의 정보로 노드들을 연결시키고 Union 과정을 통해서 사이클을 판별하고 루트 노드에 대한 정보를

숨바꼭질 2백준의 숨바꼭질 문제와 같은 문제이지만 최단 시간을 구하는것과 그 방법의 개수를 모두 구하는 문제이다.최단 시간을 구하고 개수를 구해야하기 때문에 BFS 알고리즘을 사용하여 최단 시간을 구하고 다른 방법들을 통해서 도착지에 도착했을 때 최단시간과 같다면 개수

펠린드롬?숫자로 이루어진 배열이 주어지고 해당 배열의 시작과 끝이 주어졌을 때 그만큼의 부분 수열이 좌우대칭인 펠린드롬인지 판별하는 문제이다.처음엔 그냥 isPalindrome 이라는 함수를 구현하여 문제에서 주어지는 s 값과 e 값을 이용하여 substring 한 값

RGB거리 2기존의 RGB거리 문제에서 조건이 추가된 문제이다.추가된 조건은 이렇게 두가지 이다. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.단순히 말하면 첫번째 집과 마지막 집의 색이 달라야

용액용액들의 특성값이 주어질때 해당 용액들을 잘 합쳐서 0에 가장 가깝게 만드는 문제이다.문제에서 정렬된 순서로 주어지니 따로 정렬을 할 필요도 없고 그냥 왼쪽 포인터변수 하나, 오른쪽 포인터변수 하나를 이용해 문제를 풀면 된다.포인터 변수 left, right를 선언

서버 증설 횟수사용자들의 수가 0시부터 24시까지 주어질때 필요한 서버의 개수를 구하는 문제이다. 문제에서 주어지는 조건은 사람이 m명 이상일 때부터 서버가 1개씩 늘어나고 해당 서버는 k시간 후에 없어진다는 조건이다.일단 첫번째로 현재 인원수를 기준으로 필요한 서버수

파티파티에 참가하는 N 명이 목적지인 X 마을까지 왕복해야하는데 가장 오래걸리는 사람의 소요시간을 구하는 문제이다.모든 정점에서 모든 정점까지의 거리가 아닌 각 출발지에서 하나의 정점인 X까지 가는 거리와 X에서 모든 정점까지의 거리를 구하면 되니 플로워셜 대신 다익스

테트로미노숫자가 적혀진 N X M 크기의 종이가 있을 때 그 위에 주어진 4칸짜리 도형들 중 하나를 적절하게 배치해서 가장 최대의 값을 구하는 문제이다.문제에서 주어진 모형들을 잘 살펴보면 보라색 ㅜ 모양 을 제외하고는 모두 상하좌우 완전탐색을 하면 전부 확인할 수 있

MooTube (Silver)N개의 동영상이 있고 동영상 끼리의 유사도 가 주어지는데 영상끼리의 유사도가 K 이상이라면 해당 영상은 추천동영상이 된다고 할때 K와 어떤 동영상의 번호 V가 주어지면 V 동영상의 추천 동영상은 몇개인지 출력하는 프로그램이다.일단 유사도를

비밀 코드 해독(https://school.programmers.co.kr/learn/courses/30/lessons/388352어릴 때 했던 숫자야구랑 비슷한데 스트라이크랑 볼의 개념이 아니고 그냥 무조건 오름차순으로 주어졌을 때 일치하는 개수를 알려주면

퍼즐 게임 챌린지일단 문제가 굉장히 길어서 읽기가 싫었는데 요약을 하자면 문제의 난이도와 푸는 시간이 주어진다.내 수준인 level이 문제의 난이도보다 높다면 그냥 푸는 시간만큼 걸리고 내 level이 문제의 난이도보다 낮다면 전 문제를 다시 풀고 이번 문제를 다시 푸

집합1부터 20까지가 가능한 공집합 S가 주어졌을 때 주어지는 연산을 수행하는 문제이다.옛날에 풀었던 문제인데 그 때 풀때는 자료구조 Set을 이용해서 풀었는데 이번에는 비트마스킹 을 이용해서 풀어보려고 한다.위의 코드를 보면 알겠지만 단순히 그냥 자료구조에다가 연산을

기타콘서트기타들이 N개 주어지고 각 기타들이 어떤 곡을 칠 수 있는지 주어진다.이러한 기타들을 조합해서 최대한 많은 곡을 연주하고 싶을 때 필요한 최소의 기타의 수를 구하는 문제이다.비트마스킹을 사용해서 모든 조합의 수를 구한다.예제에서 주어진 4개의 기타를 사용한다면

후보키테이블의 정보가 String\[]\[] relation 형태로 주어졌을 때 이 테이블에서 나올 수 있는 후보 키의 최대 개수를 구하는 문제이다.비트마스킹 문제를 풀려고 찾은 문제여서 비트마스킹으로 접근했다.코드를 짜기 전 생각한 구현 단계는1\. 비트마스킹으로 나

감시최대 8 X 8 크기의 격자 내에 1번부터 5번 종류의 CCTV의 위치와 벽의 정보가 주어진다.이 상황에서 각 위치에 있는 CCTV 들을 회전할 수 있을 때 감시 사각 지대의 최소 크기를 구하는 문제이다.일단 혼자 생각하다가 바킹독님의 시뮬레이션 강의를 참고해서 풀

조이스틱게임할 때 이름을 바꾸는 거처럼 조이스틱으로 A로 채워져 있는 기본 문자열을 내가 원하는 name 으로 바꾸는 문제이다.주의해야 할 점은 커서는 순환되는 구조여서 처음과 끝을 이동할때 역방향으로 이동할 수 도 있다.첫번째로 구한 방식에서 테스트케이스는 통과했는데

예산지방의 수 N 이 주어지고 각 지방에서 요구하는 예산이 주어진다.이때 정부의 예산 총액이 M 이라고 주어질 때 예산안에 맞게 예산을 배정하고 예산 중 최댓값인 정수를 출력하는 프로그램이다.각 지방에서 요구하는 예산의 총액이 정부 예산 총액보다 적다면 그냥 다 배정하

치즈N X M 크기의 모눈종이 위에 치즈의 위치정보가 1로 주어진다.치즈는 공기에 두 면 이상이 노출 되면 1시간 후에 사라지는데 치즈로 둘러쌓인 공기는 노출되었다고 치지 않는다.격자의 정보가 주어졌을 때 치즈들이 모두 녹는데 얼마나 걸리는지 계산하는 문제이다.일단 기

후위표기식중위 표기식으로 되어있는 수식을 후위 표기식으로 바꾸는 문제이다.'스택에 연산자를 넣으면서 풀면 될 것 같아서 그렇게 생각을 하고 방향을 잡고 생각을 하고 있었는데 괄호처리 방법을 잘 모르겠고 연산자의 우선순위를 고려하다 보니 코드가 너무 난잡해져서 어떻게 해

블로그N 일 동안의 방문자 수가 입력으로 주어질 때 입력으로 같이 들어오는 X 일의 기간동안의 최대 방문자 수와 최대 방문자 수를 보유한 기간의 개수를 출력하는 문제이다.일단 첫번째로 푼 방법은 틀렸다.일단 코드부터 보면 배열에서 구간을 정해주고 해당 구간동안의 구간합

트리의 지름트리의 정점의 개수와 간선에 대한 정보들이 주어질때 이 트리의 한 정점에서 어떤 정점까지의 거리를 구했을 때 그 중 가장 긴 거리를 트리의 지름이라고 한다.트리의 지름을 출력하면 되는 문제이다.트리의 지름을 구하려면 가장 먼 두 정점을 알아야 한다.그래서 생

사이클 게임점의 개수 n 과 진행된 차례의 수 m 이 주어지고 다음 m 줄 동안 두개의 점들을 고른다.이렇게 계속 턴을 바꿔가며 점들을 고를 때 만약에 사이클이 완성 되었다면 해당 턴을 출력하고 마지막까지 사이클이 완성되지 않는다면 0 을 출력하는 문제이다.일단 사이클

나무 섭지N X M 크기의 격자안에 남우의 위치, 벽의 위치, 출구의 위치, 귀신의 위치들이 주어진다.남우는 귀신과 벽을 피해 출구에 도달해야 하는데 귀신은 벽을 뚫고 이동하기 때문에 귀신을 잘 피해서 도망가야한다.남우가 탈출을 할 수 있다면 Yes를, 탈출하지 못한다

이중 우선순위 큐테스트케이스 T 와 각 테스트케이스에 대해서 들어올 입력의 개수 k 가 주어진다.입력은 어떤 연산을 할지, D 또는 I 가 들어오며, I 는 삽입 연산을 의미한다.D 는 삭제를 뜻하는데 다음으로 들어오는 숫자가 1 이라면 최댓값을, -1 이라면 최솟값을

파이프 옮기기 1두칸을 차지하는 파이프가 있다.N x N 크기의 격자에 벽과 빈 공간의 위치가 주어진다. 파이프는 가로 방향, 세로방향, 대각선 방향이 가능하다.초기의 파이프가 (1, 1) (1, 2) 를 차지하고 있을 때, 파이프의 한쪽 끝이 (N, N) 까지 이동시

빙산N x M 크기의 격자에 물의 위치 0 과 한 덩어리로 이루어진 빙산들의 높이가 주어진다.각각의 빙산들은 1년마다 물이 맞닿은 수 만큼 녹는다고 할 때 이 하나의 빙산 덩어리가 두개로 나눠지는 최초의 시간을 출력하고 다 녹을 때까지 분리되지 않는다면 0을 출력하는

탑탑의 개수 N 과 이 탑들의 높이가 주어진다.각 탑은 꼭대기에서 왼쪽으로 레이저 신호를 발사하는데 이 레이저 신호는 신호를 발사한 곳 보다 높은 탑에서만 수신할 수 있다고 한다.이 때 각 탑에서 레이저 신호를 수신하는 탑들의 번호를 출력하는 프로그램이다.처음에는 입력

\[1차] 뉴스 클러스터링두 문자열의 유사도를 구하는 문제이다.자카드 유사도라는 것을 구하는데 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값이다.만약 두 집합이 모두 공집합이라면 자카드 유사도는 1이며, 문제에서는 입력으로 들어온 문자열을 두 글자씩 끊어서

IP 주소IP네트워크는 네 개의 바이트로 이루어져있고 각 바이트는 0부터 255까지의 값을 가진다.이 때 앞의 32-m 자리는 0 또는 1로 이루어져 있고 뒤의 m자리는 0으로 채워진다.이와 같은 IP네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP

줄 세우기N명의 학생 중에서 일부 학생들을 뽑아서 M번 비교한 결과가 주어진다.결과를 보고 비교한 결과에 맞게 줄을 세운 결과를 출력하는 문제이다.며칠 전에 푼 한 줄로 서기 문제랑 비슷한 문제인줄 알았는데 이번 문제는 나보다 큰 사람이 정확히 누구인지 주어지기 때문에

Dance Dance RevolutionDance Dance Revolution 게임을 하는데 발을 움직일 때 얼마나 힘이 드는지 주어진다.문제에서 주어지는 이동을 전부 해야할 때 드는 최소의 힘을 구하는 문제이다.처음에는 프로그래머스에서 풀었던 키패드 누르기 처럼 그

외판원 순회외판원 순회(TSP : Traveling Salesperson Problem) 문제는 도시들이 있고 어떤 도시에서 출발하여 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소비용을 구하는 문제이다.백준에 외판원 순회 문제가 또 있는데 그 문제와 똑같이

음악프로그램간단하게 설명하자면 메인 PD가 되어서 보조 PD들의 요구를 모두 맞춰주어야 하는 문제이다.문제 예제를 예를 들어 설명하면 6팀의 가수가 있다고 했을 때 보조 PD들이 아래와 같이 순서를 정해왔다고 하자.보조PD들이 정해온 순서를 모두 만족시키기 위해서는 6

텀 프로젝트텀 프로젝트를 수행하기 위해 팀을 짜는 문제이다.1번부터 N번까지의 학생이 각자 원하는 사람을 선택을 하고 사이클이 생겨야 팀을 구성 할 수 있다.이렇게 구성한 팀에서 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램이다.처음에는 유니온 파인

장난감 조립N 이 주어지고 완제품이나 중간부품들을 만드는데 부품들이 얼마나 필요한지 주어진다.이때, 하나의 완제품을 만드는데 기본 부품들이 얼마나 필요한지 출력하는 문제이다.문제에서 X를 만드는데 Y 라는 부품이 K개 사용된다는 정보가 있다.이 것을 토대로 위상정렬을