Algorithm
[백준] 2491. 수열 python
🐳 링크 백준 수열 🐕 문제 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 예를 들어 수열 1 2 2 4 4 5 7 7 2 의 경우에는 1≤2≤2≤4≤4≤5≤7≤7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4 1 3 3 2 2 9 2 3 의 경우에는 3≥3≥2≥2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1 5 3 6 4 7 1 3 2 9 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다. 🐾 풀이 방법 if문을 이용한 단순 ..
[백준] 5567. 결혼식 python
🐳 링크 백준 결혼식 🐕 문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 🐾 풀이 방법 상근이와 친구인 친구들을 f에 저장해놓고, f와 친구인 사람만 확인한 뒤 중복되지 않도록 set에 저장한다. 소스코드 import sys sys.stdin = open("input.txt","rt") n = int(sys.stdin.readline().strip()) m = int(sys.stdin.readline().strip()..
[백준] 16236. 아기 상어 python
🐳 링크 백준 아기상어 🐕 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다. 더 이상 먹을 수 있는 물고기가 공간..
[백준] 9663. N-Queen python
🐳 링크 백준 N-Queen 🐕 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 🐾 풀이 방법 n_queen 함수를 실행시킬 때에는 열을 이용해서 실행시키고, 들어간 순서대로를 행으로 배정하여 같은 열에 있는 노드와 대각노드를 제외한다. 예를 들자면, n=4인 경우 0,1,2,3 순으로 n_queen함수를 실행시키게 된다. 이때 arr에 [0,1] 이 들어가있다면, 이는 (0,0), (1,1)에 퀸이 놓여있다는 것을 의미한다. 따라서 n_queen 함수 내에서 같은 열에 위치 즉, 현재 arr값과 같은 값이면 제외하고 distance를 구해서 대각노드도 제외하는 방법으로 이..
[백준] 1149. rgb 거리 python
🐳 링크 백준 rgb거리 🐕 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 🐾 풀이 방법 26 40 83 # 1번집, 빨, 초, 파 49 60 57 # 2번집, 빨, 초, 파 13 89 99 # 3번집, 빨, 초, 파2번집을 빨강색으로 칠하게 된다면 1번집은 초..
[백준] 1260. dfs와 bfs python
🐳 링크 백준 dfs와 bfs 🐕 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 🐾 풀이 방법 dfs와 bfs로 문제를 해결할 수 있는 가장 기초적인 문제인 것 같다. 방법은 비슷하지만, dfs는 graph의 값이 1인 경우에 자식 노드로 향하기 위해 재귀를 이용하고, bfs는 graph의 값이 1인 경우에는 큐에 삽입하고 또 다른 형제노드에서 1인 값이 있는지 확인한다. 즉, dfs는 더 깊이 bfs는 더 넓게라고 생각하면 좋을 듯. dfs와 bfs [그림 출처 : https://na..
[백준] 2206. 벽 부수고 이동하기 python
🐳 링크 백준 벽 부수고 이동하기 🐕 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 🐾 풀이 방법 bfs문제에 벽을 부수는 조건이 추가된 문제이다. 방문했다는 것을 확인하기 위한 visit 배열을 단순히 [0] 이 ..
[programmers] 기능 개발 python
문제 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수입..
[programmers] 베스트 앨범 python
문제 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다. ..
[programmers] 카펫 python
문제 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 소스코드 def solution(brown, yellow): answer = [] # i*j = yellow for i in range(1, int(yellow**0.5)+1): if not yellow % i: #나누어..