Algorithm
[백준] 1316. 그룹 단어 체커 python
[백준] 1316번 그룹 단어 체커 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 풀이과정 alpha라는 딕셔너리에 나온 알파벳이면 key를 알파벳으로, value를 index로 저장한다. 이후 같은 알파벳이 등장한 경우에 alpha[key] 값과 현재 인덱스 차이가 1인 경우에만 진행하고, 아닌 경우(떨어져서 나타나는 경우)에는 중단하도록 하였다. 소스코드 ..
[백준] 2839. 설탕 배달 python
[백준] 2839번 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 풀이과정 n//5만큼의 루프를 역으로 돌아서 (ex. n//5가 5이면 5,4,3,2,1,0..
[백준] 10026. 적록색약 python
[백준] 10026번 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사..
[백준] 7562. 나이트의 이동 python
[백준] 7562번 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 풀이과정 나이트가 이동할 수 있는 8칸을 dx, dy를 통해 나타내었다. bfs를 활용하여 방문하지 않은 노드에는 이전 노드의 값에 1을 더해줌으로써 해당 노드까지 가는데 움직인 칸 수를 나타내었다. 소스코드 import sys input = sys.stdin # 나이트가 이동할 수 있는 칸 dx = [-2,-2,-1,-1,1,1,2,2] dy = [-1,1,-2,2,-2,2,-1,1] def bfs(start, end, visit, l): q = [(start[0], ..
[programmers] 단어 변환 python
[프로그래머스] 단어 변환 문제 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도..
[programmers] 정수 삼각형 python
[프로그래머스] 정수 삼각형 문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 풀이과정_bfs 삼각형을 행렬로 변환시킨다. 7 7 -1 -1 -1 -1 3 8 3 8 -1 -1 -1 8 1 0 --> 8 1 0 -1 -1 2 7 4 4 2 7 4 4 -1 4 5 2 6 5 4 5 2 6 5 visit 배열을 만들어서, visit 값이 0..
[programmers] 가장 먼 노드
[프로그래머스] 가장 먼 노드 문제 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 풀이과정 인접 리스트에 값을 대입해준다. visit 배열을 이용해 방문하지 않은 경우에 거리를 대입해준다. 대입해준 이후에는 cnt 를 1 증가시킨다. q에는 현재 노드의 인접 에지들의 [노드 번호, 지나온 거리] 값을 삽입한다..
[백준] 10844. 쉬운 계단 수 python
[백준] 10844번 쉬운 계단 수 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 풀이과정 0 1 2 3 4 5 6 7 8 9 1자리 0 1 1 1 1 1 1 1 1 1 2자리 1 1 2 2 2 2 2 2 2 1 3자리 1 3 3 4 4 4 4 4 3 2n자리수로 만들 수 있는 계단 수들은 위와 같다. 2자리수일 때, 0을 끝자리로 만들 수 있는 수는 10 한가지이다. 1을 끝자리로 만들 수 있는 수는 21 한가지, 2를 끝자리로 만들 수 있는 수는 12 ..
[백준] 11057. 오르막 수 python
[백준] 11057번 오르막 수 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 풀이과정 0 1 2 3 4 5 6 7 8 9 SUM 1자리수 1 1 1 1 1 1 1 1 1 1 [10] 2자리수 1 2 3 4 5 6 7 8 9 10 [55] 3자리수 1 3 6 10 15 21 28 36 45 55 [220]규칙: dp[i][j] = dp[i][j-1] + dp[i-1][j] 1로 끝나는 3자리 수를 만든다고 가정하면,..
[백준] 14888. 연산자 끼워넣기 python
[백준] 14888번 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×..