BOJ89 백준 알고리즘 1018 (체스판 다시 칠하기) - python (재풀이) 백준 알고리즘 1018 (체스판 다시 칠하기) - python > https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net W 또는 B로 시작하는 격자 무늬 체스판 다시 칠하기! 8 x 8의 판을 이용한다는 특징이 있다. [문제 해결] 1. 최소값 _min은 8 x 8 64로 설정 2. 8 x 8의 기준이 될 좌상단 index를 기준으로 하는 i, j for문 3. (0,0)이 W라고 가정하고 틀린 경우를 cnt에 누적한다. 정반대의 경우는 64.. 2022. 6. 24. 백준 알고리즘 14888 (연산자 끼워넣기) - python (재풀이) 백준 알고리즘 14888 (연산자 끼워넣기) - python > https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백트래킹의 컨셉에 충실! 식의 계산은 앞에서부터 진행! 계산을 하면서 각 연산자 count를 -1 -> dfs 진행 -> 다시 count +1 [문제 풀이] 1. 탈출 조건 : depth == N _max와 _min을 global로 이용하여 저장 2. result를 dfs에서 계.. 2022. 6. 22. 백준 알고리즘 2580 (스도쿠) - python (재풀이) 백준 알고리즘 2580 (스도쿠) - python > https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 가로, 세로, 3x3 사각형에 모두 1~9의 숫자 하나씩 있는 스도쿠! [문제 풀이] 1. dfs를 진행 2. _map 에 0이 있는지 체크하면서, 출력해도 되는지의 flag와 0의 좌표를 return 3. flag == True이면 _map 출력 이 때, return만 해주면 답이 여러 번 출력될 수 있으므로 완전히 종료 : exit(0) (.. 2022. 6. 17. 백준 알고리즘 1931 (회의실 배정) - python 백준 알고리즘 1931 (회의실 배정) - python > https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디! 회의실 (시작, 끝) 시간이 주어지는 경우 최대 값 구하기 여기서 잘 생각해야 하는 부분은 "회의의 시작시간과 끝나는 시간이 같을 수도 있다." 이 문장을 "일단 시작을 해야지 그 동시에 끝날 수도 있다." 라는 조건으로 해석했다. 그렇기 때문에, 시작 시간 기준으로 먼저 정렬을 한다. [문제 풀이] 1. 받아온 리스트 times를 시작 시간 기준으로 먼저 정렬 2. 정렬된 times를 한 번 더 종료 시간 기준으로 정렬 3. 회의실이 사용 가능.. 2022. 6. 12. 백준 알고리즘 2630 (색종이 만들기) - python 백준 알고리즘 2630 (색종이 만들기) - python > https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 4-분할 정복! 4분할을 하여 한 사분면이 모두 같은 색일 때까지 분할하여 카운트하는 방법 [문제 풀이] 1. 기준 색을 받는다. 2. 맵을 탐색하며 모두 같은 색인지를 확인한다. 3. 모두 같지 않다면 4분할을 재귀적으로 시도한다. 4. 모두 같은 색인 경우는 이중 for문 이후의 부분이다. 5. 그 때의 색.. 2022. 6. 1. 백준 알고리즘 11047 (동전 0) - python 백준 알고리즘 11047 (동전 0) - python > https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 주어지는 최소의 동전으로 조합하여 값을 맞추는 문제. 그리디하게 큰 수부터 접근하면 된다. 각 동전의 수는 무수히 많으므로 나눠서 몫을 이용한다. [문제 풀이] 1. 큰 수부터 접근하기 편하도록 배열 reverse -> 속도가 중요하다면 N-1번째부터 반대로 접근하는 것이 좋을.. 2022. 5. 30. 백준 알고리즘 15642 (N과 M(4)) - python 백준 알고리즘 15642 (N과 M(4)) - python > https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M 문제에서 같은 수 여러번 골라도 되며, 비내림차순을 만족해야한다. [문제 풀이] 1. DFS 함수 정의 (depth, i (초기값 1)) 2. depth == M 탈출 조건, tmp를 join하며 출력 3. 비내림차순은 다음 depth에서 i 이상을 지정해야함 -> for문이 i부터 시작되게 함 4. tmp에 j를 appen.. 2022. 5. 23. 백준 알고리즘 15641 (N과 M(3)) - python 백준 알고리즘 15641 (N과 M(3)) - python > https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M 문제인데 같은 수를 여러 번 골라도 된다! [문제 풀이] 1. DFS 함수 생성 2. 탈출 조건 depth == M에서 tmp를 join시켜 출력 3. 중복 체크를 하지 안하도 되니 visited 체크 X 4. for문을 돌리며 자연수를 tmp에 append 5. depth 증가시켜서 재귀시키고 백트래킹 import sys .. 2022. 5. 22. 백준 알고리즘 10815 (숫자 카드) - python 백준 알고리즘 10815 (숫자 카드) - python > https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 가지고 있는 숫자 카드를 체크하는 것이다. 결론적으로 큰 배열이 있을 때 효율적으로 비교 탐색이 가능한가를 묻는 문제. dictionary, 이진 탐색의 2가지를 이용해서 풀이했다. 속도는 역시 dictionary! python 최고! [문제 풀이 1 : dictionary] 1. 가지고 있는 cards를 모.. 2022. 5. 20. 이전 1 2 3 4 5 ··· 10 다음 728x90