Algorithm

[DFS] 양과 늑대 (python) - 카카오

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 DFS/BFS 둘 다 풀이 가능한데, 설명이 길어서 여기서는 DFS만 쓰고 BFS는 따로 포스팅했다. DFS는 연산자 끼워넣기 문제와 비슷하게 접근할 수 있다. 1. DFS 풀이 # 2. 재귀함수 def dfs(x,y): # 3. 현재 노드에서 연결된 노드들 for 다음 노드 in 연결된 노드들: # 4. 조건 만족 시 바로 끝까지 실행 재귀함수 if 문제 조건: dfs(nx,ny) #..

[누적합] 광고 삽입 (python) - 카카오

문제 풀이 💡 1. 시간을 전부 초로 바꿔서 배열로 풀이하기 💡 2. 누적합 최종 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 💡Idea! 1. 시간을 전부 초로 바꿔서 배열로 풀이하기 2. 누적합 💡 1. 시간을 전부 초로 바꿔서 배열로 풀이하기 시간, 분을 전부 초로 바꾸어 매초마다의 시청자수를 기록하는 배열을 만든다. 이를 통해 구간별 누적합을 구할 예정! 💡 2. 누적합 adv_time 구간 동안의 합의 최대를 구하기..

[BFS/DFS] 거리두기 확인하기 (python) - 카카오

https://programmers.co.kr/learn/courses/30/lessons/81302#fnref1 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr BFS로 풀이 이 문제는 두 가지 부분을 기본 BFS에서 추가?주의해주면 된다..

[BFS] 단어 변환 (python) - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr BFS 문제인데, '단어 하나만 다를 경우 = 연결된 간선이 존재한다'로 해석해서 풀면 된다! 기본 BFS 로직이 아래와 같다면, 여기서 '3번 이 노드에서 연결된 다른 노드들' 과정이 복잡한 문제로 볼 수 있다. # 1. 초기화 q = deque([start]) # 2. q가 빌 때까지 반복 while q: now =..

[DFS] 타겟 넘버 (python) - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 연산자 끼워 넣기 와 비슷한 문제! -> DFS로 풀고, 연산자와 피연산자의 index값을 매개변수로 잘 넘겨주어야함 def solution(numbers, target): n= len(numbers) result = 0 def dfs(tmp, index): nonlocal result if index == n: if tmp == targ..

[다익스트라] 전보 (python)

전보 - 이코테 교재 p262 문제설명 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내려면 도시 X -> Y로 가는 통로가 설치되어 있어야 한다. 어느 날 C라는 도시 C에서 위급 상황이 발생해 최대한 많은 도시로 전보를 보내야 한다. 메세지는 도시 C에서 출발해 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 정보로 주어졌을 때, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개 이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성해라. 입력조건 첫째 ..

[BFS] 경쟁적 전염 (python)

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net POINT 1. 주어진 시간 s까지 반복 2. 모든 바이러스의 순서 파악 -> 힙큐 사용 3. 번호가 낮은 종류의 바이러스부터 퍼짐 -> BFS 우선 처음 풀이는 시간 초과가 나왔다. 매 시각 바이러스의 순서를 파악하는 함수 find_virus()를 따로 만들었었는데, 바이러스를 뿌리는 함수 spread()와 만나 spread(find_virus) 하면 3차 반복문이..

[BFS] 아기상어 (python)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 이 문제는 먹을 물고기들을 탐색하는 BFS 과정을 거쳐야한다. 이때, 물고기들의 거리를 찾는 과정과 그 중 하나를 고르는 과정을 분리해서 구하자! 1. 매일 반복 -> 먹을 게 더 없을 경우 종료! 2. 현재 상어가 먹을 수 있는 물고기들의 거리 탐색 -> BFS 3. 그 중 거리가 가장 가까운 물고기 먹기! from collections import deque INF = 1e9 graph..

[BFS] 블록 이동하기 (python)

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr Point : 1. 로봇이 그래프를 탐색 (이때, 이동할 수 있는 조건을 고려해서!) 2. (n,n) 만나면 종료 이 문제는 그래프 탐색이므로 BFS로 풀이할 수 있다. 기본적인 BFS 코드는 아래와 같은 데, 이 문제는 3. 현재 노드에서 이동할 수 있는 노드들을 찾는 과정이 복잡한 경우이다. # 1. 초기화 q = deque([start]) # 2. q while q: now = q.po..