25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 백준 단계별로 풀어보기 문제가 업데이트되면서 누적합 카테고리에 새롭게 추가된 Gold 5 난이도의 누적합 문제이다. 앞 선 문제인 1018 - 체스판 다시 칠하기의 브루트 포스 알고리즘과 2차원 배열의 누적합 DP를 활용하면 무난하게 AC를 받을 수 있다. 다만 반복문을 작성할 때에는 최대한 한 반복문 안에 여러 연산을 실행할 수 있게 코드를 짜주는 것이 좋다. 해당 예제 코드보다 더 효율적인 코드가 가능해 보이기도 하다. # 빠른 입출력 import sys input = sys.stdin.readlin..

11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비트마스크는 특정 알고리즘이 아닌, 이진수와 비트 연산자를 활용한 효율적인 연산 테크닉이다. 백준의 11723번 집합 문제는 비트마스킹을 활용한 대표적인 문제로, 비트마스크 기법을 직접 설명하기보단 해당 문제의 예제를 하나씩 해결해보며 정리해본다. 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. - add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. - remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 방해물을 피해 목표 지점까지 가는 가장 빠른 방법을 찾는 문제이다. DFS로 구현했을 때 시간 초과, 이어서 BFS로 구현했을 때에도 큐의 앞에서 요소를 하나씩 빼가며 탐색하는 방법이 아니라 큐를 통째로 탐색 후 새롭게 추가된 큐로 대체하는 방법을 사용했더니 역시 시간 초과가 나왔다. 결국 최초로 방문하는 지점에 인덱스를 저장하는 방식으로 구현, AC를 받았다. # 빠른 입출력, deque 채택 import sys from collections import deque input = sys.st..

UIAlertController를 활용하면 단순히 확인, 설정, 취소만 할 수 있는 게 아니라 UIPickerView나 UIDatePicker 등을 활용하여 좀 더 풍부한 알림창을 띄울 수 있습니다.  1. xcode 파일을 생성하고 UILabel, UIButton를 추가, 해당 ViewController에 연결해줍니다. class ViewController: UIViewController { // 화면에 띄울 라벨 의미 @IBOutlet weak var label: UILabel! override func viewDidLoad() { super.viewDidLoad() } // Alert을 띄워줄 버튼 의미 @IBAction func button(..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 좀 더 응용된 백트래킹 문제이다. N-Queen처럼 한가지 함수를 더 활용하여 모음 1개, 자음 2개를 만족하지 않으면 뱉어내는 방식으로 구현하려다가, 함수 속에 추가 변수를 넣어 모음과 자음의 개수를 카운트, 그리고 만족하지 않으면 추가하지 않는 방식으로 구현하였다. L, C = map(int ,input().split()) alpha = list(map(str, input().split())) alpha.sort() visit = [False] * C ans = ..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 단계별로 풀기에서 퇴각검색 카테고리에 속해 있는, N - Queen 다음으로 나오는 문제이다. N - Queen 문제를 완벽히 익히고 나면 구현하는 데에 어려움이 없겠지만, 파이썬은 요구 시간이 좀 짜서 빠른 입출력과 3중 반복문을 한 개의 반복문으로 줄이는 등 여러 노력 끝에 AC를 받아낼 수 있었다. import sys # 스도쿠 판과 아직 채워지지 않은 칸의 좌표를 담을 리스트 sodoku = list() blank = list() # 입력, 빈칸의 ..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 퇴각 검색 알고리즘을 다룰 때 대표적으로 등장하는 문제다. 2차원 배열이 아닌 인덱스를 행, 요소를 열로 사용하는 1차원 배열을 활용하고, PyPy3로 제출해야만 시간초과 없이 AC를 받을 수 있다. n = int(input()) # 체스판, 0은 아직 놓이지 않음을 의미 map = [0] * n ans = 0 # 퀸을 놓을 수 있는지 판단하는 함수 def is_satisfy(x): for i in range(x): # 같은 열에 놓였는지, 대각선에 놓였는지(-> 절댓값으로 판..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 동적 계획법으로 구현할 수 있는 대표적인 문제인 냅색 문제이다. 각 물건을 분할하여 담을 수 있는 배낭 문제는 단순히 가치의 비율을 계산하여 최대부터 넣는 그리디 알고리즘으로 구현할 수 있지만, 분할할 수 없다면 이와 같이 동적 계획법, 혹은 백트래킹으로 구현해야 한다. 해당 포스팅은 동적 계획법으로 구현했으며, 기회가 된다면 백트래킹 방식도 작성해보려 한다. 1. 2차원 배열, Bottom Up ..