17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 50000 이하의 자연수가 주어졌을 때, 해당 자연수를 최대 4개의 제곱수의 합으로 표현할 수 있다는 라그랑주의 증명을 바탕으로 한 문제이다. 뭔가 특별한 풀이법이 존재할 것 같긴 한데, 어떤 자연수 N을 다른 자연수의 제곱수의 합으로 나타낼 때 그 개수의 최댓값은 그 자신 N을 넘을 수 없고, 1부터 N까지의 답을 순차적으로 구하려했을 때 제곱 수(1, 4, 9, 16, ...)마다 1로 초기화된다는 점에서 다이나믹 프로그래밍..
7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 파이썬은 힙 라이브러리가 내장되어 있어서 따로 구현없이 편히 풀 수 있다. 다만 최대, 최소, 절댓값 힙 등은 힙에 push를 해주는 과정에서 살짝 변형만 해주면 되지만 이중 우선순위 큐는 좀 더 복잡한 코드 작성을 요구한다. 기본적인 틀은 이러하다. 1. 최대, 최소 힙을 담을 리스트를 각각 하나씩 초기화한다. 2. 값을 추가할 때 최소는 그대로, 최대는 요소에 -1을 곱해준다. 3. 값에는 튜플 형태로 (값, id) 구성해 추가해주고, 지우는 과정에서 각..
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..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/lhha0/btrQtSEN85E/B6LfnMUpQp7Apk2wvcV2Nk/img.png)
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(_ sender: UIButton) { } } 2. Ale..
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() # 입력, 빈칸의 ..
- Total
- Today
- Yesterday
- how to start without storyboard
- 알고리즘
- 정보시각화
- pyrebase
- 백준
- TIP
- SceneDelegate
- Javascript
- PS
- how to remove border of tabbarcontroller
- Python
- CSV
- BOJ
- SVG
- 백트래킹
- DFS
- 곱셈의 역원
- xcode
- D3
- HTML
- c++
- DP
- Array
- ios
- 자료구조
- 파이썬
- 보라매사옥
- 하노이탑이동순서
- CSS
- swift
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |