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..
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): # 같은 열에 놓였는지, 대각선에 놓였는지(-> 절댓값으로 판..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bkUnCB/btrNoEo88fy/4eUsdoiEWggOLjFV1Lbkfk/img.png)
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 ..
16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 주어진 A값의 뒤에 1을 붙이거나 A를 2배하여 B로 도달하게 만드는 연산 횟수의 최솟값을 구하는 문제다. 요새 동적 계획법 연습을 많이 하기도 했고, 최근 푼 문제인 25418 - 정수 a를 k로 만들기가 동적 계획법으로 해결할 수 있는데, 이 문제와 결이 비슷하다고 생각하여 접근하였다가 메모리 초과가 나왔다. 그도 그럴 것이 B의 최댓값이 10^9 이므로 배열에 담기엔 너무 큰 수이긴 했다. (+ 동적 계획법은 배열에 일부 최적해를 계산해서 담는 방식인데, 작성한 코드를 보니 최적해를 계산한다기보단 그저 값을 할당하는 과정일 뿐이였다.) 1. DP let input = readLine..
17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 배열에서 자기 자신보다 오른쪽에 있는 가장 가까운 큰 수를 찾는 문제이다. 처음 구현한 방법은 이중 for문을 활용하였으나, 배열의 크기가 클 땐 O(n^2) 의 시간복잡도를 감당할 수 없어 시간초과가 나왔다. 실패 코드 import Foundation let n = Int(readLine()!)! var numbers = readLine()!.split { $0 == " " }.map { Int(String($0))! } var result : [Int] = [] for ..
- Total
- Today
- Yesterday
- 파이썬
- 곱셈의 역원
- HTML
- 보라매사옥
- SceneDelegate
- Javascript
- 백트래킹
- 알고리즘
- DP
- SVG
- 정보시각화
- 하노이탑이동순서
- Array
- 자료구조
- DFS
- pyrebase
- c++
- xcode
- CSS
- 백준
- PS
- TIP
- swift
- BOJ
- how to start without storyboard
- CSV
- ios
- D3
- Python
- how to remove border of tabbarcontroller
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |