아리의 개발 일상

[삼성sw 파이썬] 14413 격자판 칠하기 문제N x M 크기의 직사각형 격자판에서 각 칸의 크기는 1x1 크기의 정사각형 모양이다.이 격자판을 흰색 또는 검정색으로 칠할 계획이다.N  x M 크기의 행렬 A가 있어서, Ai,j 가 ‘#’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해야 하고, Ai,j 가 ‘.’라면 격자판의 i행 j열에 있는 칸은 흰색으로 칠해야 하며, Ai,j 가 ‘?’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해도 되고 흰색으로 칠해도 된다.이대 인접한 두 칸의 색은 항상 다르게 할 수 있는지 판단하는 프로그램을 작성해야한다. 입력첫 번째 줄에는 테스트 케이스 수가 주어진다.각 테스트 케이스 첫번째 줄에는 N,M이 주어지고 그다음줄에는 행렬 A가 N개의 줄에 나타난다...

[파이썬 삼성sw] 6057 그래프의 삼각형문제정점이 N개, 간선이 M개 있는 그래프가 주어진다. 정점에는 1번에서 N번까지의 번호가 붙어 있다.이때 i 번 정점과 j 번 정점 사이에, j번 정점과 k번 정점 사이에, k번 정점과 i번 정점 사이에 모든 간선이 있는(i, j, k)를 삼각형이라고 하자 (i 이때 삼각형 개수를 구하는 프로그램을 작성하라.입력첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.각 테스트 케이스의 첫 번째 줄에는 두정수 N, M이 공백으로 구분되어 주어진다.다음 M개의 줄에는 두 정수 X, Y가 주어진다.이는 X번 정점과 Y번 정점 사이에 간선이 있다는 의미이다.출력삼각형의 개수를 출력한다.풀이나는 DFS를 이용하여 풀었다.1번 정점에서부터 시작해서 1번 정점에서 연결된 모든 ..

[파이썬 알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘이란?모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 정점수만큼 반복하는 거와 같은 결과값을 가지지만시간복잡도가 O(n³) 이기에 정점의 수가 적을때에는 다이스트라 알고리즘보다 빠른 결과값을 받을 수 있다. 알고리즘 동작 과정비용 테이블 초기화:모든 정점 간의 최단 거리 정보를 담는 테이블을 생성합니다. 처음에는 무한대(inf)로 설정하여, 아직 연결되지 않은 상태를 나타냅니다.간선 정보 입력:간선 정보를 입력받아, 두 정점 사이의 거리를 그래프 테이블에 입력합니다. 간선 정보는 (a, b, c) 형식으로, a에서 b로 가는 거리가 c라는 뜻입니다.자기 자신으로 가는 거리는 0으로 설정:..

[삼성 sw 파이썬] 4371 항구에 들어오는 배 문제항구에 배가 들어오 늘 날을 '즐거운 날' 이라고 하자. 이때 각 배들은 항구를 주기적으로 방문한다. 예를 들어 주기가 3인 배는 항구에 1일 차 4일 차 7일 차 등에 방문하게 된다.1일 차부터 기록한 '즐거운 날' 들의 목록이 주어질 때 항구에 들렀던 배의 최소 수를 알아내자.(이때 모든 배는 1일 차에 방문한다.) 입력첫번째 줄에 테스트 케이스두 번째 줄부터는 각 케이스의 첫 번째 즐거운 날의 수 n이 주어진다.각 테스트 케이스의 두 번째 줄부터 n개의 줄에 걸쳐 즐거운 날의 정보가 오름 차순으로 정렬되어 주어진다. 출력각 테스트 케이스마다 항구에 들렸던 배의 최소 수를 출력한다. 풀이각 배들이 들어오는 주기가 존재하면 이때 배의 들어오는 배의 ..

[삼성 sw 파이썬] 2814 최장 경로문제N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서 최장 경로의 길이를 계산하자.정점의 번호 1부터 N번까지 순서대로 부여된다.경로에는 같은 정점의 번호가 2번 이상 등장할 수 없다 경로 상의 인접한 점들 사이에는 반드시 간선이 존재한다.경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다. 입력첫 줄에는 테스트케이스가 주어진다.각 테스트 케이이스의 첫 번 줄에는 두 개의 자연수 N, M이 주어진다.두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타낸다.풀이문제에서 가중치가 없는 무방향 그래프라고 주어졌으면 경로상의 가장 경로를 탐색하는 완전 탐색 문제로DFS나  BFS를 이용아여 문제를 풀 수 있다.나는 DFS르 이용하여 문제를..

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이으로 이 게임을 했을 때 모든 사람 나오는 단계의 총 합을 케빈 베이컨의 수라고 할 때 이때 이 수가 가장 적은 사람을 찾는 문제이다. 이때 단계를 계산하는 방법으로 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.1은 2까지 3을 통해 2단계 만에 연결될 수 있으며, 3까지는 1단계 , 4까지 1단계 , 5까지는 4를 통해 2단계만에 연결된다그러면 케빈 베이컨의 수는 2+1+1+2 = 6이다...

[삼성 sw 파이썬] 1945 간단한 소인수분해 문제숫자 N이 주어질 때 N=2^a * 3^b * 5^c *7*d * 11^e의 형태로 표현할 수 있다.이때 a,b,c,d,e를 출력하라 풀이기본적인 구현 문제로 while를 사용하여 2,3,5,7,11 모두 다 하면서 a, b, c, d, e를 구하는 방법이 가장 기본적으로 있다 이때 while부분이 반복되기에 함수로 만들어서 재귀형태로 풀어서 문제를 풀었다.def factors(number,a,count): if number % a != 0: return [count,number] return factors(number//a,a,count+1)number은 현재수이고 a는 나눌수 count 몇 번이나 a로 나누어 버렸는지 카운트하..

[삼성 sw 파이썬] 19185 육십갑자문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 육십갑자 라는걸 간다히 말해서 N개의 문자열 s1, s2, s3 …, sN 과 M 개의 문자열  t1, t2, t3, …, tM 있는데 1년에 두문자열의 s1과 t1 합친 문자열을 이름으로 사용한다.자 예를 들어 s={a, b, c} , t={d, e, f, g}라 하면yearSTNAME1adad2bebe3cfcf4agag5bdbd6cece7afaf8bgbg...................위의 표와 같은 형식으로 이름이 나온다. 두 문자열의 리스트와 Q개의 질문이 주어질때 각 질문에서 녀도로부터 만들어지는 이름을 만들면 ..

[백준 파이썬] 보물 1026 문제길이가 N인 정수 배열 A와 B가 있다 다음과 같이 함수 S를 정의하자. S의 값을 가장 작게 만들기 위해 A의 수를 재배열 하자 단, B에 있는 수는 재배열하면 안 된다.S의 값이 최소가 되는 프로그램을 작성하라.입력첫째줄에 N이 주어진다.둘째 줄에는 A의 배열이 주어진다.셋째 줄에는 B의 배열의 주어진다. 출력첫째줄에 S의 최솟값을 출력한다.풀이A배열만 움직여 B배열과 곱셈을 하여 모든 값을 다 더한 값을 S이다. 이때 A배열의 인덱스만 움직여야 한다고 한다. B배열의 값들의 위치는 정해져 있고 최솟값이 되기 위해서는 B배열의 높은 값을 A배열의 가장 낮은 값을 곱셈하도록 만들어주면 가장 낮은 S값이 된다. 결론은 A 배열을 오름차순으로 정렬한고 B배열을 내림차순으로..

[백준 파이썬] 14502번 연구문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 연구소의 크기는 N x M인 직사각형으로 나타낼 수 있으면 1X1 정크기의 정사각형으로 나누어져 있다.연구소는 빈칸과 벽칸으로 이루어져 있다. 바이러스는 인접한 상화좌우로 퍼져나갈 수 있다.벽을 세워서 바이러스가 퍼지는걸 막아야 하는데 세울 수 있는 벽의 개수는 3개이면 꼭 3개만 세워야 한다.이때 바이러스가 퍼지지 않은 빈칸의 개수가 최대가 되는 값을 구하여라. 입력첫줄에 연구소의 세로 N과 가로 M이 주어진다그다음줄부터 N줄에 지도의 모양이 주어진다. 0은 빈칸 1은 벽 2는 바이러가 있는 위치이다.출력첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.풀이BFS와 백트래킹을 이용하여 문제..