최단경로 알고리즘 특히 가중치가 있는 경우 유용하다

모든 정점이 출발지에서 도착지로 갈 수 있다는 가정하에 O(V^2) -> 우선순위 큐를 사용해 O(E logV)

python에서는 최소 heap을 이용해 구현하면 된다

백준 4485 녹색 옷 입은 애가 젤다지?

시간초과 - visited로 재방문 방지

import sys
input = sys.stdin.readline
import heapq

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
problem = 0

while True:
    problem += 1
    n = int(input())
    if n == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(n)]
    visited = [[False]*n for _ in range(n)]

    q = []
    # cost, x, y
    heapq.heappush(q, (graph[0][0], 0, 0))

    while q:
        cost ,x, y = heapq.heappop(q)
        visited[x][y] = True

        if x == n-1 and y == n-1:
            print(f"Problem {problem}: {cost}")
            break

        for i in range(4):
            xx, yy = x + dx[i], y+dy[i]
            if 0<=xx<n and 0<=yy<n and not visited[xx][yy]:
                heapq.heappush(q, (cost+graph[xx][yy], xx, yy))

성공 - distance로 비교해서 재방문 방지 방문하지 않은 node의 비용은 inf 방문할 때 기존 비용보다 작다면 비용을 update

import sys
input = sys.stdin.readline
import heapq

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
problem = 0

while True:
    problem += 1
    n = int(input())
    if n == 0:
        break

    graph = [list(map(int, input().split())) for _ in range(n)]
    distance = [[int(1e9)]*n for _ in range(n)]

    q = []
    # cost, x, y
    heapq.heappush(q, (graph[0][0], 0, 0))

    while q:
        cost ,x, y = heapq.heappop(q)

        if x == n-1 and y == n-1:
            print(f"Problem {problem}: {cost}")
            break

        for i in range(4):
            xx, yy, ncost = x + dx[i], y+dy[i], cost + graph[x][y]
            if 0<=xx<n and 0<=yy<n and ncost<distance[xx][yy]:
                distance[xx][yy] = ncost
                heapq.heappush(q, (cost+graph[xx][yy], xx, yy))

bfs와 살짝 섞어서 마음대로 풀었더니 시간초과가 발생했다

visited로 했을 때 시간초과가 나는 이유 완전 적절한 예시는 아니지만 distance로 했을 때 큐에 불필요한 값이 들어가지 않는다 언뜻 생각했을 때는 같은 node에 중복탐색을 허용하면 탐색을 더 많이 하는거 아닌가? 생각이 들었지만 직접 해보니 OK

컴공스러운 문제 설명을 읽는게 재미있었다

백준 5972 택배 배송

import sys
input = sys.stdin.readline
from collections import defaultdict
import heapq

n, m = map(int, input().split())
dic = defaultdict(list)

for _ in range(m):
    a, b, c = map(int, input().split())
    dic[a].append((b, c))
    dic[b].append((a, c))


q = []
heapq.heappush(q, (0, 1))

dist = [int(1e9)] * (n+1)

while q:
    cost, node = heapq.heappop(q)
    if node == n:
        print(cost)
        break
    for next_node, next_cost in dic[node]:
        if cost + next_cost < dist[next_node]:
            heapq.heappush(q, (cost+next_cost, next_node))
            dist[next_node] = cost + next_cost

가장 기본적인 문제

위 문제와 같이 visited / distance로 계산하는 코드로 비교해 봤는데 약 1.7배로 꽤 큰 차이가 난다

트리는 계층형 트리 구조를 시뮬레이션하는 추상 자료형으로 서브트리로 구성되어 있다. 트리의 자식도 트리, 자식의 자식도 트리라는 의미이다. 이때문에 트리는 재귀로 정의된 자기참조 자료구조 속성을 가진다. 짧게 말해 순환 구조를 가지지 않으므로 순환구조를 갖지 않는 그래프이다.

백준 1967 트리의 지름 시작과 끝이 어디인지 상관없이 최대 길이를 구하는 문제이다 당연히 leaf 에서 leaf가 최대 길이일것이다

import sys
input = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**9)

tree = defaultdict(list)
#부모, 자식, 간선길이
n = int(input())
for _ in range(n-1):
    p, c, d = map(int, input().split())
    tree[p].append((c,d))
    tree[c].append((p,d))


visited = [-1]*(n+1)
def dfs(curr, curr_dist):
    for next, add_dist in tree[curr]:
        if visited[next] == -1:
            visited[next] = curr_dist+add_dist
            dfs(next, curr_dist+add_dist)

visited[1] = 0
dfs(1,0)
new_start = visited.index(max(visited))
visited = [-1]*(n+1)
visited[new_start] = 0
dfs(new_start, 0)
print(max(visited))

루트에서 시작해 가장 먼 leaf를 찾고, 그 leaf에서 다시 탐색을 시작해 leaf-leaf 최대 길이를 구했다

백준 1068 트리 트리가 주어지고 삭제할 노드가 주어진다 삭제한 노드의 자식들도 모두 삭제된다. 입력으로 자신의 부모를 알려주고, 부모가 -1이라고 주어진 노드가 root node이다.

삭제한 노드를 제외하고 리프 노드의 개수를 출력하면 된다.

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def bfs(c):
    leaf = 0
    q = deque()
    q.append(c)
    while q:
        curr = q.popleft()
        flag = False
        for next in tree[curr]:
            q.append(next)
            flag = True
        if not flag:
            leaf += 1
    return leaf


n = int(input())
l = list(map(int, input().split()))
delete = int(input())

if delete == l.index(-1) :
    print(0)
else:
    tree = defaultdict(list)
    for child, parent in enumerate(l):
        if parent != -1 and child != delete:
            tree[parent].append(child)
    print(bfs(l.index(-1)))

bfs는 특별한 기능 없이 leaf노드의 개수를 세어 주도록 했다. 문제 조건은 간단하게 삭제한 노드만 트리에 포함시키지 않는 방법을 택했다. 그 노드만 포함시키지 않아도 그 자식노드가 tree에는 존재하지만 bfs를 진행하며 queue에 포함되지 않기 때문에 문제가 없다.

root node를 삭제시킬 경우만 예외를 작성해서 처리했다. 처음에는 무조건 인덱스0로 주어진 node가 root node라고 생각해서 시간이 조금 걸렸다.

백준 11438 LCA 2

잘 작동하기 위해 2가지 조건이 있다

• 탐욕선택 속성 앞의 선택이 이후 선택에 영향을 주지 않는다
• 최적 부분 구조 첫줄에 적은것과 비슷한 의미. 로컬 최적이 글로벌 최적이 되는 경우이다.

휴리스틱

교수님이 휴리스틱에 대해 1시간 넘게 열정적으로 설명해 주셨던 기억이 난다.. 설명하며 되게 행복해 보이셨다

합리적이고 체계적인 판단이 어려울 때, 필요 없을 때 빠르게 사용할 수 있는 간편추론의 방법

알고리즘에서는 최적해가 될 가능성이 없는 답들을 탐색하지 않고 답의 후보개수를 줄이는 방법이라고 한다..

• 가지치기 기법 (pruning)
• 담금질 기법 (simulated annealing)
• 유전 알고리즘 (genetic algorithm) 대표적으로 이 3가지이고, 솔직히 수업을 들을때는 왜 중요한지도 모르겠고 잘 이해도 안되었는데 요즘 인공지능이 많이 중요해지면서 이러한 기법이 더 중요해지고 있다는 것을 느꼈다. 특히 stable diffusion모델 checkpoint를 이것 저것 둘러보다 보면 pruned model이 많이 보인다.. 이 부분은 따로 다뤄봐야겠다.

백준 2138 전구와 스위치

import sys
input = sys.stdin.readline

n = int(input())
status = list(map(int, input().rstrip()))
target = list(map(int, input().rstrip()))

def change(stat, target):
    cop = stat[:]
    ans = 0
    for i in range(1, n):
        if cop[i-1] == target[i-1]:
            continue
        ans += 1
        for j in range(i-1, i+2):
            if j<n:
                cop[j] = 1 - cop[j]
    if cop == target:
        return ans 
    else:
        return float('inf')

cand = change(status, target)
status[0] = 1-status[0]
status[1] = 1-status[1]
cand = min(cand, change(status, target)+1)

print(-1) if cand==float('inf') else print(cand)

hash를 설명하며 교수님은 이렇게 말씀하셨다 어떤 값을 찾기 위해 어떻게 해야할까요?

1. 결과가 나올때까지 하나하나 검색 O(n) 전공자는 이러면 안된다
2. sorting 후 binary search O(logN) not bad.. 하지만 1, 2학년 수준 정렬이 안되는 상황이 있을 수 있고, 굳이 정렬을?
3. hash table O(1) good

-> 어떤 상황에 뭘 사용해야 적절한지 알기 위해 자료구조를 아는 것이다

약간의 울림이 있었다 군대가기 전 2학년때 배운 자료구조 수업에서는 난 아무 생각이 없었다 다시 알아보자

hash 데이터를 효율적으로 다루기 위한 방법중 하나 임의의 길이의 데이터를 고정된 길이의 데이터로 mapping한 값

hash function 임의의 길이의 데이터를 hash로 매핑하는 함수 같은 input은 같은 output

hash table key, value 형태로 데이터를 저장하는 자료구조 hash function의 hash값을 index로 사용

hashing hash function에서 hash를 출력하고 hash table에 저장

python dictionary가 hash 테이블을 사용한 자료형이다!

cryptographic hash function hash function의 일종이지만, 3가지 성질을 더 가진다

• 역상 저항성 : output으로 input을 찾는 것이 더 어렵다
• 제 2 역상 저항성 : output이 바뀌지 않는 input을 찾는 것이 더 어렵다
• 충돌 저항성 : 같은 output을 가지는 input을 찾는 것이 더 어렵다

제 2 역상 저항성과 충돌 저항성이 같은 것 같은데?? -> 공격의 시나리오가 다르다 - 수식을 보니 이해가 된다

• 제 2역상 저항성 x1, h(x1)을 알고 있을 때 h(x1) = h(x2)인 x2를 찾는 것이 어려움
• 충돌 저항성 그냥 h(x1) = h(x2)인 x1, x2를 찾는 것이 어려움

프로젝트를 하며 검색기능을 맡게 되었다. 기존방식은 post_body에 검색어 포함으로 필터링 하였다(icontain)

개선 방향

1. 연관된 상품 추천 (검색어와 비슷한 상품 노출)
2. 오타 정정
3. 텍스트로 이미지 검색

시행착오, 과정

openapi text embedding, postgresql pgvector extension 사용

pgvector 관련 글은 따로 작성

다음과 같은 ERD product_specific값으로 embedding 생성

def get_embedding(text):
    headers = {
        'Content-Type': 'application/json',
        'Authorization': f'Bearer {OPENAI_API_KEY}',
    }
    data = {
        "input": text,
        "model": "text-embedding-3-small"
    }
    response = requests.post('https://api.openai.com/v1/embeddings', headers=headers, json=data)
    response_data = response.json()
    return response_data['data'][0]['embedding']

@api_view(['POST'])
def search(request):
    data = request.data
    query = data['query']
    query_embedding = get_embedding(query)
    products = Product.objects.annotate(
        similarity=CosineDistance(F('embeddings'), query_embedding)
    ).order_by('similarity')[:10]

    posts = Post.objects.filter(product__in=products)
    posts_serializer = PostSerializer(posts, many=True)    

    return JsonResponse({
        'posts': posts_serializer.data
    }, safe=False)

db에 있는 모든 product에 similarity필드를 annotate하고 상위 10개 정렬 모든 product를 조회하니까 당연히 성능에 문제가 있을 것이다

class SearchPerformanceTestCase(TestCase):
    def setUp(self):
        self.client = APIClient()
        self.url = reverse('search')
        self.user = User.objects.create_user(name='testuser', email='testuser@example.com', password='testpassword')
        self.client.login(username='testuser', password='testpassword')
        self.category = Category.objects.create(id=1, name='TestCategory')

    def create_products(self, count):
        for i in range(count):
            Product.objects.create(
                category=self.category,
                price=100,
                name=f'TestProduct{i}',
                specific='TestSpecific',
                seller=self.user,
                embeddings=[0.01] * 1536 
            )

    def test_search_performance_10(self):
        self.create_products(10)
        self._test_search_performance()

    def test_search_performance_100(self):
        self.create_products(100)
        self._test_search_performance()

    def test_search_performance_1000(self):
        self.create_products(1000)
        self._test_search_performance()

    def _test_search_performance(self):
        data = {
            'query': 'test query'
        }

        start_time = time.time()
        response = self.client.post(self.url, data, format='json')
        end_time = time.time()

        self.assertEqual(response.status_code, 200)
        print(f"Search execution time with {Product.objects.count()} products: {end_time - start_time} seconds")

pgvector github페이지에서

Indexing By default, pgvector performs exact nearest neighbor search, which provides perfect recall. You can add an index to use approximate nearest neighbor search, which trades some recall for speed. Unlike typical indexes, you will see different results for queries after adding an approximate index. Supported index types are: HNSW - added in 0.5.0 IVFFlat

HNSW An HNSW index creates a multilayer graph. It has better query performance than IVFFlat (in terms of speed-recall tradeoff), but has slower build times and uses more memory. Also, an index can be created without any data in the table since there isn’t a training step like IVFFlat. Add an index for each distance function you want to use.

HNSW (Hierarchical navigable small world graphs)

모든 기술이 그렇듯 KNN, navigable small worlds, index-IVFFLAT등 다른 방법의 단점을 개선한 인덱싱 알고리즘이고, 이를 이용하라고 추천한다.

10개는 결과가 이상하다

5번의 search 시간을 평균값을 내도록 수정하여 1000개의 product가 있는 경우를 실험했는데 별 차이가 없었다..

1000개밖에 안되어서 그런걸까?

그냥 testdb를 하나 더 만들어서 시원하게 100,000개의 product 데이터를 넣었다 너무 오래걸려 여기까지만 32224개로 test

sys.path.append(os.path.join(os.path.abspath(os.path.dirname(__file__)), '..'))
os.environ.setdefault("DJANGO_SETTINGS_MODULE", "config.settings")
django.setup()

def populate_db():
    user = User.objects.create_user(name='testuser2', email='testuser2@example.com', password='testpassword')
    category, created = Category.objects.get_or_create(id=1, name='fruit')

    for i in range(100000): 
        Product.objects.create(
            category=category,
            price=random.randint(50, 150),
            name=f'TestProduct{i}',
            specific='TestSpecific',
            seller=user,
            embeddings=[random.uniform(-1, 1) for _ in range(1536)]
        )

if __name__ == "__main__":
    populate_db()

>>> Product.objects.count()
32224

그 전에, 미리 생각했어야 할 부분을 놓치고 지나갔다. 왜 저렇게 시간이 들쭉날쭉 할까? 그리고 차이가 별로 나지 않을까? 약간 딴길로 잠시 새자면

@api_view(['POST'])
def search(request):
    data = request.data
    query = data['query']
    start = time.time()
    query_embedding = get_embedding(query)
    end = time.time()
    print(f"Embedding generation time: {end - start} seconds")

    start = time.time()
    with connection.cursor() as cursor:
        cursor.execute("""
            SELECT id
            FROM post_product
            ORDER BY embeddings <=> %s::vector
            LIMIT 10
        """, [query_embedding])
        product_ids = [row[0] for row in cursor.fetchall()]

    end = time.time()
    print(f"Search execution time: {end - start} seconds")

    start = time.time()
    products = Product.objects.filter(id__in=product_ids)
    end = time.time()
    print(f"Product retrieval time: {end - start} seconds")

    # products에 해당하는 posts를 추출
    start = time.time()
    posts = Post.objects.filter(product__in=products)
    end = time.time()
    print(f"Post retrieval time: {end - start} seconds")
    posts_serializer = PostSerializer(posts, many=True)

    return JsonResponse({
        'posts': posts_serializer.data
    }, safe=False)

사실은 open api에서 검색어의 embedding을 가져오는 시간이 80%정도 차지했다.. test 부분에서 시간을 측정하는 것이 아니라, 내가 원하는 search execution 부분의 시간을 측정하는게 맞다.

결론

다시 원래 하던 test로 돌아와서 testcode (여기 작성한 average타임은 위에서 말했듯 크게 유의미 하지 않은걸로)

class SearchPerformanceTest(unittest.TestCase):
    def setUp(self):
        self.client = APIClient()
        self.url = reverse('search')
        self.user = User.objects.get(name='testuser')
        self.client.login(name='testuser', password='testpassword')
        self.category = Category.objects.get(name='fruit')

    def test_search_performance(self):
        data = {
            'query': 'test query'
        }

        times = []
        for _ in range(10):
            start_time = time.time()
            response = self.client.post(self.url, data, format='json')
            end_time = time.time()
            times.append(end_time - start_time)

        avg_time = sum(times) / len(times)

        self.assertEqual(response.status_code, 200)
        print(f"Average search execution time: {avg_time} seconds")

indexing 전, 후 search execution 결과 (32224개의 product 데이터)

생각보다 차이가 엄청나다.. 계산은 gpt에게 21배.. 알고리즘의 힘은 엄청나다는걸 또 느낀다

참조 https://github.com/pgvector/pgvector https://inspirit941.tistory.com/504

헷갈렸던 문법

l = Counter(['a', 'b', 'c', 'a'])
compare = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
missing = 4

for component in compare:
    missing -= l[component] 
    print(l)
    print(missing)

counter에는 {'a': 2, 'b': 1, 'c': 1}가 들어있으니 당연히 missing은 반복문이 끝난 후 0이 된다.

from collections import Counter

l = Counter(['a', 'b', 'c', 'a'])
compare = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
missing = 4

for component in compare:
    missing -= l[component] > 0
    print(l)
    print(missing)

Counter({'a': 2, 'b': 1, 'c': 1}) 3 Counter({'a': 2, 'b': 1, 'c': 1}) 2 Counter({'a': 2, 'b': 1, 'c': 1}) 1 component에 'a', 'b', 'c'가 들어갔을 때 결과이다. 양수일 경우 해당 값을 빼는 것이 아니라 -1만 해주는 결과가 나왔다 missing -= 1 if component in l else missing 기능을 수행하는 것과 같다

leetcode 76. Minimum Window Substring

문자열 s, t가 주어지는데 t를 포함하는 최소 문자열을 s에서 찾는 문제

class Solution:
    def minWindow(self, s: str, t: str) -> str:
      need = Counter(t)
      start = end = left = 0
      missing = len(t)

      for right, char in enumerate(s, 1): # 오른쪽 포인터를 움직이다가
          missing -= need[char] > 0
          need[char] -= 1


          if missing == 0: # 다 찾았으면 왼쪽 포인터를 움직인다
              # need에서 양수가 되면 왼쪽 포인터를 그만 움직여야 하니까 0이 된 순간 탈출 -> start, end에 현재 포인터값 기록
              # Counter need에서
              # 양수일때 : 필요함(오른쪽 포인터 움직임) / 음수일때 : 필요보다 더 있다(왼쪽 포인터를 계속 움직일 수 있다) / 0일때 : 왼쪽 포인터를 그만움직이는 경계값
              # t에 없는 문자도 need에 기록중이지만 t에 포함이 안되어 있으면 양수가 될 수 없다
              # t에 없는 문자는 0이 될수는 있지만 0이 된 순간 왼쪽 포인터를 움직일 때 다시 나올 수 없기 때문에 탈출 후 기록하지 않으므로 괜찮..
              while left<right and need[s[left]] < 0:
                  need[s[left]] += 1
                  left += 1

              # while 탈출했으므로 필요한 문자를 버리기 직전
              if end == 0 or right-left <= end-start:
                  start, end = left, right
                  # 현재 시작과 끝을 기록 후 왼쪽 포인터값을 버린다(오른쪽 포인터를 이동)
                  # 어떤 문자가 필요한지(need에서 양수), missing += 1
                  need[s[left]] += 1
                  left += 1
                  missing += 1
      return(s[start:end]) # 1부터 시작했으므로 슬라이싱 할때 +1 x

혼자 푸는데 실패했고 코드가 길지는 않지만 counter의 음수값과 0일때 경계값이 헷갈려서 이해하기 힘들었다..

백준 20437 문자열 게임2

문자열 w가 주어지고 어떠한 문자든 상관없이 k개가 포함된 최소, 최대 문자열 길이 출력하는 문제이다. 단 해당 문자열에 딱 k개만 포함

위에 leetcode의 문제를 이해했다는 기쁨으로 인해 무지성 투포인터로 풀기를 해버려 엄청나게 많은 시간을 썼다..

def window(w,k):
    tr_f = False
    ans = 10001
    left = 0
    cnt = Counter()
    for right, char in enumerate(w, 1):
        cnt[char] += 1
        if cnt[char] == k:
            while left < right and cnt[char]==k:
                left += 1
                cnt[w[left]] -= 1
            if ans > right-left:
                ans = right-left
                tr_f = True
    return (tr_f, ans)

def window2(w,k):
    tr_f = False
    ans = -1
    left = 0
    cnt = Counter()
    for right, char in enumerate(w, 1):
        cnt[char] += 1
        if cnt[char] == k:
            prev_cnt = Counter(cnt)
            prev_left = left
            while left < right and cnt[char] == k:
                left += 1
                cnt[w[left]] -= 1
            if ans < right - left:
                ans = right - left
                tr_f = True
            else:
                left = prev_left
                cnt = prev_cnt
    return (tr_f, ans)

t = int(input())
for _ in range(t):
    w = str(input())
    k = int(input())

    tr, ans = window(w,k)
    tr2, ans2 = window2(w,k)
    if not tr or not tr2:
        print(-1)
    else:
        print(ans, ans2)

효율적이지도 않고 맞지도 않는다.. 틀리는 이유는 오른쪽 포인터를 두고 왼쪽 포인터를 움직이면서 최대 길이의 문자열을 지나치게 된다. EX) w = superaquatorndado k = 2 일때

최대 길이인 raquator를 a를 탐색하며 지나가 버린다

블로그가 처음이라 글외에 설명을 어떻게 해야 할지 모르겠다.. 아이패드를 살 좋은 명분인가..?

정확히 내가 필요한 문자가 무엇인지 알고 있을 때는 leetcode 방법이 좋을 수 있겠지만 집착을 버리고 다시 생각해 보니 해결할 수 있었다..

import sys
input = sys.stdin.readline
from collections import Counter, defaultdict

t = int(input())
for _ in range(t):
    w = str(input())
    k = int(input())
    cnt = Counter(w)
    idx_dir = defaultdict(list)
    tr_f = False
    for idx, char in enumerate(w):
        if cnt[char] >= k:
            tr_f = True
            idx_dir[char].append(idx)

    if tr_f:
        ans1 = 10001
        ans2 = -1
        for idx_lst in idx_dir.values():
            for i in range(len(idx_lst)-k+1):
                ans1 = min(ans1, idx_lst[i + k - 1] - idx_lst[i])
                ans2 = max(ans2, idx_lst[i + k - 1] - idx_lst[i])
        print(ans1+1, ans2+1)
    else:
        print(-1)

결국 Counter를 이용해서 k개 이상 나온 문자의 인덱스를 딕셔너리로 저장 k칸만큼 떨어진 딕셔너리 value들끼리 길이 비교 인덱스끼리 뺄셈 했으므로 +1한 값을 출력

백준 1806 부분합

길이가 n인 수열, 연속된 부분합 중 s이상이 되는 것 중 최소 길이 출력

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
l = list(map(int, input().split()))

ans = float('inf')
left = 0
temp = 0
for right in range(n):
    temp += l[right]
    if temp < s:
        continue
    while left <= right and temp >= s:
        temp -= l[left]
        left += 1
    left -= 1
    temp += l[left]
    ans = min(right-left+1, ans)        

print(0) if ans == float('inf') else print(ans)

left, right 투포인터를 사용해서 탐색 부분합이 s이상이면 right를 멈추고 left를 움직인다. while 탈출할때 left가 한칸 더 가니까 탈출 후 left -= 1

간단하게 풀었고 투포인터 문제 중 가장 기본적인것같다..

백준 1522 문자열 교환

a, b로만 이루어진 문자열이 주어지고 a와 b의 위치를 최소로 교환해서 모든 a와 b가 붙어있도록 수정 단 문자열은 원형 구조이다. ex) abbbbbbbbba -> 성공

import sys
input = sys.stdin.readline

ass = input().rstrip()

ans = float('inf')
cnt = ass.count('a')
for i in range(len(ass)):
    if i+cnt >= len(ass):
        ans = min(ans, ass[i:len(ass)].count('b')+ass[0:(i+cnt)%len(ass)].count('b'))
    else:
        ans = min(ans, ass[i:i+cnt].count('b'))

print(ans)

처음에 rstrip을 안해서 틀렸다. 시간 단축을 위해서 sys를 사용하면 문자열을 받을 때 개행문자가 포함되니 까먹지 말자!

로직은 a의 개수만큼으로 슬라이싱해서 부분 문자열에 b가 몇개있는지 count

슬라이딩 윈도우 정석 + 리스트를 원형 자료형으로 생각하는 부분 추가 원형 구조를 해결하기 위해 그냥 % 이용해서 인덱스만 수정해 주었다

백준 1253 좋다

n개의 수가 주어지고 자기 자신을 포함하지 않는 두 수의 합으로 나타낼 수 있으면 좋다 -> 좋은 수의 개수 출력

import sys
input = sys.stdin.readline
from collections import Counter


n = int(input())
l = list(map(int, input().split()))

test = set(l)
cnt = Counter(l)
ans = 0

if 0 in test:
    if cnt[0]>=3:
        ans += cnt[0]
        cnt[0] = 0

    for comp in cnt:
        if cnt[comp]>=2 and comp!=0:
            ans += cnt[comp]
            cnt[comp] = 0


for left in range(n):
    for right in range(left+1, n):
        if l[left] + l[right] in test:
            if l[left] != 0 and l[right] != 0:
                ans += cnt[l[left]+l[right]]
                cnt[l[left]+l[right]] = 0

print(ans)

처음에 counter를 써야겠다 생각이 들어서 그냥 쭉 구현했다. 문제를 풀고 다른사람들의 풀이를 보니 내가 조금 독특하게 푼 것 같긴 하다..

먼저 2가지 숫자를 골라 합한 수가 배열에 있는지 test -> 있으면 개수만큼 정답에 추가 여기서는 counter와 set을 이용했다 문제가 되는 부분은 고른 숫자에 0이 있을 경우이다. 자기 자신을 포함하면 안되기 때문에 0이 있을 경우에만 따로 처리를 해 주었다.

0이 배열에 있을때

0이 3개 이상 있으면 모든 0이 좋다 그리고 0이 하나라도 있으면 0이 아닌 수가 2개이상 있으면 해당 수는 모두 좋다 0때문에 좋은수로 판명난 수는 counter = 0

문제를 해결하고 너무 비효율적이라는 것을 깨달았다..

import sys
input = sys.stdin.readline
from collections import Counter


n = int(input())
l = list(map(int, input().split()))

test = set(l)
cnt = Counter(l)
ans = 0

if 0 in test:
    if cnt[0]>=3:
        ans += cnt[0]
        test.remove(0)

    for comp in cnt:
        if cnt[comp]>=2 and comp!=0:
            ans += cnt[comp]
            test.remove(comp)


for left in range(n):
    for right in range(left+1, n):
        temp = l[left] + l[right]
        if temp in test:
            if l[left] != 0 and l[right] != 0:
                ans += cnt[temp]
                test.remove(temp)

print(ans)

생각보다 느려서 다시 살펴봤더니 counter를 건들것이 아니라 set에서 탐색한 숫자를 지우는게 현명한 선택이었다.

일반적인 투포인터 풀이

수정 전

수정 후

백준 13144 List of Unique Numbers

import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))
cnt=0

for i in range(n):
    for j in range(i+1, n+1):
        sliced = l[i:j]
        if len(sliced) == len(set(sliced)):
            cnt+=1
print(cnt)

슬라이싱 시도 -> 시간초과

cnt = n
left, right = 0, 0

while left < n:
    right = left+1
    num_set = set()
    num_set.add(l[left])
    while left<right<n:
        if l[right] in num_set:
            break
        num_set.add(l[right])
        right += 1
        cnt += 1
    left += 1
print(cnt)

최적화 덜된 투포인터 -> 시간초과

오른쪽 포인터를 움직이다가 걸렸을 때 왼쪽 포인터를 한칸 움직이고 다시 탐색하는게 아니라 오른쪽 포인터가 만족할때까지 왼쪽 포인터를 움직여야 한다

import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))

cnt = 0
left, right = 0, 0
num_set = set()

while left < n and right < n:
    if l[right] not in num_set:
        num_set.add(l[right])
        right += 1
        cnt += right-left
    else:
        while l[right] in num_set:
            num_set.remove(l[left])
            left += 1


print(cnt)

작은 디테일이 큰 성능 차이를 만든다,,

최근에 문제가 공개되지 않아 테스트 케이스를 돌려보지는 못했지만 친구에게 문제 내용을 대충 들어서 2024 네이버 공채 코테문제를 풀어 보았는데 구현보다는 최적화를 어떻게 할 것인지에 대한 요구가 있는 것 같다.. 개인적으로 요긴하게 쓰는 것이 bisect, 직접 구현한 이분탐색, 투포인터 등등.. 이니 구분해서 정리를 해 봐야겠다