새싹프로그래머의 이야기

문제: cache 사이즈와 문자열 리스트가 주어졌을 때, 캐시 교체에 드는 총 실행시간을 구하는 문제입니다.

풀이 코드:

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

문제 풀이:

문제 풀이의 핵심은 maxlen 옵션을 활용한 deque 사용입니다.

문제에서 캐시 교체 알고리즘은 LRU 알고리즘을 활용한다고 명시해주었습니다.

예를 들면, 길이가 3인 ['a', 'b', 'c'] 라는 리스트에 'd' 라는 원소가 추가된다면 'a'라는 원소가 없어지고 'd'가 추가되는 것입니다.

deque의 maxlen 옵션을 활용한다면 위와 같이 동일하게 동작하는 deque를 구현할 수 있습니다.

from collections import deque

q = deque(maxlen=3)

for i in range(6):
    q.append(i)
    print(q)

위와 같은 코드가 있을 때, 데크에 담기는 원소를 확인해보면 다음과 같습니다.

따라서, 문제 풀이는 maxlen이 정의된 deque를 통해 풀어주었습니다. 

def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

maxlen이 설정된 deque에 append 할 경우, LRU 알고리즘과 맞게 동작하므로 원소가 있는지 여부만 판단하여 실행시간을 구해주었습니다.(원소가 있을 경우, 'cache hit'. 없을 경우, 'cache miss'.)

* 해당 문제는 https://www.youtube.com/watch?v=orf9ailzXvI 을 듣고 작성하였습니다.

문제: 문자열이 주어졌을 때, 문제에서 주어진 방식으로 압축 시킬 수 있는 모든 방법중에서 가장 짧은 문자열의 길이를 구하는 문제입니다.

풀이 코드:

def solution(s):
    answer = 0
    length = len(s)
    lst = [[] for _ in range((length - 1) // 2 + 2)]
    string = ''
    l = 1

    while l <= (length - 1) // 2 + 1:
        strlst = [s[i:i + l] for i in range(0, len(s), l)]  # 1부터 (length - 1) // 2 + 1까지 길이에 맞춰 문자열 쪼개기
        pos = strlst[0]
        cnt = 0
        for i in range(len(strlst)):
            if strlst[i] == pos:    # 앞선 문자열과 동일한 문자열이 들어온다면 갯수를 count하며 추가
                cnt += 1
                string += strlst[i]
            else:
                if cnt > 1:     # 앞선 문자열과 다른 문자열이 들어온다면 문자열 압축 및 새로운 문자열 추가
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))
                cnt = 1
                string += strlst[i]
                pos = strlst[i]

            if i == len(strlst) - 1:    # 동일한 문자가 반복되며 종료될 경우에 대한 처리 진행
                if cnt > 1:
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))

        lst[l] = list(string)
        string = ''
        cnt = 1
        l += 1
    answer = 1001

    for i in lst[1:]:
        if len(i) < answer:
            answer = len(i)

    return answer

풀이 방법:

• 첫번째는 문자열이 있을 때, 앞에서 부터 문자열 길이의 반 이상으로 쪼갠다면 중복되는 것이 생길 수 없으므로 범위를 (문자열 길이 -1)//2 +1 로 정의했습니다.

-> 'abcdefg' 를 'abcde' 'fg'로 쪼갠다면 앞의 문자열에 중복되는 문자열이 뒤에 나올 수 없습니다.

• 두번째로는, 쪼개진 문자열을 앞에서 부터 탐색하면서 다른 문자열이 나올 경우 앞선 문자열에 대한 압축과 동시에 새로 들어온 문자열을 추가해주었습니다.
• 마지막으로,동일한 문자('ababccc'에서 'c') 가 반복되며 종료될 경우를 위해 마지막 index에 대하여 처리하는 코드를 추가해주었습니다.

문제: 주어진 점수를 계산하여 성격유형 검사 결과 출력하기.

풀이 코드:

def solution(survey, choices):
    answer = ''
    dic1 = {'R': 0, 'T': 0, 'C': 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    lst = 'RTCFJMAN'

    for string, score in list(zip(survey, choices)):
        if score == 4:
            continue
        elif score > 4:
            dic1[string[1]] += abs(score - 4)
        else:
            dic1[string[0]] += abs(score - 4)
    for i in range(0, len(lst), 2):
        if dic1[lst[i]] >= dic1[lst[i + 1]]:
            answer += lst[i]
        else:
            answer += lst[i + 1]

    return answer

풀이 설명:

성격 유형에 대한 점수를 확인하기 위해 다음과 같이 탐색을 해주었습니다.

또한, 탐색 결과를 바탕으로 문제 조건에 맞게 점수를 배분하였습니다.

• 4점 이상일 경우, 'RT'(예시)에서 T에 점수를 배정
• 4점 이하일 경우, 'RT'에서 R에 점수를 배정

for string, score in list(zip(survey, choices)):
    if score == 4:
        continue
    elif score > 4:
        dic1[string[1]] += abs(score - 4)
    else:
        dic1[string[0]] += abs(score - 4)

이후, 각 성격 유형에 대해 점수가 다 반영되면 각 카테고리 별로 강한 성향을 보이는 성격 유형을 answer에 담아주었습니다.

for i in range(0, len(lst), 2):
    if dic1[lst[i]] >= dic1[lst[i + 1]]:
        answer += lst[i]
    else:
        answer += lst[i + 1]

문제: LZW 압축

풀이 코드:

import string


def solution(msg):
    answer = []
    alphabet = list(string.ascii_uppercase)
    dic = {c: i + 1 for i, c in enumerate(alphabet)}
    pos = 27

    while msg:
        length = 1

        while msg[:length] in dic.keys() and length <= len(msg):
            length += 1
        if msg[:length] not in dic.keys():
            dic[msg[:length]] = pos
            pos += 1

        answer.append(dic[msg[:length - 1]])
        msg = msg[length - 1:]

    return answer

문제풀이:

alphabet = list(string.ascii_uppercase)
dic = {c: i + 1 for i, c in enumerate(alphabet)}

먼저, 알파벳에 대한 index가 필요하기 때문에 다음과 같이 enumerate 함수를 통해 딕셔너리 형태로 알파벳:index 형태로 저장해주었습니다.

while msg:
    length = 1

    while msg[:length] in dic.keys() and length <= len(msg):
        length += 1
    if msg[:length] not in dic.keys():
        dic[msg[:length]] = pos
        pos += 1

    answer.append(dic[msg[:length - 1]])
    msg = msg[length - 1:]

가장 핵심이 되는 코드는 문제 조건에 따라 다음과 같이 구현하였습니다.

• 문자열의 시작점으로부터 문자를 탐색하여 딕셔너리에 담긴 최대 길이의 문자열을 구합니다. 즉, 해당 문자열에 한 글자가 추가된다면 해당 문자열은 딕셔너리에 담기지 않은 문자열이 됩니다.
• 딕셔너리에 담기지 않는 문자열에 대해서는 새로운 index와 함께 딕셔너리에 추가해줍니다.
• 딕셔너리에 담긴 최대 길이 문자열에 대한 index를 answer 배열에 담습니다.

위 과정을 반복하여, 문자열을 압축합니다.

문제: 두 개의 문자열이 있을 때, 자카드 유사도를 구하는 문제입니다.

조건:

• 입력된 문자열을 두 글자씩 끊어서 다중집합의 원소로 만듭니다.
• 이때, 토큰화 된 문자열에 특수문자가 들어갈 경우 제외합니다.
• 대문자와 소문자의 차이는 무시합니다.

풀이 코드:

num = 65536


def solution(str1, str2):
    answer = 0

    dic1 = dict()
    dic2 = dict()

    ls1 = len(str1)
    ls2 = len(str2)
    
    for i in range(ls1 - 1):
        key = str1.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic1.get(key):
                dic1[key] += 1
            else:
                dic1[key] = 1

    for i in range(ls2 - 1):
        key = str2.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic2.get(key):
                dic2[key] += 1
            else:
                dic2[key] = 1

    # intersection
    int_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            int_val += min(dic1[i], dic2[i])
    # Union 구하기
    uni_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            uni_val += max(dic1[i], dic2[i])
            dic2.pop(i)
        else:
            uni_val += dic1[i]

    for i in dic2.keys():
        uni_val += dic2[i]

    if uni_val == 0:
        answer = num
    else:
        answer = int(int_val / uni_val * num)

    return answer

풀이 설명:

for i in range(ls1 - 1):
    key = str1.lower()[i:i + 2]
    if key.isalpha():  # 특수문자 있을 경우 제외.
        if dic1.get(key):
            dic1[key] += 1
        else:
            dic1[key] = 1

자카드 유사도의 경우, 다중집합의 경우 같은 문자열도 다른 원소로 취급하므로 개 수를 세기 위해 딕셔너리를 활용하였습니다.

또한, 특수문자가 포함된 문자열을 제거하기 위해 .isalpha() 함수를 활용하였습니다.

str1 = '112' str2 = '1212' 일 경우,

dic1 = { '11' : 1 , '12': 1}

dic2 = {'12': 2 , '21:': 1} 가 됩니다.

# intersection
int_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        int_val += min(dic1[i], dic2[i])

교집합을 구하는 부분은 다음과 같습니다. 토큰화된 문자열에 대한 개 수를 담은 딕셔너리의 key 값을 통해 같은 key가 존재할 경우, 

교집합이기 때문에 최소값을 더해주었습니다.

위의 예시에서 str1에는 '12'가 1개 , str2에는 '12'가 2개 있을 때 교집합은 1개 인 것을 보면 이해에 도움이 되실 것 입니다.

# Union 구하기
uni_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        uni_val += max(dic1[i], dic2[i])
        dic2.pop(i)
    else:
        uni_val += dic1[i]

for i in dic2.keys():
    uni_val += dic2[i]

합집합의 경우, 두 문자열에 모두 존재하는 원소일 경우 개 수의 최대 값을, dic1에만 존재할 경우 그 원소의 개 수를 더하도록 하였으며, 

교집합에 해당되는 원소에 대한 값을 반영하였을 경우, pop() 함수를 통해 dic2에서 제거를 해주었습니다.

그리고 아직 dic2에만 있는 원소에 대한 값을 반영하지 않았으므로, 반복문을 별도로 구성해 값을 반영하여 주었습니다.

문제를 풀고 나서 다른 코드들을 보니 엄청 깔끔하고 파이써닉하게 풀어낸 코드가 있어서 소개드리고 마무리 하도록 하겠습니다.

num = 65536

def solution(str1, str2):
    answer = 0

    token1 = [str1[i:i + 2].lower() for i in range(len(str1) - 1) if str1[i:i + 2].isalpha()]
    token2 = [str2[i:i + 2].lower() for i in range(len(str2) - 1) if str2[i:i + 2].isalpha()]

    intersect = set(token1) & set(token2)
    uni = set(token1) | set(token2)


    uni_val = sum(max(token1.count(i), token2.count(i)) for i in uni)
    intersect_val = sum(min(token1.count(i), token2.count(i)) for i in intersect)


    if uni_val == 0:
        answer = num
    else:
        answer = int(intersect_val/uni_val*num)
    return answer

다중집합의 원소의 개 수로 답을 구하는 문제이므로, set()과 count() 함수를 통해 깔끔하게 풀어낸 풀이가 있더라구요. 보면서 감탄만 나왔던 코드였습니다. 제가 앞으로 파이썬으로 알고리즘을 공부해가면서 나아가야할 방향을 보여주는 듯 했습니다.

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 플로이드 워셜 알고리즘이란?

최단 경로 알고리즘 중 하나로, 모든 노드에서 모든 노드까지의 최단 경로를 모두 구하는 알고리즘 입니다.

플로이드 워셜 알고리즘은 거리 정보를 계산할 때, 점화식을 활용한다는 점에서 다이나믹 프로그래밍이 적용되어 있다고 할 수 있습니다.

점화식은 다음과 같습니다.

$$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$

동작과정은 다음과 같습니다.

1. 초기 값 입력. 

각 간선(edge)에 대한 cost가 주어진다고 가정하였을 때, 이차원 배열에 해당 cost를 갱신 시킵니다.

자기 자신에 대한 cost는 0이며, 갈 수 없는 노드는 INF로 초기화 합니다.

2. 각 노드를 순회하며, 해당 노드를 거쳐갈 수 있는 경로 확인 및 갱신

예를 들어, 모든 1번 노드에 대해서 거쳐갈 수 있는 경로는 다음과 같습니다.

$$D_{23} = min(D_{23}, \, D_{21}+D_{13}) \qquad =>min(2,7+4) == 2$$

$$D_{24} = min(D_{24}, \, D_{21}+D_{14}) \qquad =>min(2,7+INF) == 2$$

$$D_{32} = min(D_{32}, \, D_{31}+D_{12}) \qquad =>min(INF,5+1) == 6$$

↑update

$$D_{34} = min(D_{34}, \, D_{31}+D_{14}) \qquad =>min(3,5+INF) ==3$$

$$D_{42} = min(D_{42}, \, D_{41}+D_{12}) \qquad =>min(INF,1+1) == 2$$

↑update

$$D_{43} = min(D_{43}, \, D_{41}+D_{13}) \qquad =>min(INF,1+4)==5$$

↑update

이와 같이 거쳐가는 경로를 계산하여, 기존 담겨있는 cost보다 더 낮은 cost가 든다면 table을 갱신하여 줍니다.

이 과정을 모든 노드에 대하여 반복하여 줍니다.

2. 코드구현

코드는 백준 알고리즘 11404번을 기반으로 작성되었습니다.

• 이차원 배열(= 거리 테이블)에 대하여, 자신한테로의 경로를 0으로 초기화 해줍니다.
• 간선와 cost에 대한 정보를 입력받아 거리 테이블에 갱신하여 줍니다.
• 3중 for문을 통해, 각 노드별로 거쳐가는 경로(점화식 기반)를 모두 탐색하고 거리 테이블을 갱신합니다. 

import sys

INF = sys.maxsize

n = int(input())    # number of city
m = int(input())    # number of bus

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0  # path to self = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = min(graph[a][b],c)    # update array about initial path

# D_ab = D_ak + D_kb
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for i in range(1,n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            graph[i][j] = 0
for i in range(1, n+1):
    print(*graph[i][1:])
    # print(' '.join(map(str,graph[i][1:])))

• Reference

https://freedeveloper.tistory.com/385

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

다익스트라(dijkstra) 알고리즘은 최단 경로를 구하는 알고리즘 중 하나입니다.

1. 최단 경로(Shortest Path) 알고리즘이란?

Path와 cost가 주어졌을 때, cost가 제일 적게 드는 경로를 찾는 알고리즘 입니다.

특히, 다익스트라 알고리즘은 한 지점에서 특정 지점까지의 최단 경로를 구하는 알고리즘으로 시작점과 끝점을 필요로 합니다.

자료구조로는 graph를 사용하며, 지점을 그래프의 node로 표현하고 경로를 그래프의 edge로 표현합니다.

2. 다익스트라 알고리즘

1. 시작 노드가 1이라고 했을 때, 알고리즘이 동작하는 원리는 다음과 같습니다.
2. 1에서 cost가 가장 가까운 노드 3에 대한 distance를 업데이트 합니다
3. 1에서 가장 가까운 노드를 모두 업데이트 합니다. 즉, 1에 대해서 1 -> 3, 1 -> 2, 1 -> 5 의 cost가 업데이트 됩니다.
4. 코스트가 낮은 3으로 이동하지만 연결된 노드가 없으므로, 2로 이동합니다.
5. 2 -> 5의 cost = 1이므로, 1 -> 5 의 최소 cost는 6 입니다. 따라서, 기존의 cost 9 짜리 1 -> 5 경로는 폐기되고 6으로 새로 업데이트 됩니다.

*다익스트라 알고리즘은 모든 cost가 음의 정수가 아니어야만 동작 가능합니다. 음의 정수가 포함되어 있을 경우, 최단거리를 구하는 알고리즘은 Bellman-Ford 알고리즘으로 향후 포스팅 하도록 하겠습니다.

*시간복잡도는 우선순위 큐를 사용할 경우, O($ElogV$)입니다.

3. 코드구현

• 노드에 대한 정보를 담을 때는, graph를 활용합니다.
• 우선순위 큐와 거리 정보를 담을 list를 사용합니다.
• 반복문을 통해, 출발 노드 부터 최소거리 순으로 거리 정보를 업데이트 해줍니다.
• 위 그림의 1 -> 2 -> 5와 같이 거쳐서 가는 경로에 대한 거리 정보도 업데이트 해줍니다.
• 거리정보 업데이트가 완료되면, 수행을 종료합니다.

코드는 백준 알고리즘 1753번 문제 풀이를 통해 작성하였습니다.(https://www.acmicpc.net/problem/1753)

import sys
import heapq

INF = 1E10

v, e = map(int, sys.stdin.readline().split())
k = int(input())

graph = [[]for _ in range(v+1)]
heap_q = [(0, k)]
distance = [INF] * (v+1)
distance[k] = 0

for _ in range(e):
    start, end, cost = map(int, sys.stdin.readline().split())
    graph[start].append((cost,end))


def dijkstra():
    while heap_q:
        nowCost, node = heapq.heappop(heap_q)

        if distance[node] < nowCost:    # if distance is updated
            continue

        for newCost, newNode in graph[node]:    # check adjacent node
            dist = distance[node] + newCost
            if distance[newNode] > dist:    # update lower cost
                distance[newNode] = dist
                heapq.heappush(heap_q, (dist, newNode))

dijkstra()

for i in range(1,v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

Reference

https://jaemunbro.medium.com/algorithm-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-python-20f061fdc8f1

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. BFS란?

그래프를 탐색하는 알고리즘의 한 종류로, leaf 노드에 도달할 때 까지 깊이 우선 탐색을 하는 DFS와 달리 인접한 노드부터 탐색하는 방법입니다. 그래프의 각 깊이 별로 탐색을 하게 되므로, 넓이 우선 탐색이라고 부릅니다.

*시간복잡도는 DFS와 마찬가지로 인접리스트 방식은 모든 노드(n)와 간선(e)을 탐색하므로, O(n+e) 입니다.

구체적으로 단계를 설명해보자면 다음 그림과 같습니다.

2. 구현 방법

• queue를 통해 인접한 배열을 담아가며 탐색합니다.
• visited 배열을 통해 방문 여부를 확인합니다.
• 인접한 노드를 우선적으로 탐색하며, 방문하지 않은 노드만 탐색합니다.

백준알고리즘 1260번을 기반으로 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_bfs = [False]*(n+1)

def bfs(n):
    q = deque([n])
    visited_bfs[n] = True

    while q:
        node = q.popleft()
        print(node, end=' ')

        for new_node in graph[node]:
            if visited_bfs[new_node]:
                continue
            q.append(new_node)
            visited_bfs[new_node] = True

bfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. DFS란? 

그래프를 탐색하는 알고리즘의 한 종류로, leaf node(자식이 없는 노드)에 도달할 때까지 한 방향으로 탐색하는 기법입니다.

*시간 복잡도는 인접리스트 방식의 DFS는 모든 노드(n)와 모든 간선(e)을 탐색했다고 할 수 있으므로, O(n+e)의 복잡도를 가집니다.

구체적으로 보자면, 다음과 같은 탐색과정을 거칩니다.

2. 코드 구현

• 재귀적 구현을 통하여 구현합니다.
• visited 배열을 통해 방문 여부를 확인하여야 합니다.
• 노드를 방문할 경우 방문처리를 해주며, 방문하지 않은 노드만 방문합니다.
• 방문하는 방향으로 leaf node에 도달할 때 까지 탐색을 진행합니다.
• 위, 과정을 모든 leaf node를 방문할 때 까지 반복합니다.

백준 알고리즘 1260번을 통하여 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_dfs = [False]*(n+1)

def dfs(n):
    print(n, end=' ')
    visited_dfs[n] = True

    for node in graph[n]:
        if visited_dfs[node]:
            continue
        dfs(node)
dfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 이진 탐색(Binary Search)이란?

오름차순으로 정렬된 배열에서 찾고자하는 element를 탐색하는 알고리즘 입니다.

데이터를 반으로 나눠가며 탐색을 진행합니다.

시간 복잡도는 O( log N ) 입니다.

 2. 구현 방법

• 배열에서 중간 값을 찾고자하는 target 값이랑 비교한다
• 중간 값 < target 이라면, 중간 값보다 오른쪽에 있는 배열로 범주를 좁혀 과정을 반복한다
• 중간 값 > target 이라면, 중간 값보다 왼쪽에 있는 배열로 범주를 좁혀 과정을 반복한다

3. 코드

백준 알고리즘 10815번을 기준으로 작성하였습니다.

myCard - 오름차순으로 정렬 되어 있는 배열

Binary Search - 반복문

def binarySearch(target):
    start = 0
    end = len(myCard) - 1

    while start <= end:
        mid = (start + end) // 2
        if myCard[mid] == target:
            return 1
        elif myCard[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return 0

Binary Search - 재귀

def binarySearch(target,start,end):
    mid = (start+end)//2

    if start > end:
        return 0
    if myCard[mid] == target:
        return 1
    elif myCard[mid] < target:
        start = mid + 1
    else:
        end = mid -1

    return binarySearch(target,start,end)