최근 많은 화두가 되고 있는 스테이블 코인에 대한 좋은 강연을 듣게 되었습니다.

스테이블 코인 뿐아니라 현재의 금융 시스템의 한계를 지적하면 코인이 나오게된 배경과 생태계의 구성, 반대로 코인의 금융 네트워크에서 바로 이용되기 어려운 한계를 암호학 관점에서 바라보고 이 한계를 깰 수 있는 동형암호에 대한 연설까지 금융과 IT 기술에 관심이 있는 사람이라면 아주 유익한 강연이었다고 생각하여 글을 정리하고 공유 합니다.

 1부. 동형암호화란 무엇인가

― 기존 암호 방식의 한계와 ‘데이터를 보지 않고 계산하는’ 기술의 등장

최근 데이터 보안 분야에서 가장 큰 화두는 **동형암호(Fully Homomorphic Encryption, FHE)**이다.
이 기술은 “데이터를 암호화한 상태 그대로 계산할 수 있다”는 점에서 기존 암호 방식과 근본적으로 다르며,
AI 시대의 핵심 보안 기술로 주목받고 있다.

이 글에서는

• 기존 암호 방식의 구조적 문제
• 현재 코인(블록체인)이 가진 한계점
• 동형암호 기술이 등장한 이유
  를 중심으로 알아본다.

1. 기존 암호 기술의 구조적 한계

전통적인 암호 방식(AES, RSA 등)은
암호화 → 복호화 → 연산 → 재암호화
과정을 거친다.

즉, 데이터를 활용하려면 반드시 평문(원본) 상태가 되어야 한다.

이것이 문제가 되는 이유는 다음과 같다:

🔸 1) 연산 과정에서 ‘잠깐이라도’ 평문이 노출된다

• 서버 메모리, 로그, 캐시 등에 평문이 스치기만 해도 위험
• 내부자 공격, 해킹, 클라우드 운영자의 접근 위험 존재
• "암호화돼 있으니 안전하다"는 개념이 실제 사용 단계에서는 깨져버림

🔸 2) 클라우드를 신뢰해야 하는 구조

데이터 분석을 위해 클라우드에 올리면,
클라우드는 ‘내 데이터를 평문으로 볼 수 있는 존재’가 된다.

오늘날 금융·의료·AI·정부 데이터는 민감도가 높기 때문에
“서버를 신뢰해야만 사용 가능한 구조” 자체가 큰 리스크다.

2. 현재 블록체인·코인이 가진 근본적 한계

🔹 1) 양자컴퓨터 등장 시 암호가 즉시 무력화됨

비트코인·이더리움 등 대부분의 코인은
타원곡선 기반 공개키 암호(ECDSA) 를 사용한다.

양자컴퓨터는 이 암호를 빠르게 깨는 실험이 진행 중이며,
만약 실용화되면 다음과 같은 일이 벌어진다:

• 공개키 → 개인키 추출 가능
• 개인키 탈취 = 지갑 전체 자산 탈취
• 블록체인은 되돌릴 수 없으므로 복구 불가능

즉, 현재 코인은 양자컴퓨터 등장 순간 바로 해킹 위험에 노출된다.

🔹 2) 금융 시스템에 바로 적용되기 어려움

현 금융 시스템이 코인을 대체하지 못하는 이유는 다음과 같다:

1. 가격 변동성
   • 비트코인은 결제 수단이 되기 어렵다
   • “오늘과 내일 가치가 다르기 때문”
2. 규제 부재
   • 금융기관은 법적 리스크를 감당해야 한다
   • 자금세탁방지(AML), KYC 등 제도 미비
3. 데이터 비밀성 부족
   • 블록체인은 ‘무결성’ 중심 설계 → 공개형
   • 금융 데이터는 비밀성이 필수
   • 때문에 ‘퍼블릭 블록체인’ 그대로 금융에 적용하기 어렵다
4. 거래 처리 속도 및 확장성 문제
   • VISA, MasterCard에 비해 TPS가 낮음

이처럼 현재 암호화폐는 기술적·제도적 한계 때문에
금융을 완전히 대체하기 어려운 상태다.

3. 동형암호 기술의 등장

이러한 한계를 해결하기 위한 기술이 바로 **동형암호(FHE)**이다.

🔹 동형암호란?

“데이터를 복호화하지 않고, 암호화된 상태 그대로 연산하는 기술”

즉,

• 서버는 평문을 절대 보지 못하고
• 데이터는 항상 암호화된 상태로 남아 있고
• 연산 결과만 사용자가 복호화한다.

예시로 보면 더 이해하기 쉽다.

■ 기존 이메일 검색

• 암호화된 이메일 → 복호화 → 검색 → 다시 암호화
• 검색 과정에서 평문 노출됨

■ 동형암호 기반 이메일 검색

• 암호화된 이메일을 암호화된 키워드로 검색
• 서버는 평문을 전혀 알 수 없음
• 사용자가 결과만 복호화

4. 동형암호의 현재 기술 수준

천정희 교수 연구진이 개발한 **CKKS(그리고 최신 CKKS+)**는
AI·머신러닝 연산에 적합한 세계적 표준 스킴이다.

• 실수·복소수 연산 지원
• 높은 정확도
• 빠른 처리 성능
• 양자컴퓨터에도 안전

다만, 평문 연산에 비해 여전히 100~1000배 느리다.
그래서 모든 AI 모델에 바로 적용하기는 어렵지만,

• RAG(검색 기반 응답)
• 민감 정보 검색
• 생체 정보 보호
• 금융 기밀 데이터 처리

같은 분야에서 실용화가 빠르게 확산되고 있다.

✔️ 1부 핵심 요약

1. 기존 암호는 ‘연산을 위해 복호화해야 한다’는 구조적 한계가 있다.
2. 현재 코인은 양자컴퓨터 등장 시 개인키가 무력화되어 큰 취약점이 있다.
3. 블록체인은 무결성은 강하지만 비밀성은 약해 금융에 바로 적용되기 어렵다.
4. 동형암호는 데이터를 노출하지 않고 연산할 수 있는 차세대 보안 기술이며, AI·금융·국방 분야에서 빠르게 확산 중이다.

 2부. 스테이블코인이 열어가는 금융의 미래

― 결제·송금·AI 시대의 금융 인프라가 어떻게 바뀌는가

스테이블코인은 블록체인 기술을 금융에 가장 현실적으로 적용할 수 있는 수단으로 평가받고 있다.
특히 글로벌 결제, 해외송금, AI 기반 경제활동 등에 새로운 금융 인프라로 떠오르고 있다.

이 글에서는

• 스테이블코인의 개념
• 기존 금융 시스템의 문제
• 스테이블코인이 금융권에서 어떻게 활용되는지
• 장점과 한계점
  을 다룬다.

1. 기존 글로벌 금융 인프라의 한계

우리가 해외 송금을 보낼 때 2~5일이 걸리고 수수료가 5~6%나 붙는 이유는 구조 때문이다.

■ 기존 송금 흐름 (SWIFT)

SWIFT는 국제 표준 역할을 하지만 실제 송금 절차는 복잡하다:

은행 → 중계 은행 → 해외 은행 → 정산 기관 → 수취 은행

중간 참여 기관이 많을수록

• 시간이 길어지고
• 수수료가 증가하며
• 오류 가능성도 커진다

■ 카드 결제의 복잡한 구조

고객 → POS → PG → VAN → 카드사 → 인 issuing bank → acquiring bank → 상점

결제 한 번에 수많은 기관이 개입한다.
이 구조 때문에 결제가 “즉시 이루어지는 것처럼 보이지만 실제 정산은 며칠 뒤”에 완료된다.

2. 스테이블코인의 등장

비트코인은 “중개인 없이 돈을 보낼 수 있다”는 혁신을 보여줬지만

• 가격 변동성
• 느린 속도
• 높은 수수료

때문에 결제·송금용으로 적합하지 않았다.

이를 해결하기 위해 등장한 것이 스테이블코인이다.

■ 스테이블코인이란?

“달러 등 실물 자산에 가치를 1:1로 고정(Peg)한 디지털 자산”

예:

• USDT, USDC
• 국내에선 원화 스테이블코인 연구 단계

스테이블코인은 코인의 장점과 기존 금융의 안정성을 결합한 셈이다.

3. 스테이블코인 기반 결제의 장점

스테이블코인은 인터넷만 있으면 누구나 전 세계로 즉시 송금할 수 있게 한다.

■ 스테이블코인 결제 흐름

고객 → 블록체인 네트워크(검증자) → 상점

중간 단계가 거의 없다.
따라서:

• 송금 속도: 수 초 이내
• 수수료: 약 0.5% 수준
• 영업일·지연 없음
• 국가 간 연결성 문제 없음
• 은행 인프라가 부족한 국가에서도 사용 가능

특히 아프리카, 남미(페루 등)

• 은행 계좌 보급률이 낮음
• 통화가 신뢰받지 못함
• 급격한 인플레이션

이런 지역에서는 테더(USDT)가 사실상 달러 대용 통화로 쓰이고 있다.

4. 금융기관이 스테이블코인을 주목하는 이유

• 빠른 결제
• 낮은 수수료
• 전 세계 어디로든 즉시 송금
• 스마트컨트랙트 기반 자동 정산
• AI·IoT 디바이스 간 결제 자동화

특히 미국은 “지니어스 법안” 등을 통해 스테이블코인 규제를 정비 중이며,
이 흐름이 본격화되면 글로벌 기업들도 비용 절감을 위해 스테이블코인 결제를 채택할 가능성이 크다.

그렇게 되면
➡️ 한국 포함 각국도 규제·기술 대응이 필요해진다.

5. 스테이블코인의 금융권 적용 한계

아직 넘어야 할 과제도 명확하다:

🔸 1) 금융 규제 정비 필요

• AML/KYC 의무
• 스테이블코인 발행사 관리
• 준비금 투명성
• 국가별 규제 체계 충돌

🔸 2) 체인 간 상호운영성 문제

• 여러 블록체인 간 전송이 불편
• 브릿지 해킹 위험 존재

🔸 3) 원화 기반 스테이블코인 생태계 부족

• 미국·유럽 대비 국내 정책·산업 환경 미비
• 은행·금융기관의 실험이 제한됨

6. AI 시대에 스테이블코인이 중요한 이유

미래에는 AI가 AI에게 결제하는 시대가 올 것으로 전망된다.

예:

• AI가 자동으로 API 호출 비용 결제
• 자율주행차가 자동으로 충전 비용 지불
• 기계끼리 실시간 정산

이를 위해서는

• 인터넷에서 동작하는 안전한 결제 네트워크
• 프로그래머블하고 투명한 디지털 화폐
  가 필요하다.

바로 이 역할을 스테이블코인이 담당할 수 있다.

✔️ 2부 핵심 요약

1. 기존 결제·송금 시스템은 복잡한 구조와 높은 수수료, 긴 처리 시간이 문제다.
2. 스테이블코인은 인터넷 기반 금융망으로 결제·송금을 재구성할 수 있는 기술이다.
3. 금융권은 비용 절감·속도 향상을 위해 스테이블코인 활용에 큰 관심을 갖고 있다.
4. 규제·상호운영성·국내 생태계 부족 등 해결해야 할 과제도 존재한다.
5. AI 시대에는 기계·AI 간 결제를 위한 기본 인프라로 스테이블코인이 중요한 역할을 할 전망이다.

TOP-N과 인덱스 스캔이왜 그렇게 동작하는지까지

사내에서 페이징처리를 위해서 고전 방식의 쿼리를 이용한 TOP-N 방식을 사용한다.

예시

SELECT *
FROM
(
	SELECT ROWNUM as row_num, T.*
	FROM
	(
		SELECT *
		FROM MY_TABLE
		WHERE :조건
		ORDER BY :인덱스_컬럼
	) T
	WHERE ROWNUM <= :pageNum * :pageCount + 1
)
WHERE row_num > (:pageNum - 1) * :pageCount

pageNum: 페이지 번호

pageCount: 한 페이지에 표기할 아이템 수

위와 같은 규칙에 맞게 작성되어있는 페이징을 처리하는 서비스의 테스트를 진행했다.

처음은 단순하게 생각했다.

PK정렬 -> 인덱스 존재 -> 인덱스로 정렬 없이 상위 N개를 먼저 읽어온다.

하지만 실제 개발서버에서 진행한 오라클의 실행계획(plan)은 예상과 달랐다.

• PK 인덱스가 있음에도 TABLE ACCESS FULL
• ORDER BY 정렬 후 WINDOW SORT
• 힌트를 사용할 경우, 비용(cost)증가
• CARDINALITY(card) 값이 실제 데이터 개수와 다름
• 조건에 따라 인덱스를 타거나 풀스캔을 진행하거나

위 경우를 하나씩 파고들어가며 Oracle 옵티마이저의 핵심 철학과 TOP-N 최적화의 내부 동작 원리를 이해할 수 있었다.

1. 페이징 쿼리와 인라인뷰의 오해

인라인뷰는 모든 데이터를 정렬하고 ROWNUM으로 자를까?

SELECT *
FROM (
	SELECT *
	FROM MY_TABLE
	ORDER BY MY_TABLE_COL_PK
    )
WHERE ROWNUM <= 1000

인라인뷰에 ORDER BY 절이 있으니 Oracle은 모든 행을 정렬한 뒤, 1000개만 자를까?

1. MY_TABLE 전체를 읽기(FULL SCAN)

2. 메모리 / 디스크 정렬 (WINDOW SORT)

3. 상위 1000개만 자르기

이것은 부분적으로만 맞다.

정렬 대상 컬럼에 적절한 인덱스가 있다면 Oracle은 이렇게 동작하지 않는다.

2. TOP-N이란?

TOP-N은 정렬된 결과의 상위 N개만을 가져오는 방식이다.

즉, 정렬 전체를 다 만들지 않고 상위 N개를 판별할 수 있는 순간 STOPKEY로 즉시 중단하는 최적화이다.

이 최적화가 발생할 경우 플랜

COUNT STOPKEY
WINDOW NOSORT STOPKEY

STOPKEY가 등장한다면 Oracle은 중간에 읽기를 끊었다는 신호

3. TOP-N이 효율적으로 작동하는 조건

TOP-N 최적화는 모든 상황에서 효율적인 것은 아니다.

핵심: ORDER BY 컬럼이 인덱스 정렬 순서와 동일한 형태로 존재해야 한다.

예시

즉, 정렬 가능한 인덱스가 있을 때만 TOP-N 최적화가 제대로 동작할 수 있다.

4. 적절한 인덱스 혹은 PK가 있는데도 WINDOW SORT / FULL SCAN이 나온 이유

실제 발생한 플랜

SELECT STATEMENT optimizer=all_rows (cost=113 card=1000 bytes=220000)
 VIEW (cost=113 card=1000 bytes=220000)
  WINDOW SORT PUSHED RANK (cost=113 card=221 bytes=18564)
   TABLE ACCESS FULL OF 'MY_TABLE' (TABLE) (cost=112 card=221 bytes=18564)

"SELECT *" 를 사용

인덱스를 정렬 기준으로 사용할 수 있어도 쿼리에 SELECT * 문법을 사용하면 모든 컬럼을 테이블에서 찾아야한다.

즉, 인덱스를 따라 N개의 ROWID를 찾음 -> ROWID로 테이블을 다시 랜덤 엑세스(N번의 랜덤 I/O)

Oracle은 “랜덤 I/O 1000번” vs “풀스캔 1번”을 비교해
풀스캔이 더 쌀 것 같으면 TABLE ACCESS FULL 을 선택한다.

그 결과:

→ 인덱스는 정렬 순서를 제공하나
→ 결과 행의 모든 컬럼을 얻기 위해 결국 테이블 재접근이 필요
→ 랜덤 액세스 비용이 비싸면 옵티마이저가 풀스캔 선택

5. 힌트로 강제로 인덱스 스캔 → 더 안 좋은 COST?

인덱스 정렬을 위한 힌트 사용

--인덱스 컬럼정렬 힌트 사용
SELECT /*+ index_asc(t MY_TABLE_COL_PK) */*
FROM (
	SELECT *
	FROM MY_TABLE t
	ORDER BY MY_TABLE_COL_PK
    )
WHERE ROWNUM <= 1000

플랜결과

SELECT STATEMENT optimizer=all_rows (cost=409 card=1000 bytes=220000)
 VIEW (cost=409 card=1000 bytes=220000)
  WINDOW NOSORT STOPKEY (cost=409 card=221 bytes=18564)
   TABLE ACCESS BY INDEX ROWID OF 'MY_TABLE' (TABLE) (cost=409 card=221 bytes=18564)
    INDEX FULL SCAN OF 'MY_TABLE_COL_PK' (INDEX (UNIQUE)) (cost=8 card=221)

하지만 COST가 더 올라감.

왜일까?

이유는 매우 단순하다.

인덱스 FULL SCAN 방식 = 전체 풀스캔보다 더 많은 페이지 랜덤 액세스

인덱스는 보통:

• 블록이 더 작음
• 페이지 수가 더 많음
• 물리적 순서가 데이터 순서와 다름

즉, 인덱스 FULL SCAN은 테이블 FULL SCAN보다 오히려 더 많은 I/O가 발생할 수 있다.

그 다음엔 ROWID로 테이블 랜덤 액세스

그러니 힌트로 인덱스를 타게 만들면

“불필요하게 인덱스를 훑고 + 테이블을 다시 랜덤 액세스하는 비효율”

이 될 수도 있다.

6. 플랜에서 인덱스 스캔을 타는 경우

SELECT *
FROM (
	SELECT *
	FROM MY_TABLE
	ORDER BY MY_TABLE_COL_PK
    )
WHERE ROWNUM <= 50

--혹은
SELECT *
FROM MY_TABLE
ORDER BY MY_TABLE_COL_PK
FETCH FIRST 50 ROWS ONLY;

where 절의 ROWNUM을 50으로 제한해보자

이런 경우 옵티마이저가 “50개만 읽으면 되니까?” 하고 TOP-N 최적화를 자동으로 적용할 때가 있다.

왜 자동으로 적용되었을까?

• 테이블이 충분히 크고
• PK 인덱스가 정렬순서와 같고
• 상위 소량의 행(50개)만 필요할 때

이런 경우 Oracle은 다음 과정을 선택한다:

1. 인덱스를 DESC로 스캔해 상위 50개 ROWID 추출
2. 50개의 ROWID만 테이블에서 랜덤 액세스
3. STOPKEY로 종료

이 작업은 풀스캔보다 훨씬 빠를 수 있다.

즉, 데이터량과 TOP-N의 N 값의 상대적 크기가 최적화 방향을 결정한다.

7. 왜 인라인 뷰의 card수가 실제 테이블의 row 수와 다를까

실제 테이블 rowcount = 1000+
그런데 실행계획에서: card = 221이렇게 나왔다.

이유

cardinality는 실제 접근 행수가 아니라
옵티마이저가 통계 기반으로 “예상”한 행 수이다.

따라서:

• 통계가 오래됨
• 히스토그램 없음
• 인덱스 컬럼 분포가 균등하다고 오해
• WHERE 조건의 선택도가 다르게 해석됨

이런 이유로 실제와 다르게 보인다.

8. 그럼 지금 사용 중인 인라인 페이징이 나쁜가?

결론

❌ 인라인 뷰 + ROWNUM 페이징 자체가 나쁜 것이 아니다.

⭕ ORDER BY 컬럼 인덱스 유무가 성능을 좌우한다.

ORDER BY 인덱스가 없다면
→ WINDOW SORT + FULL SCAN은 정상적이며 불가피하다.

ORDER BY 인덱스가 있다면
→ TOP-N 최적화가 적용되어 인덱스 스캔 + STOPKEY 가 가능해진다.

9. TOP-N 최적화가 발휘되는 데이터량 기준

정확한 기준 값은 없지만 경험적으로 다음과 같다.

즉, 데이터가 많아질수록 TOP-N 최적화는 더 큰 힘을 발휘한다.

🏁 마무리

1. 인라인뷰의 정렬 가능한 인덱스 유무가 중요하다.
2. STOPKEY는 상위 N개에서 “조기 종료”를 가능하게 한다.
3. 인덱스 스캔이 항상 더 빠른 것이 아니며, SELECT * 이라면 테이블 랜덤 액세스 비용 때문에 FULL SCAN이 더 빠를 수도 있다.
4. Cardinality(card)는 실제 행 수가 아닌 통계 기반 추정치이다.
5. PK 인덱스는 정렬에 유리하나, 모든 상황에서 인덱스를 타는 것은 아니다.
6. TOP-N은 데이터가 많을수록 효과가 크다.

Oracle 실행계획은 단순히 “풀스캔이면 느린 쿼리다”가 아니라 왜 풀스캔이 선택되었는지를 이해하는 것이 중요했다.

TOP-N, STOPKEY, 인덱스 스캔의 상관관계를 확실히 이해하기 좋은시간이었습니다.

JS를 활용하는 front 소스에서 사용자 입력을 통해서 함수를 더 진행시킬지 중단할지 정해야하는 경우가 많이 생깁니다.

모든 Modal 창을 통해서 callback 처리를 각각 함수에서 받아서 처리하면 문제가 생길 일이 없지만, 복잡한 비지니스 로직해서

하나의 함수에서 연속적으로 사용자 입력을 받아할 경우가 생길 수 있습니다.

최근 실무에서 위와 같은 문제가 생긴적이 있는데 이를 해결하기 위해서 사용한 간략한 기법을 정리해 봅니다.

예시코드

let success = ''	//resolve를 담을 변수
let fail = '' 		//reject를 담을 변수


const returnPromise = () => {
    console.log("returnPromise call")
    
    return new Promise((resolve, reject) => {
        success = resolve
        fail = reject
    })
}


const promiseControllTest = async () => {
    console.log("test start")

    //유저 입력 confirm을 비동기로 호출
    //업무에서는 Modal창을 통해서 사용자 입력을 받는다.
    setTimeout(() => {
        if(confirm("확인을 눌러주세요.")) success()
        else fail()
    }, 0)
    
    console.log("유저 입력까지 returnPromise 대기")
    
    let resultP = await returnPromise()
        .then(() => "success 되었음.")
        .catch(() => "reject 되었음.")

    //resultP 값에 따라서 함수를 더 진행할지 결정할 수 있음
    console.log("resultP = ", resultP)

    console.log("test end")
}

위 소스의 promiseControllTest 함수는 await된 returnPromise의 resolve가 사용자 입력인 confirm이 resolve()를 해줄 때까지 pending 되었다가 이후 결과 값 resultP를 통해서 함수를 더 진행시킬지 종료 시킬지(reuturn) 결정할 수 있습니다.

실무에서 React 혹은 Vue를 사용할 경우, 새로운 컴포넌트에서 success / fail 변수를 할당하고 Modal 창을 비동기적으로 호출하여 동작을 컨트롤할 수 있습니다.

하코테 8일차 문제 역시 스택/큐 문제입니다.

해당 문제에서는 큐를 이용한 문제 풀이를 하였으나 반드시 자료구조 큐를 이용할 필요없이 성능 향상을 위한 방식을 고려해볼 수 있어습니다.

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.

작업 진도는 100 미만의 자연수입니다.

작업 속도는 100 이하의 자연수입니다.

배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses speeds return

[93, 30, 55] [1, 30, 5] [2, 1]

[95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1] [1, 3, 2]

입출력 예 설명

입출력 예 #1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.

세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

문제 풀이

해당 문제는 작업의 순서에 따라서 배포까지 남은 작업기간이 앞선작업과 일치하는지 계속 비교하는 문제로 FIFO(First In First Out)의 큐 자료구조를 혹은 방법론을 이용하는 문제입니다.

1. 배포까지 남은 작업 기간을 계산하여 큐에 넣기

2. 배포할 작업보다 작업 기간이 작거나 같은 작업은 함께 배포 -> 큐에서 함께 제거

방식으로 접근 합니다.

소스 코드

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        /*
        문제 풀이 개요
        함께 배포될 세트를 작업의 순서대로 처리
        순차처리 -> 큐
        함께 배포 -> 현재 배포할 작업보다 완료 예정기간이 작거나 같은 것
        */
        Deque<Integer> q = new ArrayDeque<>();  //완료까지 남은 작업일을 담는 큐
        List<Integer> list = new ArrayList<>();    //정답을 담을 리스트
        
        //작업 담기
        for(int i = 0; i < progresses.length; i++) {
            //남은 작업 기간 -> 소숫점은 하루가 더 필요하므로 올림처리 한다.
            int leftD = (int)Math.ceil((100.0 - progresses[i]) / speeds[i]); 
            q.offer(leftD);
        }
        
        //배포일 계산
        while(!q.isEmpty()) {
            int cnt = 1;    //함께 배포될 작업 수
            int d = q.poll();   //현재 작업이 완료되기까지 걸리는 기간
            
            //함께 배포될 작업 카운트
            while(!q.isEmpty() && q.peek() <= d) {
                q.poll();
                cnt++;
            }
            
            list.add(cnt);
        }
               
        return list.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

해당 코드는 앞선 문제풀이 방식을 순차적으로 코드로 구현한 코드입니다.

남은 작업을 계산하여 큐에 넣기 -> 배포일이 같은 작업을 큐에서 반복적으로 제거하면서 정답 리스트에 적재

시간복잡도 O(logN)

하지만 위 문제의 경우, 작업(porgresses)를 처음부터 끝까지 그대로 봐도 무방하므로 큐 자료구조의 직접 사용하지 않고 풀이가 가능합니다. 그 밖에도 ArrayList를 이용해서 정답을 삽입, Stream을 통한 정답 타입(int 배열)로 변환하면서 오버헤드 등을 줄이는 방식이 가능합니다.

개선된 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {     
        /** 개선된 풀이 */
        int n = progresses.length;
        // 임시로 최대 n개까지 담을 버퍼
        int[] tmp = new int[n];
        int k = 0; // 실제 결과 길이

        // 첫 작업의 완료일(정수 올림)
        int curr = (100 - progresses[0] + speeds[0] - 1) / speeds[0];
        int cnt = 1;

        for (int i = 1; i < n; i++) {
            int day = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
            if (day <= curr) {
                // 현재 배포 묶음에 포함
                cnt++;
            } else {
                // 지금까지 묶은 개수 확정
                tmp[k++] = cnt;
                // 새 기준일로 갱신
                curr = day;
                cnt = 1;
            }
        }
        // 마지막 묶음 추가
        tmp[k++] = cnt;

        // 결과 크기에 맞춰 잘라서 반환
        return Arrays.copyOf(tmp, k);
    }
}

1. 불필요한 큐에 담기 제거

2. 올림을 위한 형변환을 제거(float, Math 등 사용 제거)

3. 스트림 오버헤드 제거(List를 Array로 변환하기 위함)

을 통해서 메모리 사용 감소 및 동작 간소화로 성능을 개선할 수 있습니다.

실제 프로그래머스의 결과만 보았을 때, 시간적으로 약 100배 좋은 성능을 낼 수 있습니다.

단순히 문제가 요구하는 카테고리의 자료구조를 사용하여 문제를 풀 수 있지만, 기본형(int 배열 등)의 사용이나 정수형 올림 나눗셈을 이용한 캐스팅 제거, 스트림을 통한 오버헤드 제거 등을 적극적으로 활용해보는 것이 좋은 성능의 코드를 만들 수 있다는걸 체감하게된 좋은 문제였습니다.

하코테(하루 코딩 테스트) 2주차의 두번째 문제 입니다.

이번주는 회사 일정으로 문제풀이 및 블로그 글 작성이 버거움이 있었어서 블로그 글을 몰아쓰게 되었습니다.

그래도 매일 한 문제씩 풀자고 목표를두니 작성을 포기하지는 않게되어서 도움이되네요.

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices return

[1, 2, 3, 2, 3] [4, 3, 1, 1, 0]

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.

2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.

3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.

4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.

5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

문제 풀이

해당 문제는 현재의 주식 가격과 미래의 주식 가격이 변경되는 시점의 차이를 확인해야합니다.

정확히는 가격이 떨어지는 시점을 비교하는 것이 핵심 입니다.

사실 이 문제를 처음 접했을 때, 주식 가격에 따른 가격/인덱스 정보를 담은 리스트를 담고 정렬하여 문제를 풀려고 시도 했습니다.

그와 같은 풀이는 가격이 처음 변동되는 시점을 확인할 수 없다는 문제로 잘못된 풀이라고 할 수 있습니다.

문제의 카테고리가 스택/큐 이기에 두 자료구조를 사용해야한다는 힌트로 문제를 풀 수 있었습니다.

주식 가격이 처음 변경되는 시점은 시간을 순서대로 가격을 비교할 때, 현재 시점의 가격이 가장 가까운 이전 시점의 가격의 순서와 비교를 합니다. 가장 먼저 들어온 가격이 아닌 가장 나중에 들어온 가격과 비교 -> 즉, 스택 자료구조를 선택 합니다.

소스코드

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        /*
        문제 풀이 개요
        과거의 주식가격을 미래의 시점과 비교
        
        주가의 하락시점 확인
        -> 시간의 순서로 주식가격이 가장 먼저 나오는 주가하락 시점을 파악
        -> 스택 자료구조를 이용하여 순차비교
        */
        int len = prices.length;
        int[] answer  = new int[len]; //정답을 담을 배열
        Deque<Integer> st = new ArrayDeque<>(); //순번을 담을 스택
        
        //주식가격을 순회하며 미래시점 순번 비교
        for(int i = 0; i < len; i++) {
            //주식가격이 처음 하락하는 경우
            while(!st.isEmpty() && prices[st.peek()] > prices[i]) {
                int idx = st.pop();
                answer[idx] = i - idx;
            }
            
            st.push(i);
        }
        
        //스택에 남아있는 가격이 떨어지지 않은 시점 게산
        while(!st.isEmpty()) {
            int idx = st.pop();
            answer[idx] = len - idx - 1;
        }
        
        return answer;
    }
}

문제 풀이에서 언급한 것처럼 해당 문제는 카테고리가 스택/큐 이기에 두 자료구조를 사용해야한다는 힌트로 문제를 풀 수 있었습니다.

이러한 힌트가 없었다면, 문제 풀이에 더 어려움을 겪었을 것 같습니다.

문제를 접할 때, 어떤 자료구조와 개념으로 접근해야할지 아직 더 많은 훈련이 필요할 것 같습니다.

하코테를 시작하고 2주차가 시작되었습니다.

월요일에 큰 일정이 없어서 무사히 문제를 풀 수 있었습니다.

지난주에는 계속 해시 문제를 풀었다면, 이번주에는 스택/큐 문제가 나올 것으로 보입니다.

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.

arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수

배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr answer

[1,1,3,3,0,1,1] [1,3,0,1]

[4,4,4,3,3] [4,3]

입출력 예 설명

입출력 예 #1,2

문제의 예시와 같습니다.

풀이

이번 문제는 arr를 순회하면서 현재의 값이 이전 값과 같은지를 비교하는 문제였습니다.

스택/큐 문제인만큼 스택 자료구조를 활용해서 최상단의 값이 현재 타겟 값과 동일한지 비교하는 문제로 판단했습니다.

실제로 해당 문제를 Stack이나 ArrayDeque를 활용해서 스택으로 문제를 풀 수 있지만, 성능적인 측면에서 조금 더 불리한 면이 있습니다.

특히 최종적으로 Stream을 통해서 return 값의 형태인 int 배열로의 변환은 박싱/언박싱의 오버헤드가 있습니다.

import java.util.ArrayDeque;

public class Solution {
    public int[] solution(int []arr) {
        /*
        문제 풀이 개요
        arr를 하나씩 담으면서 현재 값이 이전 값과 동일하지 않는다면, 담는다.
        */
        ArrayDeque<Integer> q = new ArrayDeque<>();

        //탐색
        for(int num : arr) {
            if(q.isEmpty() || q.peekLast() != num) {
                q.offer(num);
            }
        }

        //변환
        int[] answer = q.stream()
                .mapToInt(Integer::intValue)
                .toArray();

        return answer;
    }
}

ArrayDeque를 다시 int 배열로 만들기 위해 Stream의 사용은 성능적으로 불리함

개선된 풀이 1.

import java.util.stream.IntStream;

public class Solution {
    public int[] solution(int[] arr) {
        int n = arr.length;
        if (n == 0) return new int[0];

        return IntStream.range(0, n)
                .filter(i -> i == 0 || arr[i] != arr[i - 1])
                .map(i -> arr[i])
                .toArray(); // int[]
    }
}

스트림을 확용한 가독성 풀이

하지만, 역시 스트림을 사용하므로써 성능적으로 약간의 개선만 있을 뿐 효과적이라고 볼 수 없다.

효율성 테스트 평균 시간 30ms

개선된 풀이 2.

import java.util.Arrays;

public class Solution {
    public int[] solution(int []arr) {
        /*
        문제 풀이 개요
        arr를 하나씩 담으면서 현재 값이 이전 값과 동일하지 않는다면, 담는다.
        */
        int n = arr.length; // arr의 길이
        
        // 예외처리
        if(n == 0) return new int[0];
        
        int l = 0;  // 임시 배열의 크기
        int[] temp = new int[n];    // 임시 배열
        
        temp[l++] = arr[0]; //첫번째 값 넣기
        
        for(int i = 1; i < n; i++) {
            if(temp[l-1] != arr[i]) temp[l++] = arr[i];   // 이전 값과 다르면 담기
        }
        
        return Arrays.copyOf(temp, l);
    }
}

인덱스로 필요한 배열을 직접 생성한다.

성능적으로 가장 우수하다

효율성 테스트 평균 시간 10ms

오늘 풀이는 낮은 난이도의 문제이나 효율성적인 면에서 어떤 코드가 더 좋은지에 대한 고민이 필요한 부분인 것 같다.

위 세가지 풀이 모두 정답이지만, 해당 하는 팀이 선호하는 컨벤션이 무엇인지를 확인하고 모두 사용할 줄 아는것이 좋을 것 같다.

하지만 기본적으로 스트림 등을 활용한 멋진 코드 보다 속도와 메모리 관리 등에 효율적인 순수 배열/루트를 활용하는 것이 더 좋지 않을까란 생각이 들었다.

매일 코딩테스트 5일차 문제까지 완료했습니다. 조금씩 매일 문제를 푸는데에 익숙해지는 것 같습니다.

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

completion의 길이는 participant의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

[participant] [completion] return

["leo", "kiki", "eden"] ["eden", "kiki"] "leo"

["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko"

["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"

입출력 예 설명

예제 #1

"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2

"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3

"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

문제 풀이

해당문제는 참가자 - 완료자 목록을 계산해서 남은 1명을 구해냅니다.

각 문자열 배열로 존재하고 목록을 서로 비교해야하기에 문자열 배열 비교 혹은 해시 테이블을 사용할 수 있습니다.

배열풀이

각 배열을 정렬한다. -> i번째 값이 불일치 한다면, 해당하는 참가자 배열의 값이 완주못한 선수이다.

시간복잡도

- O(nlogn)

- 2번의 배열 정렬(O(nlogn))과 한번의 탐색(O(n))이 필요

해시 테이블 풀이

참가자를 해시 테이블에 담고 완주자를 테이블에서 제거서해서 남은 인원이 완주못한 선수이다.

시간복잡도

- O(n)

- 두번의 해시 테이블 삽입(O(1)) 및 제거(O(1))가 필요

참가자의 최댓값은 10만이고 메모리에 대한 제약이 없기에 해시 테이블의 풀이를 선택한다.

소스 코드

import java.util.Map;
import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        /*
        문제 풀이 개요
        참가자 목록 - 완주자 목록을 계산한다.
        참가자 중에 동명이인(중복)이 있을 수 있다 -> Map 이용
        */
        Map<String, Integer> map = new HashMap<>();
        for(String p : participant) map.merge(p, 1, Integer::sum);  //참가자 추가
        for(String c : completion) map.merge(c, -1, Integer::sum);  //완료자 제거
        
        //결과 찾기
        String answer = map.entrySet().stream()
                .filter(e -> e.getValue() != 0)	//0이 아닌 것만 남기기
                .map(Map.Entry::getKey)	//엔트리의 key만 추출
                .findFirst()	//첫번째 값(이미 1개이지만 값을 가져오기 위함) -> Optional<String>
                .orElseThrow();	//예외처리를 통해 String으로 변환
        
        return answer;
    }
}

알아두면 좋은 점

해시 문제 중 비교적 간단한 문제이지만, Map의 추가/삭제 그리고 최종 값을 찾기 위한 탐색까지 사용해야하는 좋은 문제인것 같습니다.

특히 유용한 문법인 merge 메서드와 stream API, Map의 Entry 인터페이스 사용까지 적절히 연습할 수 있었습니다.

하코테 4일차 풀이까지 완료. 다행히 작심삼일로 끝내지 않게 되었으니 꾸준히 해보려고 합니다.

문제 설명

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

속한 노래가 많이 재생된 장르를 먼저 수록합니다.

장르 내에서 많이 재생된 노래를 먼저 수록합니다.

장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

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

제한사항

genres[i]는 고유번호가 i인 노래의 장르입니다.

plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.

genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.

장르 종류는 100개 미만입니다.

장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.

모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres plays return

["classic", "pop", "classic", "classic", "pop"] [500, 600, 150, 800, 2500] [4, 1, 3, 0]

입출력 예 설명

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번 노래는 수록되지 않습니다.

풀이

이번문제로 Map / Set 추상 자료형 활용한 해시 테이블 문제 입니다.

장르별로 mapping이 필요한 -> Map

장르별로 mapping된 value는 계속 추가됨 -> ArrayList

재생 수 만큼 내림차순 정렬이 필요함 ArrayList sort

소스 코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        /*
        문제풀이 개요
        장르별로 mapping이 필요한 -> Map
        장르별로 mapping된 value는 계속 추가됨 -> ArrayList
        재생 수 만큼 내림차순 정렬이 필요함 ArrayList sort
        */
                
        Map<String, List<int[]>> songsByGenre = new HashMap<>(); // genre -> [index, plays]
        Map<String, Integer> totalByGenre = new HashMap<>();     // genre -> total plays

        for (int i = 0; i < genres.length; i++) {
            String g = genres[i];
            songsByGenre.computeIfAbsent(g, k -> new ArrayList<>()).add(new int[]{i, plays[i]});
            totalByGenre.merge(g, plays[i], Integer::sum);
        }

        // 1) 장르를 총 재생 수 기준으로 내림차순 정렬
        List<String> genreOrder = new ArrayList<>(totalByGenre.keySet());
        genreOrder.sort((a, b) -> Integer.compare(totalByGenre.get(b), totalByGenre.get(a)));

        // 2) 각 장르 내에서 (재생수 내림차순, 인덱스 오름차순) 정렬 후 상위 2개 선택
        List<Integer> ans = new ArrayList<>();
        for (String g : genreOrder) {
            List<int[]> list = songsByGenre.get(g);
            list.sort((x, y) -> {
                if (x[1] != y[1]) return Integer.compare(y[1], x[1]); // plays desc
                return Integer.compare(x[0], y[0]);                   // index asc
            });
            for (int k = 0; k < Math.min(2, list.size()); k++) {
                ans.add(list.get(k)[0]); // 노래 인덱스만 수록
            }
        }

        // 3) 리스트 -> 배열
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

알아두면 좋은 점.

1. computeIfAbsent

V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

• 의미: 맵에서 key에 해당하는 값이 없으면 mappingFunction을 실행해서 새 값을 만들어 넣고, 그 값을 리턴.
• 있으면 그대로 리턴, 없으면 새로 계산해서 put.

예시:

Map<String, List<Integer>> map = new HashMap<>(); // "rock" 키가 없으므로 새 ArrayList 생성 후 추가됨 

map.computeIfAbsent("rock", k -> new ArrayList<>()).add(100); // 다시 호출하면 이미 있으므로 기존 리스트에 추가 
map.computeIfAbsent("rock", k -> new ArrayList<>()).add(200); System.out.println(map); // {rock=[100, 200]}

→ 네 코드에서는 songsByGenre.computeIfAbsent(g, k -> new ArrayList<>()) 로 장르별 리스트를 자동으로 초기화해주는 역할.

2. merge

V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)

• 의미: 맵에 key가 없으면 value를 넣고,
  이미 있으면 remappingFunction으로 기존 값과 새 값을 합쳐서 갱신.
• 보통 합계 누적, 문자열 연결 등에 활용.

Map<String, Integer> total = new HashMap<>();

// rock 키가 없으니 300으로 추가됨
total.merge("rock", 300, Integer::sum);

// rock 키가 이미 있으니 (300 + 500)으로 갱신됨
total.merge("rock", 500, Integer::sum);

System.out.println(total);	// {rock=800}

이번에 풀이한 "베스트 앨범" 문제도 기존에 풀어봤던 문제였습니다.

다만, 기존 풀이가 남아있지 않아서 다시 풀어볼 수 있었습니다.

기존에도 Map을 활용해서 문제를 풀었는데 이번에는 put / get 문법으로의 조합이아닌 Map 유틸의 computedIfAbsent / merge를 활해서 풀이를 했습니다.

Java 8에서 추가된 해당 문법은 활용도가 높은만큼 익숙해지면 다른 문제를 푸는데에 도움이 될 것 같습니다.