Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/e011.swift

Last active January 11, 2016 08:15
Show Gist options
  • Save sooop/6c698856a65cfce5b87a to your computer and use it in GitHub Desktop.
Save sooop/6c698856a65cfce5b87a to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler on Swift # 001 (011 ~ 020)
Raw
e011.swift
/*
아래와 같은 20×20 격자가 있습니다.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.
그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까?*/
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
let grid = [08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08, 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00, 81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65, 52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91, 22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80, 24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50, 32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70, 67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21, 24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72, 21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95, 78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92, 16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57, 86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58, 19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40, 04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66, 88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69, 04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36, 20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16, 20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54, 01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]
let gridSize = 20
timeit{
func getMaxSumAt(pos:Int) -> Int {
let sum_h = pos % gridSize > (gridSize - 4) ? 0 : grid[pos..<(pos+4)].reduce(1, combine:*)
let sum_v = pos / gridSize > (gridSize - 4) ? 0 : Array(0..<4).map{return grid[pos+(20*$0)]}.reduce(1, combine:*)
let sum_s1 = pos % gridSize > (gridSize - 4) || pos / gridSize > (gridSize - 4) ? 0 : Array(0..<4).map{return grid[pos+(21*$0)]}.reduce(1, combine:*)
let sum_s2 = pos % gridSize < 3 || pos / gridSize > (gridSize - 4) ? 0 : Array(0..<4).map{return grid[pos+(19*$0)]}.reduce(1, combine:*)
return [sum_h, sum_v, sum_s1, sum_s2].reduce(0){ max($0, $1)}
}
print(Array(0..<grid.count).map(getMaxSumAt).reduce(0, combine:max))
}
// 70600674
// time: 11.1490488052368 ms
Raw
e012.swift
/*
1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
이 삼각수들의 약수를 구해봅시다.
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.
그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?*/
// Swift 2.0
import Foundation
// 시간 체크용
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
func isSquared(n:Int) -> Bool {
let o = Int(sqrt(Double(n)))
return n == o
}
func numberOfDivisors(n:Int) -> Int {
let l = Int(sqrt(Double(n)))
var k = 1
var r = 0
while k <= l {
if n % k == 0 {
r += 2
}
k += 1
}
if isSquared(n) {
r -= 1
}
return r
}
timeit {
var a = 1
let getTriN = { (n:Int) -> Int in
return n * (n + 1) / 2
}
while true {
let n = getTriN(a)
if numberOfDivisors(n) >= 500 {
print(n)
break
}
a += 1
}
}
// 76576500
// time: 620.541036128998 ms
Raw
e013.swift
/*
아래에 50자리 숫자가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
...
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
*/
/*
큰 수를 8자리씩 끊어서 계산할 수 있는 별도의 타입을 만든다.
예전에 만든 BigInt 타입은 내부에 n자리 정수 배열을 이용해서
자리를 만들었는데, 이 타입은 자리수 레벨에 대한 계수로서 각 값을 저장하고
일종의 다항식처럼 동작한다.
따라서 덧셈의 경우 같은 차수의 값끼리 더하고,
후에 해당 차수를 오버하는 값들에 대해서 올림처리만 한다.
이 방식은 배열로 처리하는 것과 비슷한 성능을 보일 수 있는데,
곱셈의 경우 다항식의 곱셈 방식을 이용할 수 있기 때문에 상당한 성능차이를 보인다.
*/
func timeit(@noescape f: () -> ()) {
let begin = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(begin)
print("time: \(elapsed) ms")
}
struct BigInt: CustomStringConvertible {
// Swift 2.0 에서는 Printable이 CustomStringConvertible로 변경됨
static let UNIT = 100000000 // 8자리씩 끊어서 이용함. 32비트에서는 4자리로.
let unit_count = 8
typealias NumberBucket = (Int, Int)
let data: [NumberBucket]
init(_ buckets: [NumberBucket]) {
data = BigInt.roundUp(buckets)
}
init(var _ intValue:Int) {
var level = 0
var temp = [NumberBucket]()
while intValue > 0 {
temp.append((intValue % BigInt.UNIT, level))
level += 1
intValue = intValue / BigInt.UNIT
}
data = temp
}
init(_ strValue:String) {
var level = 0
var temp = [NumberBucket]()
let u = Array(strValue.utf8).map{ Int($0) - 48 }
let l = u.count
for a in 0...l/unit_count {
var d = 0
for b in 0..<unit_count {
let c = l - (unit_count * a + unit_count - b - 1) - 1
if c < 0 {
continue
}
d = d * 10 + u[c]
}
temp.append((d, level))
level += 1
}
data = temp
}
var description: String {
let d = data.sort{ $0.1 > $1.1 }
return "\(d[0].0)" + d[1..<d.count].map{String(format:"%04d", $0.0)}.joinWithSeparator("")
// return "".join(d.map{String($0)})
}
static func roundUp(buckets:[NumberBucket]) -> [NumberBucket] {
let maxKey = buckets.map{ $0.1 }.reduce(buckets[0].1){ $0 > $1 ? $0 : $1 }
var result = [NumberBucket]()
var flag = 0
for k in 0...maxKey {
var s = buckets.filter{ $0.1 == k }.map{ $0.0 }.reduce(flag, combine: +)
if s >= BigInt.UNIT {
flag = s / BigInt.UNIT
s = s % BigInt.UNIT
} else {
flag = 0
}
result.append((s, k))
}
if flag > 0 {
result.append((flag, maxKey+1))
}
return result
}
static func multiplyNumberBucket(l:NumberBucket, _ r:NumberBucket) -> [NumberBucket] {
let x = l.0 * r.0
let y = l.1 + r.1
if x < BigInt.UNIT {
return [(x, y)]
}
return [(x % BigInt.UNIT, y), (x / BigInt.UNIT, y+1)]
}
func add(target:BigInt) -> BigInt {
return BigInt(data + target.data)
}
func multiply(target:BigInt) -> BigInt {
var result = [NumberBucket]()
for a in data {
for b in target.data {
result += BigInt.multiplyNumberBucket(a, b)
}
}
return BigInt(result)
}
}
func +(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.add(rhs)
}
func *(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.multiply(rhs)
}
timeit{
let s = "37107287533902102798797998220837590246510135740250\n46376937677490009712648124896970078050417018260538\n74324986199524741059474233309513058123726617309629\n91942213363574161572522430563301811072406154908250\n23067588207539346171171980310421047513778063246676\n89261670696623633820136378418383684178734361726757\n28112879812849979408065481931592621691275889832738\n44274228917432520321923589422876796487670272189318\n47451445736001306439091167216856844588711603153276\n70386486105843025439939619828917593665686757934951\n62176457141856560629502157223196586755079324193331\n64906352462741904929101432445813822663347944758178\n92575867718337217661963751590579239728245598838407\n58203565325359399008402633568948830189458628227828\n80181199384826282014278194139940567587151170094390\n35398664372827112653829987240784473053190104293586\n86515506006295864861532075273371959191420517255829\n71693888707715466499115593487603532921714970056938\n54370070576826684624621495650076471787294438377604\n53282654108756828443191190634694037855217779295145\n36123272525000296071075082563815656710885258350721\n45876576172410976447339110607218265236877223636045\n17423706905851860660448207621209813287860733969412\n81142660418086830619328460811191061556940512689692\n51934325451728388641918047049293215058642563049483\n62467221648435076201727918039944693004732956340691\n15732444386908125794514089057706229429197107928209\n55037687525678773091862540744969844508330393682126\n18336384825330154686196124348767681297534375946515\n80386287592878490201521685554828717201219257766954\n78182833757993103614740356856449095527097864797581\n16726320100436897842553539920931837441497806860984\n48403098129077791799088218795327364475675590848030\n87086987551392711854517078544161852424320693150332\n59959406895756536782107074926966537676326235447210\n69793950679652694742597709739166693763042633987085\n41052684708299085211399427365734116182760315001271\n65378607361501080857009149939512557028198746004375\n35829035317434717326932123578154982629742552737307\n94953759765105305946966067683156574377167401875275\n88902802571733229619176668713819931811048770190271\n25267680276078003013678680992525463401061632866526\n36270218540497705585629946580636237993140746255962\n24074486908231174977792365466257246923322810917141\n91430288197103288597806669760892938638285025333403\n34413065578016127815921815005561868836468420090470\n23053081172816430487623791969842487255036638784583\n11487696932154902810424020138335124462181441773470\n63783299490636259666498587618221225225512486764533\n67720186971698544312419572409913959008952310058822\n95548255300263520781532296796249481641953868218774\n76085327132285723110424803456124867697064507995236\n37774242535411291684276865538926205024910326572967\n23701913275725675285653248258265463092207058596522\n29798860272258331913126375147341994889534765745501\n18495701454879288984856827726077713721403798879715\n38298203783031473527721580348144513491373226651381\n34829543829199918180278916522431027392251122869539\n40957953066405232632538044100059654939159879593635\n29746152185502371307642255121183693803580388584903\n41698116222072977186158236678424689157993532961922\n62467957194401269043877107275048102390895523597457\n23189706772547915061505504953922979530901129967519\n86188088225875314529584099251203829009407770775672\n11306739708304724483816533873502340845647058077308\n82959174767140363198008187129011875491310547126581\n97623331044818386269515456334926366572897563400500\n42846280183517070527831839425882145521227251250327\n55121603546981200581762165212827652751691296897789\n32238195734329339946437501907836945765883352399886\n75506164965184775180738168837861091527357929701337\n62177842752192623401942399639168044983993173312731\n32924185707147349566916674687634660915035914677504\n99518671430235219628894890102423325116913619626622\n73267460800591547471830798392868535206946944540724\n76841822524674417161514036427982273348055556214818\n97142617910342598647204516893989422179826088076852\n87783646182799346313767754307809363333018982642090\n10848802521674670883215120185883543223812876952786\n71329612474782464538636993009049310363619763878039\n62184073572399794223406235393808339651327408011116\n66627891981488087797941876876144230030984490851411\n60661826293682836764744779239180335110989069790714\n85786944089552990653640447425576083659976645795096\n66024396409905389607120198219976047599490197230297\n64913982680032973156037120041377903785566085089252\n16730939319872750275468906903707539413042652315011\n94809377245048795150954100921645863754710598436791\n78639167021187492431995700641917969777599028300699\n15368713711936614952811305876380278410754449733078\n40789923115535562561142322423255033685442488917353\n44889911501440648020369068063960672322193204149535\n41503128880339536053299340368006977710650566631954\n81234880673210146739058568557934581403627822703280\n82616570773948327592232845941706525094512325230608\n22918802058777319719839450180888072429661980811197\n77158542502016545090413245809786882778948721859617\n72107838435069186155435662884062257473692284509516\n20849603980134001723930671666823555245252804609722\n53503534226472524250874054075591789781264330331690"
let ns = s.componentsSeparatedByString("\n")
let c = ns.map{BigInt($0)}.reduce(BigInt(1), combine:+)
print(c)
}
// 5537376230
// time: 0.0170680284500122 ms
Raw
e013_old.swift
/*
아래에 50자리 숫자가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
...
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
*/
/*
손으로 숫자를 덧셈하는 방법을 사용하여
뒤에서부터 한자리씩 더하고 10이 넘으면 1올려주는 방식으로
덧셈한다.
문자열을 숫자로 변환하는 부분에서 utf8 맵을 이용하여 48을 빼는 쪽이
성능이 빠르다.
*/
import Foundataion
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
extension String {
subscript(range:Range<Int>) -> String {
return self[advance(startIndex, range.startIndex)..<advance(startIndex, range.endIndex)]
}
}
func convert(s:String) -> [Int] {
// "0"의 ascii 값은 48이므로, utf8 값에서 이를 뺀다.
// character -> String -> Int를 거치는 과정에 비해 이는 약 3배 가량 빠르다.
return Array(s.utf8).map{ Int($0) - 48 }.reverse()
}
func add(s1:String, s2:String) -> String {
let n1 = convert(s1)
let n2 = convert(s2)
var resultList = [Int]()
var flag:Int = 0
let l = max(n1.count, n2.count)
for i in 0..<l {
let x = i < n1.count ? n1[i] : 0
let y = i < n2.count ? n2[i] : 0
var temp = x + y + flag
if temp > 9 {
flag = 1
temp = temp - 10
} else {
flag = 0
}
resultList.append(temp)
}
if flag > 0 {
resultList.append(flag)
}
return resultList.reverse().map{String($0)}.reduce("", combine:+)
// "".join() 보다 이게 빠르다?
}
timeit{
let s = "37107287533902102798797998220837590246510135740250\n46376937677490009712648124896970078050417018260538\n74324986199524741059474233309513058123726617309629\n91942213363574161572522430563301811072406154908250\n23067588207539346171171980310421047513778063246676\n89261670696623633820136378418383684178734361726757\n28112879812849979408065481931592621691275889832738\n44274228917432520321923589422876796487670272189318\n47451445736001306439091167216856844588711603153276\n70386486105843025439939619828917593665686757934951\n62176457141856560629502157223196586755079324193331\n64906352462741904929101432445813822663347944758178\n92575867718337217661963751590579239728245598838407\n58203565325359399008402633568948830189458628227828\n80181199384826282014278194139940567587151170094390\n35398664372827112653829987240784473053190104293586\n86515506006295864861532075273371959191420517255829\n71693888707715466499115593487603532921714970056938\n54370070576826684624621495650076471787294438377604\n53282654108756828443191190634694037855217779295145\n36123272525000296071075082563815656710885258350721\n45876576172410976447339110607218265236877223636045\n17423706905851860660448207621209813287860733969412\n81142660418086830619328460811191061556940512689692\n51934325451728388641918047049293215058642563049483\n62467221648435076201727918039944693004732956340691\n15732444386908125794514089057706229429197107928209\n55037687525678773091862540744969844508330393682126\n18336384825330154686196124348767681297534375946515\n80386287592878490201521685554828717201219257766954\n78182833757993103614740356856449095527097864797581\n16726320100436897842553539920931837441497806860984\n48403098129077791799088218795327364475675590848030\n87086987551392711854517078544161852424320693150332\n59959406895756536782107074926966537676326235447210\n69793950679652694742597709739166693763042633987085\n41052684708299085211399427365734116182760315001271\n65378607361501080857009149939512557028198746004375\n35829035317434717326932123578154982629742552737307\n94953759765105305946966067683156574377167401875275\n88902802571733229619176668713819931811048770190271\n25267680276078003013678680992525463401061632866526\n36270218540497705585629946580636237993140746255962\n24074486908231174977792365466257246923322810917141\n91430288197103288597806669760892938638285025333403\n34413065578016127815921815005561868836468420090470\n23053081172816430487623791969842487255036638784583\n11487696932154902810424020138335124462181441773470\n63783299490636259666498587618221225225512486764533\n67720186971698544312419572409913959008952310058822\n95548255300263520781532296796249481641953868218774\n76085327132285723110424803456124867697064507995236\n37774242535411291684276865538926205024910326572967\n23701913275725675285653248258265463092207058596522\n29798860272258331913126375147341994889534765745501\n18495701454879288984856827726077713721403798879715\n38298203783031473527721580348144513491373226651381\n34829543829199918180278916522431027392251122869539\n40957953066405232632538044100059654939159879593635\n29746152185502371307642255121183693803580388584903\n41698116222072977186158236678424689157993532961922\n62467957194401269043877107275048102390895523597457\n23189706772547915061505504953922979530901129967519\n86188088225875314529584099251203829009407770775672\n11306739708304724483816533873502340845647058077308\n82959174767140363198008187129011875491310547126581\n97623331044818386269515456334926366572897563400500\n42846280183517070527831839425882145521227251250327\n55121603546981200581762165212827652751691296897789\n32238195734329339946437501907836945765883352399886\n75506164965184775180738168837861091527357929701337\n62177842752192623401942399639168044983993173312731\n32924185707147349566916674687634660915035914677504\n99518671430235219628894890102423325116913619626622\n73267460800591547471830798392868535206946944540724\n76841822524674417161514036427982273348055556214818\n97142617910342598647204516893989422179826088076852\n87783646182799346313767754307809363333018982642090\n10848802521674670883215120185883543223812876952786\n71329612474782464538636993009049310363619763878039\n62184073572399794223406235393808339651327408011116\n66627891981488087797941876876144230030984490851411\n60661826293682836764744779239180335110989069790714\n85786944089552990653640447425576083659976645795096\n66024396409905389607120198219976047599490197230297\n64913982680032973156037120041377903785566085089252\n16730939319872750275468906903707539413042652315011\n94809377245048795150954100921645863754710598436791\n78639167021187492431995700641917969777599028300699\n15368713711936614952811305876380278410754449733078\n40789923115535562561142322423255033685442488917353\n44889911501440648020369068063960672322193204149535\n41503128880339536053299340368006977710650566631954\n81234880673210146739058568557934581403627822703280\n82616570773948327592232845941706525094512325230608\n22918802058777319719839450180888072429661980811197\n77158542502016545090413245809786882778948721859617\n72107838435069186155435662884062257473692284509516\n20849603980134001723930671666823555245252804609722\n53503534226472524250874054075591789781264330331690"
let ns = s.componentsSeparatedByString("\n")
let c = ns.reduce("0", combine:add)
print(c[0..<10])
}
// 5537376230
// time: 41.5390133857727 ms
// 15.9739851951599 ms
Raw
e014.swift
/*
!!! SwiftStub.com 에서 답이 나오지 않음. --> 해결함
양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.
n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)
13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.
*/
/*
부분적으로 DP를 도입하여 성능을 끌어올릴 수 있다.
n 에 대한 루트 수가 정해지면 n * 2, n * 4 ... n * 2^k 의 경우에
각각 1씩 더해진 루트수가 자동으로 나오기 때문에
메모이제이션 과정을 커스터마이징할 수 있다.
*/
import Foundation
func memoize(f:(Int) -> Int) -> (Int) -> Int {
var cache = [Int:Int]()
func inner(a:Int) -> Int {
if let r = cache[a] {
return r
}
let r = f(a)
var q = r
var n = a
while cache[n] == nil && n <= 1000000 {
cache[n] = q
n = n * 2
q = q + 1
}
return r
}
return inner
}
func h(n:Int) -> Int {
if n == 1 {
return 1
}
if n % 2 == 0 {
return h(n/2) + 1
}
return h(3*n+1) + 1
}
func timeit(@noescape f:() -> ()){
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e * 1000) ms")
}
timeit{
let a = Array(1...100_0000).map{ ($0, h($0)) }
let result = a.reduce(a[0]){ $0.1 > $1.1 ? $0 : $1 }
print(result)
}
// (837799, 525)
// time: 1217.11397171021 ms
Raw
e015.swift
/*
아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).
그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?*/
/** 40! / (20! * 20!) 의 값을 구해야 한다. 계산과정에서 overflow가 발생하게 되므로 GCD를 이용해서 적절하게
약분해야 한다.
**/
import Foundation
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
var a1 = Array(21...40)
var a2 = Array(1...20)
func gcd(a:Int, _ b:Int)->Int {
let (max, min) = a > b ? (a, b) : (b, a)
if max % min == 0 {
return min
} else {
return gcd(min, max % min)
}
}
timeit {
for i in 0..<20 {
for j in 0..<20 {
let g = gcd(a1[i], a2[j])
if g > 1 {
a1[i] = a1[i] / g
a2[j] = a2[j] / g
}
if a1[i] == 1 {
break
}
}
}
let result = a1.reduce(1, combine:*)
print(result)
}
//137846528820
//time: 0.562012195587158 ms
Raw
e016.swift
/*
2^15 = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.
2^1000의 각 자리수를 모두 더하면 얼마입니까?*/
/*
13번에서 만든 BigInt 타입을 이용하여 999회 *2를 한다.
*/
// Swift 2.0
timeit {
var a = BigInt(2)
for _ in 1...999 {
a = a * BigInt(2)
}
print(a.description.utf8.map{ Int($0) - 48 }.reduce(0, combine: +))
}
// 1366
// time: 0.456215977668762 ms
Raw
e017.swift
/*
1부터 5까지의 숫자를 영어로 쓰면 one, two, three, four, five 이고,
각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.
1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?
참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다.
예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자,
115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다.*/
import Foundation
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
let words1 = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
"eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
let words10 = ["", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
let words100 = "hundred"
let words1000 = "onethousand"
func writeNumber(n:Int) -> String {
var s = ""
var i = n
if i >= 1000 {
s = words1000 + s
i = i % 1000
}
if i >= 100 {
let t = i / 100
s = s + words1[t] + words100
i = i % 100
if i > 0 {
s = s + "and"
}
}
if i >= 20 {
s = s + words10[i / 10]
i = i % 10
}
if i >= 0 {
s = s + words1[i]
}
return s
}
timeit{
var result = 0
for i in 1...1000 {
result += writeNumber(i).characters.count
}
print(result)
}
//21124
//time: 6.98500871658325 ms
// 위 함수를 재귀적으로 변경해서 사용하는 코드는 다음과 같이 작성할 수 있다.
timeit{
let words1: [String] = ["", "one", "two", "three", "four", "five",
"six", "seven", "eight", "nine", "ten", "eleven",
"twelve", "thirteen", "fourteen", "fifteen", "sixteen",
"seventeen", "eighteen", "nineteen"]
let words10: [String] = ["", "", "twenty", "thirty", "forty", "fifty",
"sixty", "seventy", "eighty", "ninety"]
func memoize<T:Hashable, U> (body: (((T) -> U), T) -> U) -> ((T) -> U)
{
var cache = [T:U]()
var result:((T) -> U)!
result = { x in
if let r = cache[x] { return r }
let r = body(result, x)
cache[x] = r
return r
}
return result
}
let mWord:(Int) -> String = memoize{ memoized, num in
switch true {
case num < 20:
return words1[num]
case num < 100:
return words10[num / 10] + memoized(num % 10)
case num < 1000:
return memoized(num / 100) + "hundred" + (num % 100 > 0 ? "and" + memoized(num % 100) : "")
default:
return "onethousand"
}
}
let result = Array(1...1000).map{ mWord($0).utf8.count }.reduce(0, combine:+)
print(result)
}
// NSNumberFormatter는 주어진 정수를 영어단어로 바꿀 수 있다. 단 이 때는 100자리와 10자리 사이에 and가 추가되지 않으므로 이 부분을 더해주어야 한다.
timeit{
var result = 0
let formatter = NSNumberFormatter()
formatter.numberStyle = .SpellOutStyle
for i in 1...1000 {
let c = formatter.stringFromNumber(i)
if let l = c {
let cs = l.characters
let r = cs.filter{ $0 != "-" && $0 != " " }.count
result += r
if i > 99 && i % 100 > 0 {
result += 3
}
}
}
print(result)
}
// 21124
// time: 99.3939638137817 ms
Raw
e018.swift
/*다음과 같이 삼각형 모양으로 숫자를 배열했습니다.
3
7 4
2 4 6
8 5 9 3
삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다.
다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다.
하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.*/
import Foundation
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
extension Array {
subscript(row:Int, column:Int) -> Element? {
get {
if(column > row) {
return nil
}
return self[row * (row + 1) / 2 + column]
}
set(newValue) {
if(column <= row) {
self[row * (row + 1) / 2 + column] = newValue!
}
}
}
}
timeit{
let c = "75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
var numbers = (c as NSString).componentsSeparatedByString(" ").map{Int(($0 as String))!}
for row in 13.stride(to:-1, by:-1) {
for col in 0...row {
numbers[row, col] = numbers[row, col]! + max(numbers[row+1, col]!, numbers[row+1, col+1]!)
}
}
print(numbers[0,0]!)
}
//1074
//time: 1.60098075866699 ms
/* Another implementation */
extension String {
func split(sep: String) -> [String]
{
return self.characters.split{ sep.characters.contains($0) }
.map{ String($0) }
}
}
timeit{
let data = "75\n95 64\n17 47 82\n18 35 87 10\n20 04 82 47 65\n19 01 23 75 03 34\n88 02 77 73 07 63 67\n99 65 04 28 06 16 70 92\n41 41 26 56 83 40 80 70 33\n41 48 72 33 47 32 37 16 94 29\n53 71 44 65 25 43 91 52 97 51 14\n70 11 33 28 77 73 17 78 39 68 17 57\n91 71 52 38 17 14 91 43 58 50 27 29 48\n63 66 04 68 89 53 67 30 73 16 69 87 40 31\n04 62 98 27 23 09 70 98 73 93 38 53 60 04 23\n"
let lines = Array(data.split("\n").map{
$0.split(" ").map{ Int($0)! }
}.reverse())
var b: [Int] = lines[0]
for i in 1..<lines.count {
b = zip(b, b.dropFirst()).map(max)
let a = lines[i]
b = zip(a, b).map(+)
}
print(b[0])
}
// 1074
// time: 2.655029296875 ms
Raw
e019.swift
/*다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).
1900년 1월 1일은 월요일이다.
4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 31일까지 있다.
2월은 28일이지만, 윤년에는 29일까지 있다.
윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다
20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?*/
import Foundation
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
timeit{
let days1 = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
let days2 = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
var year=1900, month=1, day=1, weekday=1, count=0
var days:[Int]
while year < 2001 {
if year % 400 == 0 || year % 4 == 0 && year % 100 != 0 {
days = days2
} else {
days = days1
}
day += 1
weekday = (weekday + 1) % 7
if day > days[month - 1] {
month += 1
if month > 12 {
year += 1
month = 1
}
day = 1
}
if year > 1900 && day == 1 && weekday == 0 {
count += 1
}
}
print(count)
}
// 171
// time: 4.07499074935913 ms
/*: 다음은 NSCalendar를 이용하셔 날짜를 계산하는 코드이다.
*/
timeit{
let cal = NSCalendar(calendarIdentifier:NSCalendarIdentifierGregorian)!
let dateFormat = NSDateFormatter()
dateFormat.dateFormat = "yyyy-MM-dd"
var startDate = dateFormat.dateFromString("1900-01-01")
var comps = NSDateComponents()
comps.year = 1900
var result = 0
while comps.year < 2001 {
startDate = NSDate(timeInterval: 60 * 60 * 24, sinceDate:startDate!)
comps = cal.components([.Year, .Day, .Weekday], fromDate:startDate!)
if comps.day == 1 && comps.weekday == 1 && comps.year > 1900 {
result += 1
}
}
print(result)
}
// 171
// time: 163.011968135834 ms
Raw
e020.swift
/*n! 이라는 표기법은 n × (n − 1) × ... × 3 × 2 × 1을 뜻합니다.
예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데,
여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.
100! 의 자리수를 모두 더하면 얼마입니까?*/
/*
13번 문제를 풀면서 새로 개발한 신규 타입을 이용하여 계산하는 경우 0.02 ms 가량 소요되면서
기존 알고리듬 대비 약 40000 배 가까운 성능향상을 보였다.
*/
import Foundation
func timeit(@noescape f: () -> ()) {
let begin = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(begin)
print("time: \(elapsed) ms")
}
struct BigInt: CustomStringConvertible {
// Swift 2.0 에서는 Printable이 CustomStringConvertible로 변경됨
static let UNIT = 100000000 // 8자리씩 끊어서 이용함. 32비트에서는 4자리로.
let unit_count = 8
typealias NumberBucket = (Int, Int)
let data: [NumberBucket]
init(_ buckets: [NumberBucket]) {
data = BigInt.roundUp(buckets)
}
init(var _ intValue:Int) {
var level = 0
var temp = [NumberBucket]()
while intValue > 0 {
temp.append((intValue % BigInt.UNIT, level))
level += 1
intValue = intValue / BigInt.UNIT
}
data = temp
}
init(_ strValue:String) {
var level = 0
var temp = [NumberBucket]()
let u = Array(strValue.utf8).map{ Int($0) - 48 }
let l = u.count
for a in 0...l/unit_count {
var d = 0
for b in 0..<unit_count {
let c = l - (unit_count * a + unit_count - b - 1) - 1
if c < 0 {
continue
}
d = d * 10 + u[c]
}
temp.append((d, level))
level += 1
}
data = temp
}
var description: String {
let d = data.sort{ $0.1 > $1.1 }
return "\(d[0].0)" + "".join(d[1..<d.count].map{String(format:"%04d", $0.0)})
// return "".join(d.map{String($0)})
}
static func roundUp(buckets:[NumberBucket]) -> [NumberBucket] {
let maxKey = buckets.map{ $0.1 }.reduce(buckets[0].1){ $0 > $1 ? $0 : $1 }
var result = [NumberBucket]()
var flag = 0
for k in 0...maxKey {
var s = buckets.filter{ $0.1 == k }.map{ $0.0 }.reduce(flag, combine: +)
if s >= BigInt.UNIT {
flag = s / BigInt.UNIT
s = s % BigInt.UNIT
} else {
flag = 0
}
result.append((s, k))
}
if flag > 0 {
result.append((flag, maxKey+1))
}
return result
}
static func multiplyNumberBucket(l:NumberBucket, _ r:NumberBucket) -> [NumberBucket] {
let x = l.0 * r.0
let y = l.1 + r.1
if x < BigInt.UNIT {
return [(x, y)]
}
return [(x % BigInt.UNIT, y), (x / BigInt.UNIT, y+1)]
}
func add(target:BigInt) -> BigInt {
return BigInt(data + target.data)
}
func multiply(target:BigInt) -> BigInt {
var result = [NumberBucket]()
for a in data {
for b in target.data {
result += BigInt.multiplyNumberBucket(a, b)
}
}
return BigInt(result)
}
}
func +(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.add(rhs)
}
func *(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.multiply(rhs)
}
extension String {
subscript(range:Range<Int>) -> String {
return self[advance(startIndex, range.startIndex)..<advance(startIndex, range.endIndex)]
}
}
timeit{
let d = Array(2...100).map{ BigInt($0) }.reduce(BigInt(1), combine:*)
let result = "\(d)".utf8.map{ Int($0) - 48}.reduce(0, combine:+)
print(result)
}
// 648
// time: 0.0199270248413086 ms
Raw
e020_old.swift
/*n! 이라는 표기법은 n × (n − 1) × ... × 3 × 2 × 1을 뜻합니다.
예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데,
여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.
100! 의 자리수를 모두 더하면 얼마입니까?
-- 큰수 덧셈 및 곱셈을 지원하는 타입을 새로 만들어서 구현함*/
import Foundation
func timeit(@noescape f:()->()) {
let startTime = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(startTime)
print("time: \(elapsed * 1000) ms")
}
struct BigInt: CustomStringConvertible {
let data:[Int]
init(str:String){
data = str.characters.map{Int(String($0))!}
}
init(arr:[Int]){
data = arr.map{ return $0 % 10 }
}
func add(to bi:BigInt) -> BigInt {
var ld:[Int], rd:[Int]
if data.count >= bi.data.count {
ld = data.reverse()
rd = bi.data.reverse()
} else {
ld = bi.data.reverse()
rd = data.reverse()
}
let iLong = ld.count
let iShort = rd.count
var temp = [Int]()
var flag:Int = 0
for (var i=0; i<iShort; i++) {
var n = flag + ld[i] + rd[i]
if n > 9 {
flag = n / 10;
n = n % 10;
} else {
flag = 0
}
temp.append(n)
}
if(iShort < iLong){
for(var i=iShort;i<iLong;i++){
var n = flag + ld[i]
if (n > 9) {
flag = n / 10
n = n % 10
} else {
flag = 0
}
temp.append(n)
}
}
if flag > 0 {
temp.append(flag)
}
return BigInt(arr:temp.reverse())
}
func multiply(to bi:BigInt)->BigInt{
let ld = data.reverse()
let rd = bi.data.reverse()
var flag:Int = 0
var temp:Array<[Int]> = []
var l = 0
for a in ld {
var midResult = [Int]()
for _ in 0..<l {
midResult.append(0)
}
l += 1
for b in rd {
var c = a * b + flag
if c > 9 {
flag = c / 10
c = c % 10
} else {
flag = 0
}
midResult.append(c)
}
if flag > 0 {
midResult.append(flag)
flag = 0
}
temp.append(midResult.reverse())
}
let result = temp.map{BigInt(arr:$0)}.reduce(BigInt(str:"0")){
return $0.add(to:$1)
}
return result
}
var description:String {
return data.map{String($0)}.reduce("", combine:+)
}
}
func +(l:BigInt, r:BigInt) -> BigInt {
return l.add(to: r)
}
func *(l:BigInt, r:BigInt) -> BigInt {
return l.multiply(to:r)
}
timeit{
let r = Array(2...100).map{return BigInt(str:String($0))}.reduce(BigInt(str:"1"), combine:*)
// println(r.description)
print(r.data.reduce(0, combine:+))
}
//648
//time: 811.259031295776 ms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment