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 ..
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 ..
1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m www.acmicpc.net 긴 문자열 속에서 특정 문자열을 찾아내는 알고리즘이다. Knuth Morris Pratt의 앞글자를 따왔으며, 1번부터 특정 문자열의 길이만큼 접근하는 일반적인 탐색법은 시간 복잡도가 O((n-m)n)이지만, KMP 알고리즘을 활용하면 O(n + m)의 복잡도로 시간을 단축시킬 수 있다. 1. 파이 테이블 생성 사실 KMP 알고리즘은 특정 문자열에 한 번, 그리고 이를 통해 만들어진 파이 테이블을 바탕으로 전체 문자열에 한 번 적용하여 총 두 번 쓰인다. ..
10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 좀 더 클린한 코드로 리팩토링이 필요해보이나, List와 DFS 개념을 활용하여 해결하였다. 방문 배열을 만들어주고, 정상인의 경우와 적녹색약인 경우 각각의 함수를 정의하지 않고, 정상인일 경우를 해결한 후에 적색을 녹색으로 변경하여 다시 한번 깊이 우선 탐색을 돌려주었다. import sys sys.setrecursionlimit(10 ** 9) n = int(input()) arr = list() for _ in range(n): arr.append(l..
1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다. 회전하는 큐 구현 struct Queue { var left = [Int]() var right = [Int]() var count: Int { left.count + right.count } var isEmpty: Bool ..
Swift같은 개발 언어 중에는 힙, 큐, 덱같이 기본적으로 다른 언어에서 제공해주는 라이브러리가 따로 있지 않다. 따라서 직접 구현해줘야 한다. 알아야 될 것 1. 완전 이진트리로 부모 노드를 탐색하려면, 시작 인덱스를 1부터 시작해야 한다. 2. 힙은 우선순위 큐를 위한 자료형이다. 3. 우선순위 큐의 목적은 값을 추가할 때 부모 노드에 최댓값 or 최솟값을 넣기 위함이다. 4. 따라서 입, 출력을 할 때만 연산이 수행되고, 전체 힙의 값을 확인하면 오름차순이나 내림차순으로 정렬되지 않을 수 있다. struct Heap { var heap: Array = [] // 초기화 1. 아무 것도 넣지 않을 때 init() { } // 초기화 2. 시작부터 넣을 때 init(_ data: [Int]) { he..
- Total
- Today
- Yesterday
- Javascript
- 백트래킹
- SVG
- CSS
- CSV
- DFS
- how to start without storyboard
- HTML
- DP
- PS
- Array
- Python
- TIP
- D3
- pyrebase
- BOJ
- 백준
- 곱셈의 역원
- swift
- how to remove border of tabbarcontroller
- 파이썬
- xcode
- c++
- 보라매사옥
- 알고리즘
- 정보시각화
- ios
- 하노이탑이동순서
- 자료구조
- SceneDelegate
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |