본문 바로가기

알고리즘 문제풀이

 (31)
백준(boj) 2447 별 찍기 - 10(파이썬) https://www.acmicpc.net/problem/2447*** * * ***문제의 기본 패턴입니다.주어진 예제를 보시면 기본모양의 패턴들이 점점 확장하는 모양인 것을 볼 수 있습니다.이를 이용해 문제를 해결해 봅시다.함수를 만들껀데, 저런 모양들을 그리기 위해서 시작 좌표인 x, y 값과, 그릴 그림의 길이인 n을 가지고 만들어 보겠습니다.def draw(x, y, n) #시작좌표 (x,y), 그림 그릴 길이 nbase case는 n==1일 때 시작좌표에 별을 그리고 마칩니다. (x, y시작으로 (n=1)길이 만큼 그림)마지막에 모양을 출력하기 위해서 저는 문자열을 넣을 수 있는 배열을 사용했습니다.def draw(x, y, n): if n==1: #base case dohwaji[x][y]='..
백준(boj) 11729 하노이 탑 이동 순서(파이썬) https://www.acmicpc.net/problem/11729하노이의 탑 입니다. 문제의 조건은 다음과 같습니다. 1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 최소 이동으로 가는 횟수와 옮기는 과정을 구해야 합니다. 직관적으로 생각해봅시다.위와 같이 a기둥에 n개의 원판이 주어지고 이 원판들을 모두 c로 옮겨야 합니다.이 원판을 조건에 맞게 옮기려면 일단 아래 깔린 가장 큰 원판부터 c로 옮겨야 합니다.그러기 위해선 위와같이 a에 있는 n-1개의 원판을 b로 먼저 옮겨줘야겠죠? (어떻게 옮길진 아직 생각 않으셔도 됩니다. 아몰랑)그 다음 a에 남은 가장 큰 원판을 c에 옮겨주고이제 남은 b에 남은 모든 원판들을 c로..
백준(boj) 10870_피보나치 수5 (파이썬) https://www.acmicpc.net/problem/10870base case는 f(0)=0, f(1)=1 이고,식은 f(n) = f(n-1) + f(n-2) 으로 문제에 친절하게 나와있다. 이를 코드로 옮기면 다음과 같다. python3def fib(n): if n
백준(boj) 17140_이차원 배열과 연산 (파이썬, c++) https://www.acmicpc.net/problem/17140풀이#3*3배열 A #R: 모든 행에 대해서 행의 개수 >= 열의개수 일때 적용 #C: 모든 열에 대해서 행의개수 cnt에 입력하면서 a[][]를 0으로 바꿔줌으로써 해결, 정렬시 0무시는 a[][]가 0이 아닌지 확인하여 해결#A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간 #저 규칙대로 구해서 A[r][c]==k면 종료, 시간출력, 100넘어가면 -1출력 python3from sys import* from collections import* input = stdin.readline def solve(): global n,m for t in range(101): if a[r-1][c-1] == k: return t if n >=..
백준(boj) 17142 연구소3 (파이썬, c++) https://www.acmicpc.net/problem/17142풀이바이러스가 있는 곳을 리스트에 표시해두고, 완전 탐색 하였다. 시작할 때 빈칸들을 세어두고, 확산할 때마다 cnt 변수를 1씩 늘려줘서 cnt가 빈칸의 개수가 되면 바이러스가 다 퍼진 것으로 return 해주었다. BFS를 사용하여 퍼지는 속도를 균일하게 만들어, 마지막에 퍼진 것이 제일 늦게 퍼진 것이다. python3from sys import* from collections import* input = stdin.readline def cal(): q=deque() cnt=0 visit=[[0]*n for _ in range(n)] for x, y in temp: q.append((0,x,y)) #시간, 좌표 visit[x][y]..
백준(boj) 17144_미세먼지 안녕! (파이썬, c++) https://www.acmicpc.net/problem/17144풀이크게 보면 확산, 공기청정기 작동으로 나뉘어진다. 1. 확산4방향을 확인하며 공기청정기, 범위 밖이 아니면 먼지/5 만큼의 양을 새로운 배열에 추가해주고(중간에 값을 바꿔버리면 안되므로 새로운 배열을 하나 만들어놓고 나중에 처리) , 개수를 세어준다. 4방향을 확인 했으면, 먼지의 양에서 (먼지/5)*퍼진개수를 빼준다.(Arc -= (Arc/5)*cnt) 2. 공기청정기 작동공기를 한칸씩 이동시킨다. 공기청정기의 윗부분은 RULD방향으로 진행하고, 아랫부분은 RDLU방향으로 진행하므로 벽에 닿으면 방향이 바뀌게, 공기청정기에 닿으면 끝나게 구현해주면 된다. c++로 구현한 move()함수를 보면, dd를 URDL로 만들어놔서 시작d를 ..
백준(boj) 16234_인구 이동 (파이썬, c++) https://www.acmicpc.net/problem/16234풀이인구이동이 일어나지 않을 때까지 반복하는 문제이다.인구이동이란 인접한 곳의 인구 차이가 L 이상, R 이하이면 국경선이 열리는데, 국경선이 열린 곳은 동맹국이 되고, 동맹국들은 (동맹국 총인구수/동맹국의 수)로 인구가 변한다.어느 곳을 시작점으로 잡아도 조건상 동맹국이 되는 곳들은 같으므로, 2중 포문으로 모든 곳을 확인하는데, 방문하지 않은 곳들(아직 동맹국이 안된or안될 곳들)만 순서대로 확인한다. 방문하지 않은 곳은 4방향 탐색을 하면서 L
백준(boj) 14890_경사로 (파이썬, c++) https://www.acmicpc.net/problem/14890풀이가로방향, 세로방향 총 2N개의 방향을 돌면서 잘 통과하면 1, 통과하지 못하면 0을 반환해서 개수를 세어준다. 변수 k를 이용했는데, k는 앞쪽에 경사로를 만들 수 있는 개수라고 생각하면 쉽다. 만약 길을 가다가 뒤에가 더 클 때(diff==1), k가 l보다 작다면 앞쪽에 만들 수 있는 개수가 l보다 작으므로 경사로 건설이 불가능하다. 따라서 0을 반환한다. 그렇지 않다면, 새로운 높이에 올라왔으므로 k를 다시 초기화 해준다. 만약 뒤에가 더 작다면(diff==-1) 일단 k가 0보다 크거나 같은지 확인해주어서 이 곳에 만들 수 있는지를 살펴본다. 만약 이 곳에 경사로를 놓을 수 있다면, k를 -l의 길이로 만들어준다(경사로 만들 ..

티스토리툴바