목록알고리즘 (22)
데이터 엔지니어
문제링크: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 설명 - N: 도시의 개수 - M: 버스의 개수 - (출발 도시, 도착 도시, 버스 비용) M개 - 시작도시, 끝도시 위와 같은 입력이 주어졌을 때, 시작도시부터 끝도시까지 가는 최소비용을 구하는 문제입니다. 풀이 문제를 보자마자 최소거리를 구하는 알고리즘들을 떠올렸습니다. 코테에서 주로 나오는 그래프 알고리즘들은 아래와 같습니다. 이 문제에는 시..
프로그래머스 사이트에서 주최한 월간 코드 챌린지에 참가하였습니다. 9 / 10 / 11 월 각 한번씩 열리며 각 대회마다 4개의 문제가 주어져 1, 2, 3 등에게는 상금을 수여하고, 세 번의 대회에서 총 5문제 이상 풀 경우 이벤트 상품에 응모할 수 있는 챌린지입니다. 저는 상금 받을 정도의 실력자가 아니기 때문에 알고리즘 실력도 늘리고 이벤트 응모라도 하기 위해 참가하였습니다! 문제와 풀이를 완전히 공유하는 것은 불법이기 때문에 4문제에 대한 제 개인적인 난이도 풀이로 후기를 남기겠습니다 자세한 사항은 아래 링크를 참조해주세요. 링크: programmers.co.kr/competitions/417?slug=monthly-code-challenge-s1&utm_campaign=competition417..
문제링크: https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 설명 - N: 가수의 수 - M: 보조 PD의 수 - 각 보조 PD가 정한 가수의 순서가 주어질 때 모든 보조 PD의 순서를 만족하는 가수의 순서를 출력 - 답이 여러개일 경우 아무거나 출력, 답이 없을경우 0 출력 - ex) 보조PD가 3명(M)일 때 입력이 아래와 같이 주어지면 1 4 3 6 2 5 4 2 3 => 6 2 1 5 4 3 or 1 6 2 5 4..
문제링크: https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 설명 - L: 암호 자릿 수 - C: 알파벳 개수 - C개 알파벳으로 L 자릿 수의 암호를 만들 수 있는 모든 경우의 수를 사전순으로 출력 - 조건 1: 최소 1개의 모음 (a, e, i, o, u) - 조건 2: 최소 2개의 자음 - 조건 3: 오름차순 - 중복 x 모두 소문자 풀이 python 내장 라이브러리인 combination을 사용하여 해결하였습니다. 처음에는 permutat..
문제링크: www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 골드 4여서 두려웠지만, 경우의 수만 잘 따져주면 되는 문제였습니다. 문제 설명 - N: 숫자의 개수 - N개의 숫자가 주어진다. - 숫자를 2개씩 묶을 수 있다. 묶은 수는 곱하기로 계산된다. - 숫자는 단 한번만 묶거나 안 묶인다. - ex) -1, 2, 3, 1 이 주어졌을 때 최대의 값은 (-1)+1+(2*3)=6 이다. 풀이 처음에는 단순하게 정렬하여 양수의 큰 수 끼리 곱 음수의 작은 수..
문제링크: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 삼성 기출로 나왔던 문제입니다. 삼성 기출은 조건 확인을 확실히 해주셔야 합니다. 문제 설명 - N: 맵의 크기 - 아기 상어 초기 크기 = 2 / 크기 만큼 물고기를 먹어야 => 크기 + 1 / 상어 위치 = 9 - 지나갈 수 있는 경우: 아기 상어 크기 >= 물고기 크기 - 먹을 수 있는 경우: 아기 상어 크기 > 물고기 크기 - 먹을 수 있는 경우가 여러가지인 경우 1...
문제링크: https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제 설명 - 가로 세로가 n인 크기의 체스판에 n개의 queen을 놓을 수 있는 경우의 수 - queen은 가로 세로 대각선 이동이 가능 - n = 4 인경우 아래 이미지 처럼 2가지 경우의 수가 나옵니다. 풀이 - DFS / 백트래깅 (백트래킹은 지난 https://data-engineer.tistory.com/19에서 설명한 것 처..
문제링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 삼성 기출로 나왔던 문제입니다. 문제 설명 - N, M: 맵의 높이, 넓이 - 테트로미노: 정사각형 4개를 이어붙인 모양 - 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대 - 테트로미노들은 회전 대칭 가능 풀이 이 문제 같은 경우는 도형이 5개에다가 회전을 해도 총 경우의 수가 15가지 ex) ㅜ ㅏ ㅗ ㅓ (4가지) 가 나옵다. 각 지점마다 해당..