인간 같은 원숭이

1. 연구 배경 및 문제 정의

• 초분광 이상탐지(Hyperspectral Anomaly Detection, HAD) 은 사전 레이블 없이 배경으로부터 이상 픽셀을 식별하는 과제다. 기존 통계적(RX, 2S-GLRT 등)·표현학습·오토인코더 기반 기법은 국지적(로컬) 특징 또는 전역(글로벌) 특징 중 한쪽에 편향되거나, 중심 픽셀 정보가 포함되어 블라인드-스팟 조건을 만족하지 못해 재구성 오류 기반 탐지력에 한계가 있었다.

1.1 블라인드 스팟  조건

기존 오토인코더(AE) 기반 이상 탐지에서는 입력의 픽셀을 재구성할 때 입력과 출력이 1:1 대응되며, 전체 정보를 모두 활용해 해당 위치를 복원함. 이 경우, 모델이 이상(target anomaly) 을 직접 보고(referencing) 복원하는 문제가 발생하여,

➤ 이상인 영역도 정상처럼 잘 재구성되는 현상이 발생하고
➤ 결과적으로 이상 탐지력이 약화됨

이를 해결하기 위해 self-supervised 방식에서는 중심을 마스킹(Masking) 하거나 블라인드 필터(Blind convolution) 를 이용해 입력 중심정보를 완전히 차단한 뒤,

주변 정보만으로 중심을 유추하도록 모델을 학습시킴

블라인드-스팟 조건이란, 중심 픽셀을 전혀 사용하지 않고 주변 정보만으로 복원하도록 설계된 self-supervised 재구성 조건. 이 조건을 만족해야만 재구성 오류 기반 이상 탐지에서 높은 민감도를 확보할 수 있으며, PUNNet은 이를 전제로 설계된 구조임

2. 핵심 기여

1. Patch-Shuffle Downsampling(PD) 으로 입력을 공간적으로 재배열해 큰 이상물의 공간 상관을 분산, 블라인드-스팟 네트워크에 적합한 형태로 변환.
2. NAFNet Block + Dilated Conv: 비선형 활성화가 없는 복원 전용 NAFNet 블록에 딜레이티드 DW-Conv와 채널 어텐션(SCA) 을 삽입, 글로벌 문맥을 효율적으로 주입.
3. 위 두 모듈을 기존 PDBSNet 블라인드-스팟 구조에 통합해 PUNNet 을 제안—로컬·글로벌 공간-분광 정보를 동시에 활용하면서도 중심 픽셀은 보지 않는 self-supervised 재구성을 달성.

3. 네트워크 아키텍처 (Fig. 1, 2)

단계 주요 구성 설명·의의

4. 실험 설정

• 데이터셋: AVIRIS 공항(HSI-I), ROSIS 해변(II), AVIRIS 도시(III), Gaofen-5 위성 항만(IV) — 총 4개 실환경 장면.
• 비교 방법: 전통(GRX, 2S-GLRT, CRD) 3종 + DL(GAED, RGAE, Auto-AD, PDBSNets) 4종.
• 평가지표: ROC, AUC, 추론시간.

1. ROC (Receiver Operating Characteristic) Curve

● 정의

ROC 곡선은 True Positive Rate (TPR) 와 False Positive Rate (FPR) 간의 관계를 시각적으로 표현한 곡선

● 의미

• FPR이 낮을수록 오탐이 적음.
• TPR이 높을수록 이상 검출이 잘됨.
• 좌상단(0,1)에 가까운 곡선일수록 이상탐지 성능이 우수함.

● 논문 내 해석

• 논문 Fig. 4에 4개 장면에 대한 ROC 곡선이 시각화되어 있음.
• PUNNet이 모든 장면에서 가장 위쪽에 위치, 오탐은 적고 탐지는 잘하는 구조임을 시사함.

2. AUC (Area Under Curve)

● 정의

• ROC 곡선 아래 면적(Area Under the ROC Curve)을 0~1 사이 값으로 정량화한 지표.
• AUC가 1.0에 가까울수록 모델이 이상과 배경을 잘 분리한다는 의미.

● 의미

• AUC = 1.0: 완벽한 이상탐지
• AUC = 0.5: 랜덤 추측과 동일 (쓸모없는 모델)

● 논문 내 수치 (Table I)

• PUNNet: 평균 AUC = 0.97
• 기존 모델(Auto-AD, PDBSNets 등) 대비 1~2%p 향상
• 특히 복잡한 장면(AVIRIS 도시, Gaofen-5 항만)에서도 우수한 성능 유지

지표 정의 PUNNet 결과 및 해석

📌 이 3가지 지표는 초분광 이상탐지 모델 평가에 있어 정확도 + 효율성을 동시에 고려할 수 있게 해주며, 특히 hsi_auto 같은 실무 프로젝트에서는 ROC-AUC만 보는 것이 아니라 속도와 실제 운영 조건까지 고려한 판단이 중요합니다.

5. 주요 결과 (Fig. 3, 4, Table I)

데이터 GRX 2S-GLRT CRD GAED RGAE Auto-AD PDBSNets PUNNet

• 시각적 품질: Fig. 3에서 붉은 이상 타깃이 PUNNet(열 (j))에서 가장 선명·배경억제 우수.
• ROC: 네 장면 모두 PUNNet 곡선이 최상단—검출·오경보 균형 우수.
• 추론시간: 추가 업/다운샘플링으로 PDBSNets 대비 소폭 증가하지만(약 0.1 s↑), MATLAB 기반 전통 알고리즘 대비 여전히 빠름.

6. 파라미터·어블레이션 (Fig. 5, Table II)

• Stride Size ss: 2-5 범위 실험 결과 AUC 안정적(>0.98).
• 요소 기여:
  • PUNNet w/o P(패치-셔플 제거): AUC ↓0.01-0.02
  • PUNNet w/o N(NAFNet→단순 dilated Conv): AUC ↓0.02-0.03
    → 두 모듈 모두 성능 향상에 필수.

7. 강점·한계 및 실무 적용 시사점

강점 한계

9. 결론

PUNNet은 Patch-Shuffle + NAFNet을 통해 블라인드-스팟 self-supervised 초분광 이상탐지의 전역 정보를 보강한 최신 모델이다. 실험적으로 기존 PDBSNets 대비 평균 AUC +1.5 %p, 명확한 시각적 개선을 달성했으며, hsi_auto 파이프라인에 통합하면 레이블 의존도를 획기적으로 낮추면서도 성능을 향상시킬 수 있다.

1. 연구 목적

• 문제 정의: 기존 HSI 분류 모델(CNN, Transformer)은 스펙트럼-공간 정보의 전역 표현(long-range dependency)을 효과적으로 처리하지 못하거나 계산 복잡도(특히 Transformer의 O(N²))가 높음.
• 연구 목표: 선형 시간 복잡도로 공간/스펙트럼 정보를 효과적으로 처리할 수 있는 모델 설계.

2. 제안 모델: S2Mamba

Mamba 기반 Selective State Space Model(SSM)**을 활용해 공간-스펙트럼 정보를 동시에 모델링.

모델 전체 구조:

입력: HSI patch (크기: P×P×K)
→ 1×1 Conv (D차원 임베딩)
→ PCS 모듈 (Patch Cross Scanning, 공간 정보)
→ BSS 모듈 (Bi-directional Spectral Scanning, 스펙트럼 정보)
→ SMG 모듈 (Spatial-Spectral Mixture Gate, 융합)
→ FC → Class Prediction

3. 각 모듈 상세

 3.1. PCS (Patch Cross Scanning)

• 목적: 인접 픽셀 간 공간 문맥 추출
• 방법:
  • 입력 패치를 1D 시퀀스로 변환 (위→아래, 아래→위, 좌→우, 우→좌 총 4방향)
  • 각 시퀀스에 Mamba 기반 selective scan 수행
  • 출력은 4방향 정보를 통합한 공간 표현 텐서 Y ∈ ℝ^(P×P×D)

3.2. BSS (Bi-directional Spectral Scanning)

• 목적: 연속 스펙트럼 밴드 간 의미적 흐름 파악
• 방법:
  • 공간 차원을 평탄화한 후 스펙트럼 축 K 방향으로 양방향 scan
  • Spectral sequence → Selective scan 적용
  • 출력: 스펙트럼 표현 텐서 P ∈ ℝ^(P×P×D)

3.3. SMG (Spatial-Spectral Mixture Gate)

• 목적: 공간/스펙트럼 특징을 픽셀 단위로 동적 융합
• 방법:
  • 공간 표현 Y와 스펙트럼 표현 P를 softmax 기반으로 가중합
  • 위치별로 gate weight M̃ ∈ ℝ^(P×P×2) 생성
  • Threshold τ=0.1 적용해 의미 없는 특징 제거

4. 실험 결과

Indian Pines (16 classes)

• S2Mamba: OA = 97.92%, AA = 98.88%, κ = 0.9761
• 기존 최고 모델(GraphGST) 대비 +0.86% 향상
• 파라미터 수: 0.12M

Pavia University (9 classes)

• OA = 97.81%, 기존보다 +6.74% 향상
• 복잡한 도시경관(텍스처 다양)에도 강한 성능

Houston 2013 (15 classes)

• OA = 93.36%, Transformer 기반 모델 대비 +2.56%

추가 지표:

• 훈련 시간:
  • Indian Pines 기준 SpectralFormer 대비 약 33% 단축
• 모델 크기:
  • Transformer 대비 4~8배 작음

5. Ablation Study

조합 Indian Pines (OA) 설명

6. 장점 요약

항목 설명

한계 및 개선점

항목 한계점

결론

S2Mamba는 Mamba 기반 selective scan 구조를 초분광 이미지 분류에 최초 적용한 모델로,

• 공간-스펙트럼 정보 통합
• 계산량 최적화
• 높은 정확도
  를 동시에 달성.

산업용 HSI 분류 시스템에 실시간/임베디드 적용 가능한 수준의 경량 모델로 추천 가능.

링크:

https://github.com/TheSole0/S2Mamba-HSI-lineScanCam?tab=readme-ov-file

1. 개요 및 문제 정의

배경

S2Mamba는 Spectral-Spatial Multi-Head Attention Mamba Network로, 최근 제안된 Mamba 구조의 장점을 활용하여 초분광 영상(Hyperspectral Imaging, HSI)의 스펙트럼-공간 정보를 동시에 처리하기 위한 경량 구조. 본 프로젝트에서는 이를 이상 탐지(Anomaly Detection) 및 결함 분류(Classification)에 적용하여, 복잡한 산업 표면에서 결함을 신속하고 정확하게 판별하는 목적을 가짐.

문제 정의

• HSI 데이터는 채널 수(예: 224 bands)가 많아 고차원 처리에 어려움이 있으며, 결함 클래스의 수가 적고 데이터 불균형이 심함
• 기존 CNN은 국소 패턴 위주로 처리하며, 전역 스펙트럼 연산을 반영하기 어려움
• 기존 Transformer 기반 구조는 메모리 과다 소모 및 추론 속도 저하 문제 존재

2. 접근 방법: S2Mamba 모델 설계 및 적용

구조 개요

• 입력: (B, C=224, P, P) 형태의 HSI patch
• 모델: Mamba 기반 attention block 1개(depths=[1]), embedding dim=64
• 출력: 클래스 수에 따른 로짓 (CrossEntropy 기반 분류)

HSI 전처리

• white/dark reference 보정
• label remap (1: 정상, 2: DW, 3: DA, 4: 기타 → 0~3 재맵핑)
• patch 기반 패치 추출 (P=7), 클래스별 max 1000개 샘플링

훈련 방식

• 다중 샘플 학습 지원 (여러 capture 폴더 병합)
• 클래스 불균형 대응을 위한 inverse weight 기반 CrossEntropyLoss 적용
• ExponentialLR 스케줄러 적용

3. 구조

4. 성능 평가 및 시각화

• [예시 결과]
  • OA=0.9995, AA=0.9568, Kappa=0.8015
  • 소수 클래스(DW, DA)에 대한 과적합 방지 및 generalization 확인됨

5. CLS-DL1 / CLS-DL2와의 차이점

6. S2Mamba 장단점 정리

 

항목설명

✅ 장점	경량 구조로 빠른 추론 / 고차원 입력에서의 효율적 attention 처리 / Transformer 대비 메모리 사용량 적음
⚠️ 단점	단일 depth 구조에서는 공간 정보 활용이 제한적 / 대규모 시계열 처리에는 부적합 / 고정 파라미터 구조로 task에 따라 최적화 필요

https://school.programmers.co.kr/learn/courses/30/lessons/86491

def solution(sizes):
    temp = []
    for i, j in sizes:
        if i >= j :
            temp.append([j,i])
        else:
            temp.append([i,j])
            
    wi, hi = sorted(temp, reverse=True), sorted(temp, key=lambda x:x[1], reverse=True)
    
    return wi[0][0] * hi[0][1]

https://school.programmers.co.kr/learn/courses/30/lessons/42840

n1 = [1, 2, 3, 4, 5] * 2000
n2 = [2, 1, 2, 3, 2, 4, 2, 5] * 1250
n3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000

def solution(answers):
    
    c1,c2,c3 = 0,0,0
    for i1,i2,i3,ans in zip(n1, n2, n3, answers):
        if i1 == ans: c1 += 1          
        if i2 == ans: c2 += 1           
        if i3 == ans: c3 += 1
    
    result = [c1,c2,c3]
    maxi = max(result)
    answer = []
    
    for i, j in enumerate(result):
        if maxi == j:
            answer.append(i+1)
            
    return answer

깔끔한 예시 정답코드

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

• score 하나로 변수 3개 쓸필요가 없다는 점
• " if answer == pattern1[idx%len(pattern1)]" 이유는
  • pattern 들마다 순환주기가 다르니까 각각 순환주기로 나눠준것
  • 7%4 -> 나머지 3이지만
  • 1 % 5 ->  1,  2%5 -> 2,  3%5 -> 3, 4%5 -> 4, 5%5 -> 0 이렇게 남는다
  • 이를 통해 내가 직전에 짠 코드처럼 *1000 이렇게 할필요가 없어짐

https://school.programmers.co.kr/learn/courses/30/lessons/42839

• 순열 문제
• "".join(i) -> 튜플과 리스트를 일반 문자열 또는 숫자형태로 변환 무조건 외워야됨!
• 두번 째 "from itertools import permutaions" 라이브러리 또한 순열을 위해서 외워야됨

1. 순열의 조합 찾음 -> 소수 찾기

from itertools import permutations

def permutation(x):
    # 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수
    if x < 2: # 연산속도 줄이기 위함?!
        return False
    else:
        for tt in range(2, x):
            if x % tt == 0:
                return False
    return True

def solution(numbers):
    count = 0
    test_case =[]
    
    for i in range(len(numbers)):
        data = list(permutations(numbers, i+1)) # 1자리수 2자리수 전부 조합
        rdata = list(set(map("".join, data))) # 중복제거 및, 튜플에서 리스트 형태 변환
        for j in rdata: # 개별로 리스트에 정수로 추가
            test_case.append(int(j))
    
    test_case = list(set(test_case)) # 재중복 체크
    for t in test_case: # 개별적으로 소수인지 아닌지 체크
        if permutation(t) == True:
            count += 1 # 소수면 count+=1
    return count

https://school.programmers.co.kr/learn/courses/30/lessons/42842

더보기

어떤 수를 나누어떨어지게 하는 수를 그 수의 약수라고 합니다.

8을 1, 2, 4, 8,로 나누면 나누어떨어집니다.

1, 2, 4, 8은 8의 약수입니다.

[출처] [5-1][1. 약수와 배수] 약수란? 배수란? (구체물로 개념 익히세요~)|작성자 세가지소원

https://siloam72761.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EC%B9%B4%ED%8E%AB

 

[프로그래머스][Python] 카펫

1. 문제설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의

siloam72761.tistory.com

 

def solution(brown, yellow):
    answer = []

    # 10, 2
    for i in range(1,yellow+1): # 3 -> 0,1,2 
    	#yellow의 약수를 이용해 row를 더 길게 설정한다.
        if(yellow % i ==0): # i가 2일 때
            yellow_row = (yellow /i) # 1.0
            yellow_col = i # 2
            if (2 * (yellow_row + yellow_col) + 4 == brown): # (2 * (1.0 + 2) + 4 == 10)
                return [yellow_row +2, yellow_col+2]

https://school.programmers.co.kr/learn/courses/30/lessons/87946

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    
    for permute in permutations(dungeons, len(dungeons)):
        count = 0
        hp = k
             
        for pm0, pm1 in permute:

            if hp >= pm0:
                count += 1
                hp -= pm1
                       
        answer = max(count, answer)
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42748

def solution(array, commands):
    answer = []
    
    for i, j ,k in commands:
        temp = array[i-1:j]
        temp.sort()
        answer.append(temp[k-1])
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42746

def solution(numbers):

    strn = list(map(str, numbers))
    sr1 = sorted(strn, key=lambda x:x*3,reverse=True)
    result = str(int(''.join(sr1))) # -> 리스트 탈출 시 유용할듯
    
    return result

• int(''.join(sr1)) -> 리스트 제거 시 엄청 유용한듯.
• key=lambda x:x*3 -> 자기 자신을 3번 곱해줌 ex) str3 -> 333

https://markdung.tistory.com/manage/newpost/303?type=post&returnURL=https%3A%2F%2Fmarkdung.tistory.com%2Fmanage%2Fposts

def solution(citations):
    citations.sort(reverse=True)
    
    for idx , citation in enumerate(citations): # 0부터 가져가면 이전 인덱스를 계속비교할 수 있음 즉 더쉽게 비교가능
        print(idx , citation)
        if idx >= citation:
            return idx
    return len(citations) # 예외처리라 보면 될듯

https://school.programmers.co.kr/learn/courses/30/lessons/1845.

# my -> pass
from collections import deque

def solution(nums):
    q = deque(nums)
    result = []
    
    while len(q) != 0:
        data = q.popleft()
        if data in result:
            continue
        else:
            result.append(data)
            
    if len(result) >= len(nums) //2: 
        return len(nums) //2
    else:
        return len(result)

# 다른 사람이 짠거
# set을 사용하면 자동으로 줄여주니까

def solution(ls):
    return min(len(ls)/2, len(set(ls)))

https://school.programmers.co.kr/learn/courses/30/lessons/42576

# 출력문 문제로 작동이 안됨;
from collections import deque


def solution(participant, completion):
    p, c = deque(participant), deque(completion)
    has = {}
    
    # while len(p) != 0:
    for i in range(len(p)):
        player = p.popleft()
        if player in c:
            c.remove(player)
        else:
            p.append(player)
    
    s = list(p)
    has[1] = s[0]
    print(has.values())

def solution(participant, completion):
    participant.sort()
    completion.sort()
    print(participant, completion)
    for i, j in zip(participant, completion):
        if i != j:
            return i
        
    return participant[-1]

• "return participant[-1]" 하는 이유

• 만일 순차적으로 전부 다 확인했는데 뒤에 complection 기준으로 끝나면 participant의 마지막 사람이 들어온 사람이기 떄문.

# 이게 문제 출제의 의도인 것 같음

def solution(participant, completion):
    data = {}
    h_val = 0
    for i in participant:
        data[hash(i)] = i
        h_val += hash(i)
    for j in completion:
        h_val -= hash(j)

    return data[h_val]

• 해시 함수는 임의의 값을 고정된 길이의 데이터로 변환하는 함수임.
  • 즉 딕셔너리를 생성  및 변환된 해시의 값을 알기위한 h_val 생성 ->  data, h_Val
  • 처음 참가자들을 확인하면서 딕셔너리에 각각의 해시값을 입력함. -> data[hash(i)] = i
  • 완주자와 비교하기 위해 h_val에 추가한 해시값을 전부다 sum함
  • 이후 완주자(complection)의 값에 해시값을 하나씩 뺴주면서 마지막에 남은 h_val의 해시값을 기존에 추가하였던 data 딕셔너리에서 불러옴
  •  

더보기

https://school.programmers.co.kr/learn/courses/30/lessons/42577

# startswith
def solution(phone_book):
    phone_book.sort()
    for i, j in zip(phone_book, phone_book[1:]):
        if j.startswith(i):
            return False
    return True

• 정렬하고 start Swith 함수를 사용한다 -> 앞 뒤랑 비교를 하는데 만일 뒤에 문자 기준으로 j.starswith(i)를 사용하면 문자 시작이 i 기준으로 시작했을 때 True로 반환하므로 False로 처리

# 해시를 사용한 문제

def solution(phone_book):
    phone_book.sort()
    answer = True
    dic = {}
    for i in phone_book:
        dic[i] = 1
    for j in phone_book:
        temp = ""
        for nums in j:
            temp += nums
            print(dic, temp, j)
            if temp in dic and temp != j:
                return False
    return answer

• 처음 딕셔너리에 전부 다 추가-> dic = {}
• 이후에 폰북에서 하나씩 전화번호를 꺼내고 이후 꺼낸 전화번호를 하나씩 비교하기 시작함
  • "temp" 라는 값에 번호를 개별적으로 대입하고 이 때 현재 딕셔너리에 존재하는지를 비교함
    • 즉 "if temp in dic" 
    • 또한 위에 상태로 두면 자기 자신의 번호랑 비교하므로 조건을 추가함
    • "and temp != j" 
    • "if temp in c and temp != j"

https://school.programmers.co.kr/learn/courses/30/lessons/42578

# 해시를 사용한 정석적인 문제
def solution(clothes):
    dic = {}
    for _, t  in clothes:
        if t not in dic:
            dic[t] = 2
        else:
            dic[t] += 1
    cnt = 1
    for i in dic.values():
        cnt *= i
    return cnt -1

• 처음에 딕셔너리 값에 전부 저장함. # int는 저장되는데 str은 저장 안됨
  • "dic[t] = 2"를 해준이유는 이후 확률 계산을 할 때 (본인 입었을 때, 안입었을 때)를 위해서 미리 2를함
    • 위처럼 아니면 "dic[t] = 1"로 두고 아래서 "cnt *= i+1" 해도 상관은 없음
  • 이후 values 값만 불러와서 확률 계산
    • ex) 3 * 2 
    • 이 때 마지막 리턴 값은 -1을 해줌.

https://school.programmers.co.kr/learn/courses/30/lessons/42579

더보기

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예genresplaysreturn

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

def solution(genres, plays):
    answer = []

    dic1 = {} # 가장 많이 재생된 장르
    dic2 = {} # 장르 내 많이 재생된 노래 수록
    
    for i, (g,p) in enumerate(zip(genres, plays)):
        if g not in dic2:
            dic2[g] = p
        else: dic2[g] += p
        
        if g not in dic1:
            dic1[g] = [(i,p)] # 리스트로 선언해줘야함
        else:
            dic1[g].append((i,p))
            
    s_dic2 = sorted(dic2.items(), key=lambda x:x[1], reverse = True)

    for k,_ in s_dic2: # 순차적으로 확인하는 거임 pop -> classic
        s_dic1 = sorted(dic1[k], key=lambda x:x[1], reverse = True)[:2]
        for i,_ in s_dic1:
            answer.append(i)
   
    return answer

• 개인적인 생각으로는 구현문제에 가까움
• 처음 dic1, dic2 생성 -> 가장 많이 재생된 장르, 장르 내 가장 많이 재생된 고유번호 
• dic1, dic2
  • for i, (g,p) in enumerate(zip(genres, plays)):
    • #  가장 많이 재생된 장르
    • if g not in dic1:
      • dic1[g] =1
    • else:
      • dic1[g] +=1
    • # 장르 내 가장 많이 재생된 고유번호
    • if g not in dic2:
      • dic2[g] = [i, p] -> 여기서 핵심은 리스트를 사용해줘야 튜플형태로 추가가 가능함
    • else:
      • dic2[g].append((i,p))

• 이후에는 가장 많이 재생된 장르를 찾기위해 정렬을 해줌. -> 횟수 기준으로
  • s_dic1 = sorted(dic1.items(), key=lambda x:x[1], reverse = True)

• for i, _ in s_dic1: -> 장르 내 가장 많이 재생된 고유번호도 찾기위해 반복문 사용 -> 또한 반복문을 통해 가장 재생이 많이 된 순서로 진행할 수 있음
  • s_dic2 = sorted(dic2[i], key=lambda, reverse=True)[:2] -> 현재 dic2는 각 장르마다 리스트로 생성되어 있음. 따라서 그 리스트를 두번 째 재생횟수 기준으로 재정렬함
  • 여기서 "[:2]"를 해주는 이유는 문제에서 각 장르별 최대 2개씩을원 했으므로 만약 하지 않는다면
  •  

 "[:2]" 입력 이후 

• for k, _ in s_dic2:
  • anwer.append(k)

https://www.acmicpc.net/problem/1707

더보기

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


def bfs(x):
    q = deque([x])
    # 처음 노드는 빨강색으로 칠하기
    visited[x] = 0 # (0: 빨강 / 1: 파랑)
    while len(q) != 0:
        x = q.popleft()
        # 인접한 노드 하나씩 체크
        for y in graph[x]:
            if visited[y] == -1: # 빨강 <-> 파랑
                visited[y] = (visited[x] + 1) % 2
                q.append(y)

# 이분 그래프(bipartite graph) 판별함수
def is_bipartite():
    for x in range(1, v+1): # 하나씩 노드를 확인
        for y in graph[x]: # 인접 노드를 하나씩 확인
            # 같은 색상인 경우가 있따면
            if visited[x] == visited[y]:
                return False
    return True

# 입력
for _ in range(int(input())):
    # 정점의 개수(v)와 간선의 개수(e)
    v, e = map(int, input().split())
    # 그래프 정보 입력받기
    graph = [[] for _ in range(v + 1)]
    # 간선의 정보(e)
    for i in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [-1] * (v+1) # 방문 정보
    # bfs를 이용해 그래프 색칠하기
    for x in range(1, v+1):
        if visited[x] == -1:
            bfs(x)
    if is_bipartite(): print("YES")
    else: print("No")

더보기

ref:

https://codingopera.tistory.com/67

 

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) [초등학생도 이해하는 파이썬]

안녕하세요 '코딩 오페라'블로그를 운영하고 있는 저는 'Master.M'입니다. 저는 현재 '초등학생도 이해하는 파이썬'이라는 주제로 파이썬(python)에 대해 포스팅을 하고 있습니다. 제목처럼 진짜 핵

codingopera.tistory.com

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

깊이 우선 탐색은 영어로 DFS(Depth Frist Search)으로 깊이를 우선으로 탐색하는 방법입니다. 위 그림과 같이 DFS는 최대한 깊이 내려간 뒤 더 이상 내려갈 곳이 없으면 옆으로 이동하는 방식을 의미합니다. 

 

DFS는 다음과 같은 특징을 가지고 있습니다.

• 모든 노드를 방문하고자 할때 사용되는 방법
• DFS는 BFS(너비 우선 탐색)에 비해 비교적 간단함 
• 검색 속도는 DFS가 BFS에 비해 느림
• 스택이나 재귀함수를 이용하여 구현

 

너비 우선 탐색 (BFS)

너비 우선 탐색 (BFS)

너비 우선 탐색은 영어로 BFS(Breadth Frist Search)으로 너비를 깊이보다 우선적으로 탐색하는 방법입니다. 위 그림과 같이 BFS는 최대한 옆으로 넓게 이동한 뒤 더 이상 옆으로 갈 수 없으면 아래로 이동하는 방식을 의미합니다.

 

BFS는 다음과 같은 특징을 가지고 있습니다.

• 최단 경로를 찾고자 할때 사용 : 위 그림과 같이 BFS는 수평으로 탐색하는 방법이기 때문에 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있습니다.
• 예를 들어 A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있습니다. 
• 큐를 이용하여 구현

지금까지는 DFS와 BFS의 개념에 대해 알아보았습니다. 이제부터는 이 부분의 이해를 돕고자 파이썬 예제를 보여드리겠습니다. 

 

그래프

먼저 위와 같은 그래프가 있을 때, 이를 파이썬 딕셔너리로 표현하면 다음과 같습니다.

 

myGraph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['A', 'H'],
    'E': ['B', 'I'],
    'F': ['C', 'J'],
    'G': ['C'],
    'H': ['D'],
    'I': ['E'],
    'J': ['F']
}

"""
DFS(Depth-First Search)
"""

def my_dfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    stack = list() # 정점과 인접한 방문 예정인 노드를 담을 배열

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

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

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

    print("dfs - ", visited)
    return visited
    
# 함수 실행
my_dfs(myGraph, 'A')
dfs -  ['A', 'B', 'E', 'I', 'C', 'F', 'J', 'G', 'D', 'H’]

1. 대표적인 DFS 코드 -> 스택과 재귀함수로 구현됨.
   1. 처음 방문했는지 확인하기위한 변수 Visited, 연관성을 알기위한 stack을 생성
   2. stack에 알고싶은 문자를 대입하고시작
   3. while stack을 도는데 이 때 x = stack.pop해서 담겨저 있는 문자를 뺴서 비교하기 시작함
      1. if x not in visited:이면 visited에 추가
      2. stack.append(reversed(array[x])) -> pop 함수는 뒤에서 부터 불러오므로 다음과 같이 해줘야함

https://www.acmicpc.net/problem/2667

더보기

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

graph = []  # 입력받을 그래프를 담을 리스트 선언
result = []  # 결과를 담을 리스트 선언
count = 0

for _ in range(N):
    graph.append(list(map(int, input().rstrip())))

# 한 점을 기준으로 (위 아래 왼쪽 오른쪽) 으로 한칸 씩 이동할 좌표 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(x, y):
    global count

    if x < 0 or x >= N or y < 0 or y >= N:
        return

    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)


# 그래프의 원소가 1일때만 dfs로 집을 방문한다.
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0

result.sort()  # 오름차순으로 정렬

print(len(result))  # 총 단지수 출력
for k in result:  # 각 단지마다 집의 수 출력
    print(k)

import sys
input = sys.stdin.readline
# graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 
# 1, 1, 1], [0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 0, 0, 0]] 

# 변수 생성, 주변 집체크용 count, 그래프, 그래프 결과값 리턴용 result
count = 0
graph, result = [], []

# 입력
N = int(input())
for _ in range(N):
    yarray = list(map(int, input().strip()))
    graph.append(yarray)

dx = [0,0,1,-1] # x방향
dy = [1,-1,0,0] # y 방향

# 주변 연결된 집찾기
def dfs(x, y):
    global count

    if x < 0 or y < 0 or x >= N or y >= N:
        return
    
    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for tt in range(len(dx)): # 0, 1, 2, 3
            nx = x + dx[tt]
            ny = y + dy[tt]
            dfs(nx, ny)

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0

result.sort()

print(len(result))
for t in result:
    print(t)

• 알고리즘을 작성할 때는 처음 메인 입력과 출력까지 전부 작성해둔 뒤 마지막으로 세부알고리즘을 구현해야함.
  • 여기서 핵심은 dfs 문제 이해가 어느정되 되었지만 반복학습이 필요예정
  • 처음 dfs 정하기 전에 방향을 dx, dy 방향을 설정함 dx[0 0 1 -1] ,dy [1 -1 0 0]
  • 이후 입력받은 dfs 그래프 값을 개별 노드로 대입함.
    • def dfs(x, y):
      • if x < 0 or x >= N or y < 0 or y >= N 거리 벗어나면 -> 예외처리 
        • return
      • if graph[x][y] == 1:
        • count +=1            -> 방문 카운트
        • graph[x][y] = 0     -> 방문했으면 0으로 처리
        • for t in range(len(dx)):             -> 4가지 방향 체크
          • nx = x + dx[i]              -> 다음 x 방향
          • ny = y + dy[i]                 -> 다음 y 방향
          • dfs(nx,ny)                       -> 다음방향을 받아서 주변에 1을 체크하는 재귀함수로 체크

https://www.acmicpc.net/problem/10026

# 실험중

import sys

input = sys.stdin.readline

N = int(input())

graph, cgraph= [], []
# graph = [['R', 'R', 'R', 'B', 'B'], ['G', 'G', 'B', 'B', 'B'], ['B', 'B', 'B', 'R', 'R'], ['B', 'B', 'R', 'R', 'R'], ['R', 'R', 'R', 'R', 'R']]

rgb = {}
count = 0

for _ in range(N):
    array = list(map(str, input().strip()))
    graph.append(array)
    cgraph.append(array)



for i in range(N):
    for j in range(N):
        if cgraph[i][j] == "G":
            cgraph[i][j] = "R"

print(graph, cgraph) # 코드는 다작성했고 내일 crgaph 변환만 확인하면 됨.


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

def dfs(x, y, temp):

    if x < 0 or x >= N or y < 0 or y >= N:
        return
    
    if graph[x][y] == temp:
        graph[x][y] = "0"
        for tt in range(len(dx)):
            nx = x + dx[tt]
            ny = y + dy[tt]
            dfs(nx, ny, temp)

def check(graph):
    r, g, b = 0,0,0

    for i in range(N):
        for j in range(N):
            rrr = "R"
            bbb = "B"
            ggg = "G"
            if graph[i][j] == rrr:
                r += 1
                dfs(i, j, rrr)
                rgb["R"] = r
        
            elif graph[i][j] == bbb:
                b += 1
                dfs(i, j,bbb)
                rgb["B"] = b
                
            elif graph[i][j] == ggg:
                g += 1
                dfs(i, j, ggg)
                rgb["G"] = g

# check(graph)
# print(rgb,sum(rgb.values()))

• 실패

더보기

import sys

# 빠른 입력함수
input = sys.stdin.readline
# 재귀 제한 변경 -> 스택 오버플로우 발생 제한을 해결하기위해 깊이 10만정도
sys.setrecursionlimit(int(1e5))

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

def dfs(x, y):
    for tt in range(len(dx)):
        nx = x + dx[tt] # 다음 방향
        ny = y + dy[tt] # 다음 방향

        if nx < 0 or nx >= N or ny < 0 or ny >= N: # 예외처리
            continue
        
        if not visited[nx][ny]: # 방문하지 않았을때
            if graph[x][y] == graph[nx][ny]: # 처음 bfs를 호출 할때의 x, y값으로 주변을 비교 즉 "G"가 들어왔다면 G만 비교하는 것임
                visited[nx][ny] = -1
                dfs(nx,ny)

N = int(input())
graph = []
for _ in range(N):
    array = list(map(str, input().strip()))
    graph.append(array)

# 연결 요소의 개수 세기
answer = 0
visited = [[False] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if not visited[i][j]:   
            visited[i][j] = True
            dfs(i, j)
            answer += 1

print(answer, end=' ')

# 초기화
answer = 0
visited = [[False] * N for _ in range(N)]

# R -> G 변환
for i in range(N):
    for j in range(N):
        if graph[i][j] == "G":
            graph[i][j] = "R"

for ii in range(N):
    for jj in range(N):
        if not visited[ii][jj]:
            visited[ii][jj] = -1
            dfs(ii,jj)
            answer += 1

print(answer)

• dfs에서 return 쓰지말고 continue 쓰자
• 재귀함수가 많이 필요할 것 같으면 "sys.setRecursion(int(1e5))" 사용 -> 10만
• 이전 나의 코드와 가장 큰 차이는, 나는 입력받은 "graph"를 건드려서 계속 사용했고, 여기는 "visited"로 방문처리를 하여 사용함
  • 처음 입력을 받고 난뒤 바로 방문처리를 위한 변수를 생성함 [[False] * N for _ in range(N)]
  • 지역을 알기위한 answer 변수또한 생성.
  • 이후 방문을 확인하는데
    • for i in range(N):
      • for j in range(N):
        • if not visited[i][j]: -> 방문하지 않았따면
          • visited[i][j] -> 방문처리
          • dfs(i, j)
          • answer +=1
  • def dfs(i,j):
    • for i in range(len(dx)):
      
      • nx = x + dx[i] -> 다음방향
      • ny = y + dy[i] 
      • if nx < 0 or nx >= N or ny < 0 or ny >= 0: -> 예외처리
        • return
      • if not visited[nx][ny]:
        • if graph[x][y] == graph[nx][ny]:  # 즉 "G"가 들어왔다면 계속 G만 찾는거임
          • visited[nx][ny] = -1  # 방문처리
          • dfs(nx, ny)

https://www.acmicpc.net/problem/1240

더보기

 

import sys

# 빠른 입력함수
input = sys.stdin.readline
# 재귀 제한 변경 -> 스택 오버플로우 발생 제한을 해결하기위해 깊이 10만정도
sys.setrecursionlimit(int(1e5))

def dfs(x):
    # x의 인접 노드 하나씩 체크
    for data in graph[x]:
        # print("data:", data)
        y = data[0]
        
        cost = data[1] # x에서 y로 가는 간선 비용
        if not visited[y]:
            visited[y] = True
            distance[y] = distance[x] + cost
            dfs(y) 

# n 노드의 개수, m 간선의 개수
n, m = map(int ,input().split())

# 트리 정보
graph = [[] for _ in range(n+1)] 

for i in range(n-1): # 항상 트리형식이므로 간선의 개수는 n-1이다.
    # 노드 a와 노드 b가 연결 (간선 비용은 c)
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

print(graph)

# 각 쿼리마다 매번 dfs를 수행
for i in range(m):
    # x에서 y로 가기위한 최단 거리 계산
    x, y = map(int, input().split())
    # 방문 여부 및 최단 거리 테이블 초기화
    visited = [False] * (n+1)
    distance = [-1] * (n+1)
    visited[x] = True # 시작점 방문 처리
    distance[x] = 0 # 자신까지의 거리는 0 

    dfs(x) # x부터의 치단 거리 계산
    print(distance[y])