아리의 개발 일상

백준 16964 파이썬DFS 스페셜 저지문제BOJ에서 정답이 여러 가지인 경우에는 스페셜 저지를 사용 한다.스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다.오늘은 스페셜 저지 코드를 하나 만들어 보려고 한다.정점의 개수 N이고 정점에 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다.DFS 방문 순서는 dfs 함수에서 //x를 방문이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구하여라.입력첫째 줄에 정점수 N 이 주어진다.둘째 줄부터는 N-1개의 줄에는 트리..

[파이썬] 백준 3190 뱀https://www.acmicpc.net/problem/3190 문제Dummy라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데 , 사과를 먹으면 뱀 길이가 늘어난다.뱀이 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝이 난다. N x N 정사각 보드 위에서 진행되고 몇몇 칸에 사과가 놓여 있다. 보드 상하좌우 끝에는 벽이 있다.뱀의 처음 시작위치는 맨 위 맨 좌측에 위치하고 처음 길이는 1이다. 뱀은 처음에는 오른쪽으로 향한다. 뱀은 매초 마다 움직이는데 아래의 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는..

[삼성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개의 줄에 나타난다...

[백준 파이썬] 2109 순회강연문제n개의 대학에서 가아연 요청을 해왔다.각 대학에서 d 일 안에 와서 강연을 해주면 p만큼의 강연료를 지불하겠다고 한다.가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 하루 최대 한 곳에서만 강연을 할 수 있다.입력첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제 시한 p값과 d값이 주어진다.출력첫번째 줄에 최대로 벌 수 있는 돈을 출력한다.풀이날짜와 가치가 주어지는데 , 이때 같은 날짜에 서로 다른  가격이 주어질 수 있다 그렇기에 이걸 고려해야 한다.나는 강연료를 저장할 배열을 하나 만들어서 그 배열의 길이가 주어진 날짜보다 작다면 배열에 추가하고 만약 주어진 날짜보다 크다면 배열을 역순으로 정렬하여 가장 마지막 값하고 현재 값하고 비교하여 현..

[파이썬 삼성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번 정점에서 연결된 모든 ..

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

[삼성 sw 파이썬] 3131. 100만 이하의 모든 소수문제1 이상 100만 이하의 도든 소수를 구하는 프로그램을 작성하시오. 출력1 이상 100만 이하의 소수를 공백을 사이에 두고 한 줄에 모두 출력한다. 풀이1부터 100만 이하의 수를 하나하나씩 소수인지 판별하도록 코드를 작성하면 시간 초과가 나는 문제이다.그렇기에 소수가 나오면 그 소수의 모든 배수를 배제하는 형식으로 코드를 작성하였다.소수가 나올 경우 기록하기 위해서 100만까지 값이 0인 리스트를 만들었고만약 이 리스트의 값이 0 이면 소수 임으로 이 값의 모든 배수를 1로 바꾸면서 제외하여 100만까지의 수를 판별하도록 만들었다.코드ans=[0]*1000001for i in range(2,1000001): if ans[i]==0: ..

[삼성 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로 나누어 버렸는지 카운트하..