아리의 개발 일상

Two Pointer 알고리즘 (투 포인터 알고리즘)개념투 포인터 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 효율적으로 목표(문제)를 해결하는 기법으로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾을 때 사용하면 시간 복잡도를 줄이는 매우 좋다.로직두 개의 포인터를 사용하여 배열을 탐색보통 하나를 왼쪽(배열 인덱스0)에서 시작, 다른 하나는  오른쪽에서 시작하여  특정 조건을 만족하는 경우를 찾는다.문제 유형에따라 오른쪽 시작 지점이 0부터 시작할 수도 있고 배열 인덱스의 최대치에서부터 시작할 수 있다.대표 유형두 수 의 합배열이 정렬된 상태에서 투 포인터를 사용하여 두 수의 합이 특정 값이 되는지 찾는 문제로직왼쪽 인덱스 left를 0으로, 오른쪽 인덱스 right를 배열의 끝으로 설정..

[삼성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배열을 내림차순으로..