알고리즘

[Python/파이썬 11057 백준] 오르막 수 (다이나믹 프로그래밍)

www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 10844 쉬운 계단수 문제랑 굉장히 유사한 문제입니다.. 유사한 문제 풀어보면 쉽게 풀리네용... 주의할 점은 첫번째 0인 숫자가 들어갈 수 있다는거구, 오름차순 숫자 갯수를 찾아야합니다. 또한 이차원 리스트 사용 숫자를 일일히 구하다보면 공통점이 있는데 마지막 수가 0일 경우 다음 숫자는 1~9가 가능하고 1일 경우 2~9 2일 경우 3~9 . . . 9는 다음 숫자..

[운영체제 6] 스케줄링 알고리즘

* 배치 처리 시스템 : 자동으로 다음 응용 프로그램이 실행되게 하는 것 ( 큐 구조) 큐(Queue) : First In First Out 단점 : A 프로그램이 실행이 시간이 너무 오래걸려서, B 프로그램이 실행하는데 시간을 많이 기다려야한다. -> 단점을 극복하고자 멀티 프로그래밍 / 시분할 시스템이 나왔다. * 시분할 시스템 (다중 사용자 지원, 응답시간 최소화) - > 다중 사용자 지원을 위해 컴퓨터 응답시간을 최소화 하는 시스템 Application 1 Application 2 3 ↓ 1 2 3 1 2 1 2 2 2 * 멀티 태스킹 -> 단일 CPU,여러 응용 프로그램이 동시에 실행되는 것처럼 보이도록 하는 시스템 ex ) MP3음악을 들으며, 문서작성을 하게 되면 MP3 | 문서 | MP3 ..

[Python/파이썬 15684 백준] 사다리 조작

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net check 함수는 세로선이 자기 위치 맞게 가면 True 아니면 False bf 함수는 재귀로 다리를 3개까지만 이어주면서 true값 비교 주석 참고하세용 import sys input=sys.stdin.readline n,m,h=map(int,input().split()) if m==0: print(0) sys.exit() bridge=[[False]*n for _ in range(h)] for _ in r..

[알고리즘] 다이나믹 프로그래밍 (DP) 이해하기

다이나믹 프로그래밍(동적계획법)이란? - 큰 문제를 풀기 위해서 작은 문제를 풀어 나가는 방식이며, 작은 문제에서 반복이 없다는 것이 특징입니다. -> 분할 정복 기법과 다른 결정적인 차이 또한 하나의 문제를 단 한 번만 푸는 알고리즘 다이나믹 프로그래밍 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은문제에서 구한 정답은 이것을 포함한 큰 문제에서도 동일한 정답이다. 이러한 조건때문에 시간 복잡도를 훨씬 줄일 수 있습니다!!! 어떻게 구현할까요?? 메모이제이션(Memoization) 기법 활용 말 그대로 메모하는 기법입니다. 작은 문제 계산된 결과값을 배열을 사용해서 저장하고, 나중에 큰 문제에서 동일한 계산을 요구할 때 배열의 저장된 값을 불러오는 것입니다. -> dp 리스트 초기화해서 안..

[Python/파이썬 백준 13460] 구슬탈출2 (BFS)

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬 탈출 2 분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 512 MB 45509 13190 6937 25.692% 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N,..

[Python/파이썬 백준 2468] 안전 영역(BFS)

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 check 해주는 그래프를 3중 리스트로 사용했는데 z 범위를 가장 큰 높이로 받아서 3중 리스트를 선언해주었습니다. z를 0~height-1 까지 범위를 잡아서 BFS를 돌렸는데 z범위가 엄청 헷갈렸...(0을 포함 안하고 돌렸었는데 틀렸다해서 넣었더니 성공... 안내릴 경우도 포함해주는건가...) cnt로 안전 영역을 세주고 최대 영역 값을 max로 판단했더니 성공~ #안전 영역 # z를 0~ 제일 큰 높이까..

[Python/파이썬 백준 5104] 스타트링크(BFS)

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 일차원 BFS 문제입니다. S,G 를 start, end값으로 선언했으며 U,D 을 dx 값에 +U 와 , -D 를 넣어줬습니다 check 값을 비교해서 queue에 삽입되면 +1씩 시켜줬으며 check[end]를 반환시켜줘서 출력시켰어용~~ # 스타트링크 # 일차원 BFS 문제이며, U,D 을 nx 값에 넣어줘서 # check 해당 값 출력 from collections import deque import sys i..

[Python/파이썬 백준 2206] 벽 부수고 이동하기(BFS)

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 처음 문제를 봤을 때 이중포문 돌려서 min 값 비교해가면서 풀어봤는데 시간초과가 났습니당! 고래서 검색 결과 check 리스트를 삼중 리스트를 사용해서 z값을 비교해가면서 부술경우 안부술경우를 나누어 풀이 # 이중포문 돌려서 각각 0으로 바꿔서 min값 비교 # 해봤다가 시간초과 돼서 보니까 3차원 쓰라고한당 from collections import deque import sy..

[Python/파이썬 백준 1012] 유기농 배추(BFS)

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 #배추 벌레 문제 bfs 돌때마다 증가 시켜주면 되는데 x,y 신경잘써서 from collections import deque import sys input=sys.stdin.readline T=int(input()) dx=[1,-1,0,0] dy=[0,0,-1,1] for i in range(T): m,n,k=map(int,input().split()) graph=[[0]*m for _ in range(n)] che..