Algorithm
[프로그래머스] 위장 Java
소스코드는 Github에서도 확인하실 수 있습니다. [프로그래머스] 위장 Java 풀이 🚀 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 위와 같이 의상이 정해져있다고 했을 때, 가짓수는 다음과 같이 계산할 수 있다. 1. 동그란 안경을 쓰냐 안쓰냐 2. 검정 선글라스를 쓰냐 안쓰냐 3. 파란색 티셔츠를 입냐 안입냐 따라서 각각에 대해 안입는 경우의 수를 추가하여 +1을 하고, 마지막에 모두 입지 않는 경우를 -1 해주어 계산할 수 있다. 그 과정에서 나는 HashMap을 사용하였는데, 그 이유는 다음과 같다. 얼굴에 장착할 수 있는 의상이 두 가지가 존재하는데, 이 두가지는 동시에 착용할 수 없다. 따라서 해쉬맵에 {"얼굴": {"동그란 안경", "선글라스"}, "상의": "파란색 티셔츠"} 와..
[프로그래머스] 전화번호 목록
소스코드는 Github에서도 확인하실 수 있습니다. [프로그래머스] 전화번호 목록 풀이 🚀 우선, 자료구조에 관계없이 풀이하는 방법에 대해서만 이야기해보자. {"119", "1234", "11911225"}라는 전화번호들이 존재할 때, 우리는 전화번호 목록에 속하는 A, B에 대해 A가 B의 접두사가 되는 A가 있는지를 확인하고 있다면 false를, 없다면 true를 리턴해야한다. 먼저, 특정 자료구조를 선언한 뒤 그 자료구조에 각 값들을 모두 넣는다. 그 후, phone_book을 순회, 각 인덱스의 값들을 슬라이싱하며 우리가 넣어둔 자료구조에 그 값을 포함하는 값이 있는지 확인한다. 예를 들자면 아까와 같이 {"119", "1234", "11911225"} 가 자료구조에 들어있을 때, 우리는 "119..
[프로그래머스] 124 나라의 숫자 Java
소스코드는 Github에서도 확인하실 수 있습니다. [프로그래머스] 124 나라의 숫자 풀이 10진법 124나라 10진법 124나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 규칙을 찾으면 다음과 같다. 주어진 10진법 수를 n이라고 하면, n을 3으로 나눈 나머지 값에 따라 각각 "4", "1", "2"로 나타내어진다. 124 숫자에서 나타낼 수 있는 수는 1,2,4만 존재하며, 나머지가 0일 때엔 "4"로, 1일 때엔 "1"로, 2일 때엔 "2"로 나타낼 수 있다. 인덱스에 맞게 배치하면 다음과 같다. Strings = {"4", "1", "2"} if n이 2인 경우: n % 3 = 2 이므로, 2는 Strings[2]인 "2"로 나타낼 수 있다. 그렇다면..
[programmers] 네트워크 python
🐳 링크 프로그래머스 네트워크 🐕 문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 🐾 풀이 방법 컴퓨터의 번호를 기준으로 탐색한다. 먼저, 컴퓨터의 수 만큼 visit이라는 방문 배열을 만든다. 해당 번호의 컴퓨터를 방문했다면 vi..
[programmers] 타겟 넘버 python
🐳 링크 프로그래머스 타겟넘버 🐕 문제 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 🐾 풀이 방법 상태 트리를 생각해보면, 각 numbers의 원소에 대해서 취할 수 있는 경우의 수는 더하거나, 빼거나 둘 중 하나이다..
[백준] 3190. 뱀 python
🐳 링크 백준 3190번 뱀 🐕 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워..
[백준] 2563. 색종이 python
🐳 링크 백준 2563번 색종이 🐕 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 그림 출처: https://www.acmicpc.net/problem/2563 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 🐾 풀이 방법 매우 단순하게, 2*2 색종이의 넓이를 계산한다고 생각해보자. 이때, 색종이의 넓이는 2*2 = 4로 계산할 수도 있고, 색종이를 모..
[백준] 1965. 상자 넣기 python
🐳 링크 백준 1965번 상자넣기 🐕 문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다. 상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오..
[백준] 1753. 최단 경로 python
🐳 링크 백준 1753번 최단경로 🐕 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한..
[백준] 4963. 섬의 개수 python
🐳 링크 백준 4963번 섬의 개수 🐕 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 🐾 풀이 방법 그래프 문제 중 간단한 문제이다. dx, dy에 상하좌우 + 대각선을 추가하여 자신 기준으로 총 8번을 탐색할 수 있도록 해준다. 연결되어있으면 계속 진행하고, 대신 자신을 0으로 만든 뒤 다음 노드로 진행해준다. 이미 연결되었다고 생각하므로 graph에서 0값으로 바꾸어주는 것이다. df..