본문 바로가기

전체 글

(34)
백준(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
재귀(recursion) 재귀(recursion) '재귀'란 자기 자신을 다시 호출하여 자기 자신을 재참조하는 방법이다.왜때문인지 나의 학식시절 교수님들께서는 재귀란 말을 안좋아하고 '되부름', '순환'으로 바꿔부르거나 그냥 'recursion'으로 부르곤 하셨다. 나는 청개구리이므로 재귀라 불렀었다. 재귀의 간단한 예를들면 아래와 같다. def sum(n): if n==0: return 0 #base case return n+sum(n-1) n=int(input()) print(sum(n))n이라는 값을 입력받아 sum()이라는 함수를 호출하는 코드이다. sum()함수를 살펴보면 n이 0일때 0을 반환하고, 그렇지 않다면 n+sum(n-1)을 반환하여 sum()을 다시 호출하게 된다. 이와같은 함수를 재귀함수 라고 한다. 이 ..
백준(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