알고리즘
-
문제 풀이 1️⃣ 목표지점 2를 찾아서 위치를 저장해둡니다. 2️⃣ 1의 값들을 전부 -1로 바꿔줍니다. 3️⃣ 찾아놓은 목표지점 위치부터 시작해서 bfs 그래프 너비 탐색을 통해서 이동할 수 있는 부분들을 탐색합니다. 4️⃣ 전체 탐색하고 탐색하지 못한부분은 -1로 그대로놔둡니다. 5️⃣ arr에 저장되어있는 값을 출력형식에 맞게 출력합니다. 전체 코드 from sys import stdin as s from collections import deque s=open('input.txt','rt') # bfs 함수부분 def bfs(si,sj): q=deque() q.append((si,sj)) v[si][sj]=1 # 4방향 탐색위한 방향설정 dx=[0,1,0,-1] dy=[1,0,-1,0] while..
[백준] 14940 쉬운 최단거리 [python]문제 풀이 1️⃣ 목표지점 2를 찾아서 위치를 저장해둡니다. 2️⃣ 1의 값들을 전부 -1로 바꿔줍니다. 3️⃣ 찾아놓은 목표지점 위치부터 시작해서 bfs 그래프 너비 탐색을 통해서 이동할 수 있는 부분들을 탐색합니다. 4️⃣ 전체 탐색하고 탐색하지 못한부분은 -1로 그대로놔둡니다. 5️⃣ arr에 저장되어있는 값을 출력형식에 맞게 출력합니다. 전체 코드 from sys import stdin as s from collections import deque s=open('input.txt','rt') # bfs 함수부분 def bfs(si,sj): q=deque() q.append((si,sj)) v[si][sj]=1 # 4방향 탐색위한 방향설정 dx=[0,1,0,-1] dy=[1,0,-1,0] while..
2023.06.06 -
문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..
[백준] 15686 치킨 배달 [python]문제 풀이 1️⃣ 치킨집의 위치와 집의 위치를 미리 찾아서 리스트에 저장합니다. 2️⃣ 치킨집과의 최솟값을 찾아야하므로 변수를 max사이즈로 지정해줍니다. 3️⃣ M개수만큼의 치킨집을 골랐을 때 최솟값을 찾아야하므로 M개의 치킨집을 고르는 조합의 수를 구합니다. 4️⃣ 조합의 수를 구하기위해 브루트포스와 백트래킹 알고리즘을 사용합니다. 5️⃣ dfs 재귀를 반복하면서 조건에 충족됐을 때 집과 치킨집과의 거리를 저장합니다. 6️⃣ 저장한 치킨집과의 거리를 min함수로 저장해서 최솟값을 출력합니다. 전체 코드 from sys import stdin as s s=open('input.txt','rt') def dfs(cur,arr): global answer # arr의 길이가 M과 같으면 아래 조건문 진입 ..
2023.06.01 -
이 문제는 구현문제로 그래프 탐색과 더불어서 풀었습니다. 처음에는 미세먼지가 확산하는 부분까지는 기존 bfs문제들과 비슷해서 작성할 수 있었는데 이 문제에서는 공기청정기 윗 부분과 아랫 부분을 나눠서 한칸씩 밀려나가는 것을 구현하는 부분이 어려웠습니다. 머릿속으로는 벽에 부딪히면 방향을 전환하고 값들을 하나씩 이동시키는 형식으로 구현하면되겠다라고 생각은 드는데 막상 구현을 하자니 어디서부터 어떻게 구현해야하는지가 어려웠던 것 같습니다. R,C,T = map(int,s.readline().split()) arr = [list(map(int,s.readline().split())) for _ in range(R)] #로봇의 위치 저장하는 배열 machine=[] #미세먼지 누적 합 저장 result=0 #동..
[백준] 17144 미세먼지 안녕! [Python]이 문제는 구현문제로 그래프 탐색과 더불어서 풀었습니다. 처음에는 미세먼지가 확산하는 부분까지는 기존 bfs문제들과 비슷해서 작성할 수 있었는데 이 문제에서는 공기청정기 윗 부분과 아랫 부분을 나눠서 한칸씩 밀려나가는 것을 구현하는 부분이 어려웠습니다. 머릿속으로는 벽에 부딪히면 방향을 전환하고 값들을 하나씩 이동시키는 형식으로 구현하면되겠다라고 생각은 드는데 막상 구현을 하자니 어디서부터 어떻게 구현해야하는지가 어려웠던 것 같습니다. R,C,T = map(int,s.readline().split()) arr = [list(map(int,s.readline().split())) for _ in range(R)] #로봇의 위치 저장하는 배열 machine=[] #미세먼지 누적 합 저장 result=0 #동..
2023.05.18 -
문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..
[백준] 14502 연구소 [Python]문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..
2023.05.11 -
이 문제를 처음 봤을 때 지문을 잘못이해해서 왼쪽으로90도 회전하고 이동하고를 같은 자리를 무한 반복하는 줄 알았다.. 질문 게시판을 가보니 나와 같은 문제를 갖고 있는 사람들이 많아서 질문을 읽고 이해를 하게되었습니다. 우선 문제의 풀이방법을 생각해보면 dfs,bfs 방식으로 접근할 수 있고 제가 풀이한 방식은 dfs의 방식을 사용했습니다. N,M = map(int,s.readline().split()) r,c,d = map(int,s.readline().split()) cnt=0 #북동남서순서 dx=[-1,0,1,0] dy=[0,1,0,-1] arr = [list(map(int,s.readline().split())) for _ in range(N)] dfs(r,c,d) 처음 주어진 방향의 값이(d)..
[백준] 14503 로봇 청소기 [Python]이 문제를 처음 봤을 때 지문을 잘못이해해서 왼쪽으로90도 회전하고 이동하고를 같은 자리를 무한 반복하는 줄 알았다.. 질문 게시판을 가보니 나와 같은 문제를 갖고 있는 사람들이 많아서 질문을 읽고 이해를 하게되었습니다. 우선 문제의 풀이방법을 생각해보면 dfs,bfs 방식으로 접근할 수 있고 제가 풀이한 방식은 dfs의 방식을 사용했습니다. N,M = map(int,s.readline().split()) r,c,d = map(int,s.readline().split()) cnt=0 #북동남서순서 dx=[-1,0,1,0] dy=[0,1,0,-1] arr = [list(map(int,s.readline().split())) for _ in range(N)] dfs(r,c,d) 처음 주어진 방향의 값이(d)..
2023.05.10 -
💡그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다. 그리디 알고리즘 예시 문제 - 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. - 입력 : N = 1260 - 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저..
[알고리즘] 그리디 알고리즘💡그리디 알고리즘이란? 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다. 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다. 그리디 알고리즘 예시 문제 - 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. - 입력 : N = 1260 - 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저..
2023.04.28 -
💡다이나믹 프로그래밍(DP)란? - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법입니다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. - 다이나믹 프로그맹의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성됩니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 다이나믹 프로그래밍 예시 - 피보나치 수열 n번째 피보나치 수를 f(n)라고 할 ..
[알고리즘] 다이나믹 프로그래밍(DP)💡다이나믹 프로그래밍(DP)란? - 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법입니다. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. - 다이나믹 프로그맹의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성됩니다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 다이나믹 프로그래밍 예시 - 피보나치 수열 n번째 피보나치 수를 f(n)라고 할 ..
2023.04.27 -
이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을 깨달았습니다.. bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다. #N,K의 입력을 받음 N,K = map(int,s.readline().split()) #각 행을 graph 이중배열에 저장 graph=[list(map(int,s.readline().split()))for _ in range(N)] # S,X,Y의 값 입력 받음 S,X,Y = map(int,s.re..
[백준] 18405 경쟁적 전염[Python]이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을 깨달았습니다.. bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다. #N,K의 입력을 받음 N,K = map(int,s.readline().split()) #각 행을 graph 이중배열에 저장 graph=[list(map(int,s.readline().split()))for _ in range(N)] # S,X,Y의 값 입력 받음 S,X,Y = map(int,s.re..
2023.04.27