아래 글과 코드는 "실전! 파이토치 딥러닝" 책을 참고하였다.

1. Adadelta & Adam 수식

두 알고리즘 모두 적응적 학습률(adaptive learning rate)을 사용 -> 매개 변수의 변화률이 많을 수록 이후에는 낮은 속도의 학습률을 가짐

1.1 Adadelta

1. 학습율 람다에 대한 정의가 필요 없음
2. 이전 경사의 제곱 값을 활용함

1.2 Adam

1. 이전 경사의 제곱 값 뿐만 아니라 감소 크기도 활용함

-> 벡터의 방향과 크기 모두 고려. 2. 대체로 Adam 사용

1.3 요약

2. 비교 실험

MNIST 학습 및 평가 실험을 통해서 두 Optimizer의 차이를 확인하자

epoch = 5 batch size = 32 learning rate for adam = 0.001

2.1. 모델 훈련 시간, 궤적(수렴)

• one epoch 학습 시 소요된 시간 (1875개의 데이터 셋)

1. adadelta: 약 49.46s
2. adam: 약 41.29s

• 수렴 (train loss 확인)

1. adadelta

• 약 batch 1000 이후로 수렴함

2. adam

• 약 batch 2000 이후로 수렴함

2.2. 최종 모델 성능

1. adadelta (training loss: 0.000609, test loss: 0.0343, test accuracy: 9890/10000)
2. adam (training loss: 0.007123, test loss: 0.0316, test accuracy: 9902/10000)

2.3. 매개변수 비교

첫번째 Convolution layer와 flatten 후 dense layer에서 parameter 차이가 크게 발생함.

from copy import deepcopy

import torch
import torch.nn as nn
import torch.nn.functional as F
import torch.optim as optim
from torch.utils.data import DataLoader
from torchvision import datasets, transforms
import matplotlib.pyplot as plt
import time

class ConvNet(nn.Module): #nn.Module을 상속받아 기본적인 기능들을 사용할 수 있게 만듦 => nn.Moudle: 부모 클래스
    def __init__(self):
        super(ConvNet, self).__init__() # super().__init__() 으로 사용해도 같음. 클래스 이름 작성하는 건 python2 버전임
        # 1 in_channels : gray scale image, 16 out channels : 16 feature maps, # stride < kernel_size * 0.1
        self.cn1 = nn.Conv2d(1, 16, 3, 1) # 1 in_channels := gray scale image.
        self.cn2 = nn.Conv2d(16, 32, 3, 1)
        # nn.Dropout: 주로 1차원에 사용. 모든 차원에 사용 가능.
        # 2D: 2D 데이터. 채널 단위로 드랍 아웃. 각 채널에 대해 동일한 위치에 있는 값을 동시에 드롭하기 때문에, 전체 채널이 드롭되거나 유지되는 방식입니다. 이를 통해 채널 간 상관관계를 보존할 수 있습니다.
        # 3D: 동영상. 특정 채널의 모든 프레임이나 볼륨이 드롭되기 때문에, 3D 데이터에서 특정 시퀀스나 채널이 온전히 제거되는 효과를 얻습니다.
        self.dp1 = nn.Dropout2d(0.10)
        self.dp2 = nn.Dropout2d(0.25)
        self.fc1 = nn.Linear(4608, 64) # 32개의 채널, 1개의 채널 = 12 X 12
        self.fc2 = nn.Linear(64, 10) # 10개의 class (classification 문제)

    def forward(self, x): # input 이미지의 해상도 28 X 28 X 1
        x = self.cn1(x) # 3 size kernel 적용 후 26 X 26 X 16
        x = F.relu(x)
        x = self.cn2(x) # 3 size kernel 적용 후 24 X 24 X 32
        x = F.relu(x)
        x = F.max_pool2d(x,2) # 2 size kernel 적용 후 12 X 12 X 32
        x = self.dp1(x)
        x = torch.flatten(x, 1) # 1 X (12 X 12 X 32)
        x = self.fc1(x) # 1 X 64
        x = F.relu(x)
        x = self.dp2(x)
        x = self.fc2(x) # 1 X 10
        op = F.log_softmax(x, dim=1) # softmax에 log 값 취함. gradient 구할 때 Nan 발생 막아주는 함수
        return op

# backpropagation
def train(model, device, train_dataloader, optim, epoch):
    model.train() # ConvNet class를 받아옴
    train_loss = []

    start_time = time.time()

    for b_i, (X, y) in enumerate(train_dataloader): # one epoch
        # (b_i = batch_idx)
        # print(f"Batch {b_i + 1}: data shape = {X.shape}, target shape = {y.shape}")
        # Batch 1: data shape = torch.Size([32, 1, 28, 28]), target shape = torch.Size([32])
        X, y = X.to(device), y.to(device) # copy data

        optim.zero_grad() # optim (torch.optim) 최적화 알고리즘 기능을 담고 있음. SGD, Adam, RMSprop 등
        pred_prob = model(X)
        loss = F.nll_loss(pred_prob, y) # - log softmax
        loss.backward()
        optim.step()

        train_loss.append(loss.item())

        if b_i % 100 == 0: # every 10 batches
            print('epoch: {} [{}/{} ({:.0f}%)]\t training loss: {:.6f}'.format(epoch, b_i, len(train_dataloader), 100.*b_i/len(train_dataloader), loss.item()))

    end_time = time.time()
    print(f"Runtime: {end_time - start_time:.6f} seconds")

    return train_loss

def test(model, device, test_dataloader):
    model.eval() # 학습할 때만 필요한 Dropout, Batchnorm 등의 기능을 비활성화 하여 추론할 때의 모드로 작동
    loss, success = 0, 0
    with torch.no_grad(): # gradient calculation을 비활성화하여 메모리 소비를 제한함 (with은 파일이나 데이터베이스를 시작하고 자동 닫기/종료하는 기능)
        for X, y in test_dataloader:
            X, y = X.to(device), y.to(device)
            pred_prob = model(X)

            # 배치별 손실 합
            loss += F.nll_loss(pred_prob, y, reduction='sum').item()

            pred = pred_prob.argmax(dim=1, keepdim=True) # 500개의 데이터에 대한 라벨이 저장됨

            success += pred.eq(y.view_as(pred)).sum().item() # view_as : reshape

    loss /= len(test_dataloader.dataset)
    print('\nTest dataset: Overall Loss: {:.4f}, Overall Accuracy: {}/{} ({:.0f}%)\n'.format(loss, success, len(test_dataloader.dataset), 100.*success/len(test_dataloader.dataset)))


# 평균값과 표준 편차 값은 훈련 데이터셋의 이미지 전체의 픽셀값 전체에 대한 평균으로 계산된다.
train_dataloader = torch.utils.data.DataLoader(
    datasets.MNIST('../data', train=True, download=True,
                   transform=transforms.Compose([transforms.ToTensor(), transforms.Normalize((0.1302,),(0.3069,))])),
    batch_size=32, shuffle= True
) # transforms.ToTensor() converts a PIL Image or Numpy array to a torch.Tensor and scales its pixel values to the range [0,1]

test_dataloader = torch.utils.data.DataLoader(
    datasets.MNIST('../data', train = False,
                   transform= transforms.Compose([transforms.ToTensor(), transforms.Normalize((0.1302,), (0.3069,))])),
    batch_size=500, shuffle=False
)

torch.manual_seed(0)
device = torch.device("cpu")

model_adadelta = ConvNet()
model_adam = deepcopy(model_adadelta)

optimizer_adadelta = optim.Adadelta(model_adadelta.parameters(), lr=0.5) # Adam 비교 report 제작
optimizer_adam = optim.Adam(model_adam.parameters(), lr=0.001)

# adadelta 로 학습
all_train_losses_adadelta = []
for epoch in range(1,6):
    train_losses = train(model_adadelta, device, train_dataloader, optimizer_adadelta, epoch)
    all_train_losses_adadelta+=train_losses
    test(model_adadelta, device, test_dataloader)

# adam으로 학습
all_train_losses_adam = []
for epoch in range(1,6):
    train_losses = train(model_adam, device, train_dataloader, optimizer_adam, epoch)
    all_train_losses_adam+=train_losses
    test(model_adam, device, test_dataloader)

# test_samples = enumerate(test_dataloader)
# b_i, (sample_data, sample_targets) = next(test_samples)

# plt.imshow(sample_data[0][0], cmap='gray', interpolation = 'none')
# print(f"Model prediction is : {model(sample_data).data.max(1)[1][0]}")
# print(f"Ground truth is : {sample_targets[0]}")

# 손실 값 시각화
# plt.figure(figsize = (10,6))
# plt.plot(all_train_losses, label='Training Loss')
# plt.xlabel('Batch Index')
# plt.ylabel('Loss')
# plt.title('Training Loss Over Batches')
# plt.legend()
# plt.show()

# 모델 파라미터 비교
for name, param_adadelta in model_adadelta.named_parameters():
    param_adam = dict(model_adam.named_parameters())[name]
    print(f"Layer: {name}")
    # print(f"SGD Parameter:\n{sum(param_sgd.data)}")
    # print(f"Adam Parameter:\n{sum(param_adam.data)}")

    diff = torch.mean(param_adadelta.data - param_adam.data)
    print(f"Difference:\n{diff}\n")

    norm_diff = (torch.max(param_adadelta) - diff)/(torch.max(param_adadelta) - torch.min(param_adadelta))
    print(f"Normalized Difference:\n{norm_diff}\n")

# fc1.weight
# cn1.weight

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

seqs = list(map(int, input().split()))

ans = 0
start, end = 0, 1

while start < N:


    if sum(seqs[start:end]) == M:
        ans += 1
        start += 1
        end = start + 1

    elif sum(seqs[start:end]) < M:
        end +=1

        if end == N+1:
            start += 1
            end = start + 1

    else:
        start +=1
        end = start+1

print(ans)

시간초과,,,, ㅠㅠㅠ two point 사용하는 문제 시작점을 하나씩 올려서 나머지 수열을 순차적으로 체크하는 방법

TO DO LIST 1 2 3 4 .. 수열이 있을 때, 1 + 2 + 3+ 4 > 10 2 + 3, 2+ 3+ 4 처럼 반복해서 Sum을 진행하게 된다. 이를 극복해보자!

-> HINT 이미 2472ms로 성공했음

+) sum += a[right] sum -= a[left] 를 활용해서 시컨스 전체를 sum하는 것을 줄이자!

아직 ListNode 와 재귀 함수 사용법이 미숙함.. ㅠㅠ

24-08-05

풀이 실패 Hint1. 재귀 구조 활용 Hint2. L1 = 1 -> 2 -> 3 일 때, L1.next는 1 -> ? 를 의미한다.

24-07-30

class Solution(object):

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        dict = {"2": "abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}

        if len(digits) > 0:

            answer = [""]

            for i in range(len(digits)):
                answer_ = []
                press_number = dict[digits[i]] 
                for letter in press_number:
                    answer_ += [ans + letter for ans in answer]
                answer = answer_

            return answer

        else: #empty input

            return []

각 번호에 할당된 문자열을 리스트로 만들고, 새로운 번호가 눌렸을 때, 새로운 번호의 문자열 리스트와의 조합을 계산한다.

press 2 : ['a', 'b', 'c'] press 3 : ['ae', 'be', 'ce' ,....]

run time은 20ms로, 꽤 길다..

class Solution(object):

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

         if digits == "":
            return []

        dict = {"2": "abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}

        answer = [""]

        for digit in digits:
            answer = [ans + letter for letter in dict[digit] for ans in answer]

        return answer

--> 간결한 코드 버전!

1. 예외 케이스를 앞으로 빼면서 코드 전체 indent를 복잡하지 않게 정리함
2. answer_ 제거. (20ms -> 17ms) answer_를 도입한 이유는 for문 돌면서 answer가 바뀌지 않도록 하는 장치였으나, 두 개의 for문을 inline으로 작성하면서 문제가 해결됨!

To do list DFS를 이용하자! 그래프 문제~~ 모든 경우의 수를 DFS로 탐색하고 백트래킹으로 결과를 조합하면서 리턴하는 코드를 작성하세요. (Hint: 결과를 조합할 때는 v의 길이가 digits의 길이와 같을 때 return 합니다.)

24-07-25

import sys
input = sys.stdin.readline

def n_safe(scores, people):

    answer = 1

    # sort w.r.t paper score rank
    sort_paper = sorted(scores)
    interview_rank_top_paper = sort_paper[0][1]

    if interview_rank_top_paper < 3: # the case: top paper + top interview both. 
        return interview_rank_top_paper

    # sort w.r.t interview score rank
    sort_interview = sorted(sort_paper, key = lambda x:x[1])[:interview_rank_top_paper]

    for paper, interview in sort_interview[1:]:
        if paper < sort_interview[0][0]:
            answer += 1

    return answer

n_problems = int(input())

answer = []
for problem in range(n_problems):
    people = int(input())

    scores = []
    for person in range(people):
        scores.append(list(map(int,input().split())))

    if people > 1:
        answer.append(n_safe(scores,people))
    else:
        answer.append(1)    

print("\n".join(map(str,answer)))

--> 틀림

1. input = sys.stdin.readline 작성없으면 시간초과
2. 서류 심사 순으로 sort한 후 paper 순으로 sort하여 풀었으나, sort는 한번만 해도 된다.

24-06-28 (Time Over.)

from collections import deque

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        self.grid = grid

        self.m = len(grid)
        self.n = len(grid[0])

        idxland = self.indexislands()
        searching_space = len(idxland)
        islands = 0
        discovered = []

        if searching_space > 0:
            while len(idxland) > 0:

                v = idxland.popleft()
                if not v in discovered:
                    islands +=1
                    discovered = self.DFS(v, discovered)

            return islands

        else:
            return islands

    def DFS(self, v, discovered = []):

          if not v in discovered:

            discovered.append(v)
            vx, vy = v

            adjacent = [(vx-1, vy), (vx, vy-1), (vx+1, vy), (vx, vy+1)]

            for adj in adjacent:

                if not adj in discovered:
                    adjx, adjy = adj

                    if adjx < self.m and adjy < self.n and adjx >= 0 and adjy >= 0:

                        if self.grid[adjx][adjy] == "1":
                            self.DFS(adj,discovered)

            return discovered



    def indexislands(self):

        indislands = deque([])

        for m in range(self.m):
            for n in range(self.n):
                if self.grid[m][n] == "1":
                    indislands.append((m,n))

        return indislands

DFS을 이용해서 "연결된 땅"을 정의하고자 했다.

1. 그래프 최상단 노드 구하기 : 주어진 리스트에서 1로 적힌 값의 index를 구함.
2. 그래프 최상단 노드에서 각각 DFS 진행 DFS 진행 시 좌우상하 4가지 노드를 연결노드로 진행.

결과는 Time over.. 1번의 과정을 생략하면 통과할 수 있을 것 같다. 주어진 리스트에서 1로 적힌 노드부터 DFS를 진행하여 마지막 m-1, n-1 값까지 searching 하는 것이다.

나의 코드에서는 discovered 라는 리스트로 탐색 구역을 저장했는데, "1" -> "0"으로 변경하면서 탐색 구역을 체크하는 것이 좋을 것 같다 (저장 공간 절약)

Tip. 네 방향 각각 DFS 재귀를 사용하자. (파이썬 알고리즘 책 p.332) -> 왼쪽으로 탐색하는 DFS, 오른쪽으로 탐색하는 DFS, 등..

24-06-22

N = int(input())

max_range = 0
money_list = []

for money in input().split(" "):
  money = int(money)
  max_range = max(money, max_range)
  money_list.append(money)

deposit = int(input())

if sum(money_list) <= deposit:
  print(max_range)

else:
  condition = True
  small_range = int(deposit/N)
  max_range = min(max_range, deposit)

  while(condition):

    expectation, total = int((small_range + max_range)/2), 0

    for money in money_list:
      if money < expectation:
        total += money
      else:
        total += expectation

    if (total == deposit):
      condition = False

    elif total < deposit:
      small_range = expectation
      if max_range - small_range < 2:
        condition = False

    elif total > deposit:
      max_range = expectation

  print(expectation)

이분 탐색으로 잘 풀었지만, 코드의 가독성을 높힐 필요가 있다.

1. while(left <= right): 로 작성하자. 해당 구문을 사용하면 다른 작성자가 이분 탐색을 사용했구나 하고 읽기가 편하다.
2. middle = (left + right) // 2
3. left = middle + 1 또는 right = middle - 1 을 사용하여 무한 루프가 도는 것을 방지하자.

240615

from collections import deque

N = int(input())

if N == 1:
  print(1)

else:
  cards = deque(list(range(1, N+1)))

  while len(cards) > 1:
    discard = cards.popleft()
    topcard = cards.popleft()
    cards.append(topcard)

  print(cards[0])

위 코드는 244ms 의 런타임이 소요되었다.

240615 (2)

from collections import deque

N = int(input())

if N == 1:
  print(1)

else:
  cards = deque(list(range(1, N+1)))

  for _ in range(1, N):
    discard = cards.popleft()
    cards.append(cards.popleft())

  print(cards[0])

위 코드는 152ms 런타임이 소요되었다.

두 코드의 가장 큰 차이는 for/while 문 사용 차이이다. while의 경우 condition 문을 N-1번 계산해야하기 때문에 시간 소요가 커진다. 주어진 카드 개수에서 마지막 남은 카드 개수가 1개라는 점을 생각해보면, 버리는 행위는 N-1번으로 정해져 있다는 것을 알 수 있다. 따라서 이번 문제에서는 for문 사용이 적합하다

연결 리스트가 팰린드롬 구조인지 판별

240110

리스트를 만들어 q.pop(0) != q.pop() 를 이용해 팰린드롬 구조를 판별하였으나 시간이 1220ms로 느린편이다. 이는 리스트의 경우 pop(0) 진행 시 모든 값이 한칸씩 시프팅 되기 때문에 시간 복잡도가 O(n)으로 발생하기 때문이다.

1. 양방향 모두 O(1)이 가능한 데크를 사용하자 collection.deque()

2. != None 보다 is not None이 더 빠르다

3. input이 []일 때도 고려하자

4. 위 1~3 해결 후, 런너 기법 & 다중 할당 & 연결 리스트를 활용하여 문제해결하자 (p.210)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        number_list = []

        while head.next != None:
            number_list.append(head.val)
            head = head.next

        number_list.append(head.val)

        while len(number_list) > 1:
            if number_list.pop(0) != number_list.pop(-1):
                return False

        return True

22-06-02

BFS가 뭐지..?

Next what to do.

1. from collections import deque 활용 while queue 가 포인트라고 생각함.!

23-08-16

BFS로 해결! <- 검색함..

import numpy as np
from collections import deque


candi_matrix =[]
n,m = 7,7

for i in range(n):
    candi_matrix.append(list(input().split(" ")))

Graph = {}

for i in range(n):
    for j in range(m):

        node = candi_matrix[i][j]

        connected_nodes = []
        if i > 0:
            if candi_matrix[i-1][j] == node:
                connected_nodes.append((i-1,j))
        if j > 0:
            if candi_matrix[i][j-1] == node:
                connected_nodes.append((i,j-1))
        if i < n-1:
            if candi_matrix[i+1][j] == node:
                connected_nodes.append((i+1,j))
        if j < m-1:
            if candi_matrix[i][j+1] == node:
                connected_nodes.append((i,j+1))

        if len(connected_nodes)>0:
            Graph[(i,j)] = connected_nodes

 def bfs(G, start_point):
    visited = list() # 방문한 노드를 담을 배열
    queue = list() # 방문 예정인 노드를 담을 배열

    queue.append(start_point) # 처음에는 시작 노드 담아주고 시작하기.

    while queue: # 더 이상 방문할 노드가 없을 때까지.
        node = queue.pop(0) # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            queue.extend(Graph[node]) # 해당 노드의 자식 노드로 추가

    #print("bfs - ", visited)

    return visited

visited_nodes = []
candi_pop = 0
while len(visited_nodes) < len(Graph.keys()):


    start_point = list(set(Graph.keys())- set(visited_nodes))[0]
    connected_nodes = bfs(Graph,start_point)

    if len(connected_nodes) >= 3:
        candi_pop += 1

    visited_nodes += list(set(connected_nodes) & set(Graph.keys()))

print(candi_pop)

Next what to do

1. BFS 검색없이 사용!

22-05-30

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        buy = 10000
        profit = 0
        n = len(prices)
        for i in range(0,n,2):
            if i == n-1:
                profit = max(profit,prices[i]-buy)
            else:
                j = i + 1
                profit = max(profit,prices[j]-prices[i],prices[j]-buy,prices[i]-buy)
                buy = min(buy,prices[i],prices[j])
            print(profit)
        return profit

인덱스 두 개를 사용하여 시간 복잡도를 줄이고자 하였다. 1475ms로, 아쉬운 성능.

Next what to do.

1. 70ms 이하로 줄일 수 있다!

24-10-20

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        n = len(prices)

        if n == 1:
            return 0

        buy, profit = 10**(4), 0
        for i in range(n-1):
            buy = min(buy, prices[i])
            profit = max(profit, prices[i+1]-buy)

        return profit

O(n)으로 해결함 run time - 114ms

이전 코드 보완 사항

• n == 1 예외 처리 진행
• min & max 사용 간소화

Run time을 더 줄이고 싶다면?

• len(prices)를 사용하지 않고 진행하면 시간이 더 줄 수 있음

• 단, 나눗셈을 하지 않고 O(n)에 풀이하시오.

22-05-30

import numpy as np

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        answer = np.array([1]*len(nums))
        for i,n in enumerate(nums):
            multiplication = answer*n - answer
            multiplication[i] = 0
            answer += multiplication

        return answer

array로 각 원소의 곱만큼 더하기 방식으로 진행했다. 단, 해당 원소는 0을 더함으로 조건을 만족하였다. 하지만, Time Out. ㅎㅎ array 자체로 계산하는 것이 O(n)...

Next to do.

1. 왼쪽 곱셈에 결과에 오른쪽 값을 차례대로 곱셈하는 방식으로 풀자

24-09-11

import numpy as np 
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        n = len(nums)

        answer = np.array([1]*n)

        for i, num in enumerate(nums):

            backup = answer[i]
            answer *= num
            answer[i] = backup

        return answer

자기 자신에 해당하는 인덱스만 backup으로 남겨둔 후, 어레이의 모든 값에 숫자를 곱함. 그 이후 해당 인덱스에 backup 값으로 다시 대체함.

Next What to Do

1. 2*O(n) 으로 푼다고 생각
2. 정방향 O(n) + 역방향 O(n)

22-05-30

fail.. 스택쌓기로 풀었는데, 잘 안됨..

Next what to do

1. 투 포인터 사용 ''' So, we can set 2 pointers left_max,right_max and check which side is greater,if one side is greater iterate on other side because at the min side the water will be filled at its limit. and iterate till pointer is lower than the other one. '''
2. 1번 성공 시, 스택쌓기 재도전

24-09-10

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        if len(height) < 2 or min(height) == max(height):
            return 0

        water_left, water_right = [], []
        top_height_left, top_height_right = height[0], height[-1]

        for i in range(1,len(height)):

            left_gap,right_gap = top_height_left-height[i],top_height_right-height[len(height)-i]

            water_left.append(max(left_gap, 0))
            water_right.append(max(right_gap,0))

            top_height_left, top_height_right = max(top_height_left, height[i]), max(top_height_right, height[len(height)-i])

        water = 0
        for i in range(len(height)-1):
            water += min(water_left[i], water_right[len(height)-1-i-1])

        return water

1. 왼쪽으로 슬라이딩 하면서 가장 높은 벽과 현재 벽의 차이 구함.
2. 오른쪽으로 슬라이딩 하면서 1번과 유사하게 구함.
3. 1번과 2번의 산출된 값 중에 작은 값이 water 높이임.

Next what to do 좌우 포인터가 가운데로 점점 이동하여 만난다는 방향으로 코드 작성하기

22-05-25

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)

        for i in range(n-1):
            for j in range(0,i+1):
                ss = s[j:n-i+j]
                if ss == ss[::-1]:
                    return ss

        return s[0]

Time Limit Exceeded 현재 코드 계산량은 $n(n-1)/2.$ abcdef.(중략).xx 이런 경우, xx를 찾기위해서 $O(n^2)$의 작업을 해야함.

Next what to do

1. 짝수(2)-홀수(3) 투 포인터 사용
2. 작은 단위에서 확장하는 방식으로 코드 짜기

24-09-10

class Solution(object):


    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        def findPalindrome(s):
            if s == s[::-1]:
                return True
            else:
                return False

        def updatepalindrome(s, start, end, condition = True):

            while (start > 0) and (end < n) and condition:
                if findPalindrome(s[start-1:end+1]):
                    start -= 1
                    end += 1
                else:
                    condition = False

            return start, end

        def searchingPalindrome(s, start, end, palindrome): 

            if findPalindrome(s[start:end]): 
                updated_start, updated_end = updatepalindrome(s, start, end)

                palindrome = s[updated_start:updated_end] if len(palindrome) < (updated_end-updated_start) else palindrome

            return palindrome

        n = len(s)

        if n < 2:
            return s

        palindrome = s[0]

        for i in range(n-1):

                # even searching
                start, end = i, i+2
                palindrome = searchingPalindrome(s, start, end, palindrome)

                # odd searching
                start, end = i, i+3
                palindrome = searchingPalindrome(s, start, end, palindrome)

        return palindrome

1. input 길이가 2보다 짧은 경우, 예외 처리 진행
2. output을 주어진 인풋의 첫번째 글자로 시작함.
3. 첫번째 글짜부터 길이가 짝수인 팰린드롬, 홀수인 팰린드롬을 확인하여 output에 업데이트 함.

Next what to do

1. 빠르게 리턴하는 부분에서 한 글자인 경우, 전체 글자가 팰린드롬인 경우로 처리하자.
2. 코드 가독성 높히기
   • palindrome = max(palindrome, searchingPalindrome(i, i+2), searchingPalindrome(i, i+3), key=len)
   • line이 30줄 넘지 않도록 작성하자
3. 주의) 슬라이싱과 인덱스 조회에는 차이가 있다. 이를 잘 고려해서 작성할 것.

22-05-25

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        answer = dict()
        for str_ in strs:
            sort_str = ''.join(sorted(str_))
            if sort_str in answer.keys():
                answer[sort_str].append(str_)
            else:
                answer[sort_str] = [str_]

        return answer.values()

• Runtime: 2817ms
• Memory: 17.2MB

Next what to do

1. collections.defaultdict(list)를 이용하여 KeyError를 해결하자. <- key 있는지 확인하는 것 자체가 시간이 오래 걸림

24-06-29

import collections 
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        anangram = collections.defaultdict(list)
        for word in strs:
            key = ''.join(sorted(word))
            anangram[key].append(word)

        return anangram.values()

이전코드에서 collections.defaultdict(list) 사용을 추가함. 런타임은 63ms로 1/4 가량 줄어듦. 현업에서도 collections.defaultdict()는 많이 사용하면 좋을 듯!

22-05-25

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.lower()
        alphanumeric = 'abcdefghijklmnopqrstuvwxyz0123456789'
        processed_s = ''.join([alpha for alpha in s if alpha in alphanumeric])
        n = len(processed_s)

        for i in range(int(n/2)):
            if processed_s[i] != processed_s[n-1-i]:
                return False
        return True

• Runtime: 58ms
• Memory: 15.5MB

Next what to do.

1. 정규식 사용하여 전처리 진행
2. 슬라이싱을 이용하여 팰린드롬 확인하기

24-06-29

[::-1] 로 string을 거꾸로 뒤집을 수 있다.

22-05-24

N = int(input())
ropes = sorted([int(input()) for _ in range(N)],reverse = True)

answer = 0
while(ropes):
    answer = max(answer,ropes[-1]*len(ropes))
    ropes.pop()

print(answer)

Time cost가 있음 왜일까~ max = O(n)이기 때문에 루프안에서 max 사용하는 것이 좋지 않음

24-06-21

import sys

N = int(input())

rope_list = {}
for _ in range(N):
  rope = int(sys.stdin.readline())
  if rope in rope_list.keys():
    rope_list[rope] += 1
  else:
    rope_list[rope] = 1

sorted_rope_list = sorted(rope_list, reverse = True)

big_rope = sorted_rope_list[0]
n_rope = rope_list[big_rope]
answer = big_rope * n_rope
for key in sorted_rope_list[1:]:
  n_rope += rope_list[key]
  answer = max(answer, key*n_rope)

print(answer)

import sys sys.stdin.readline() 으로 input을 받으면 속도가 많이 개선된다!

22-05-24

N = int(input())
alphabet,count_apb = ['']*9,''
for _ in range(N):
    for i,a in enumerate(input()[::-1]):
        alphabet[8-i] += a
        count_apb += a*(i+1)

answer,number_hash,number = 0, {}, 9
for i,apb in enumerate(alphabet):
    for a in sorted(apb,key = lambda x : count_apb.count(x), reverse = True):
        if a not in number_hash.keys():
            number_hash[a] = number
            number -= 1
        answer += number_hash[a]*(10**(8-i))

print(answer)

fail.. 단어가 위치한 자리가 높은 십의 자리일 수록 높은 숫자를 부여하는 코드를 작성

반례) ABB/ BB 9회 반복 A : 8 B : 9

24-06-21

N = int(input())

char = {}
for _ in range(N):

  input_char = input()
  digits = len(input_char) # 자리수 확인

  for ic in input_char:
    if ic in char.keys():
      char[ic] += 10**(digits-1)
    else:
      char[ic] = 10**(digits-1)

    digits -= 1

sorted_char = sorted(char, key = lambda x: char[x], reverse = True)

answer = 0
iter = 0
for alphabet in sorted_char:
  answer += char[alphabet]*(9-iter)
  iter += 1

print(answer)

key point는 알파벳마다 자리수를 고려해 모두 더하고 더한 값의 대소를 비교하여, 가장 큰 값을 가진 알파벳부터 9를 부여하는 것이다. AAA / BAC 이렇게 인풋이 주어진 경우, A = 100 + 10 + 1 + 10 = 121, B = 100, C = 1 이므로 A, B, C 순으로 9,8,7을 부여하여 9121 + 8100 + 7*1 의 답을 리턴한다.