단축 URL 서비스의 조회 트래픽은 다음과 같은 특징이 있다.

• 조회가 서비스의 핵심
• 트래픽 편중

이런 특성 때문에 단순히 인덱스, 캐시를 붙이는 판단은 위험하다.

고로 이 글에서는 인덱스는 얼마나 효과가 있는가? 캐시는 DB 부하를 얼마나 줄여주는가? VU 10,000 상황에서 병목은 어디서 발생하는가? 에 대해서 알아볼 것이다.

2. 실험 환경

리소스 제한

데이터 규모 총 URL 갯수 : 100,000 트래픽 분포

실험 1. 베이스라인 (Cache OFF, Index OFF)

처음 테스트를 진행했을 때는

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT u.id, u.original_url, u.short_url, u.expiration_date, u.created_at
FROM url u
WHERE u.short_url = '7NT';

인덱스 없이 전체 테이블 스캔 형식으로 되었음을 알 수 있었다. 또한 실행 시간을 기준으로는 1개의 커넥션이 1초에 약 12개의 쿼리를 처리할 수 있다는 뜻으로 (1,000/86.34 => 약 11.58), 10개의 커넥션을 쓸 수 있다고 할 때 DB의 처리량이 약 120 QPS(Queries Per Second)로 제한되었다.

실제로 다음과 같은 결과물을 얻을 수 있었고, 커넥션이 얼마나 활용되었느냐도 같이 보면

최대치인 최대 10개의 connection이 사용되었음을 확인하였다. 여기까지는 예상했던 결과이고, Index를 적용하면 어떨까?

실험 2. 인덱스 적용 (Cache OFF, Index ON)

인덱스를 적용하여 확인한 결과 Query 실행 시간이 0.028ms로 1차 실험 결과와 달리 99.97% 줄었음을 확인하였다.

본격적으로 DB connections를 확인한 결과,

1차 결과물과 달리 DB connection 수가 1개만 활용된 것을 확인하였다. 이를 통해, 커넥션 풀 효율성이 크게 향상된 것을 확인하였다.

다만, QPS는 1차 실험 결과와 큰 차이가 없는 것으로 보아, 대규모 트래픽 처리에 한계가 있음을 확인하였다.

실험 3. 캐시 적용 (Cache ON, Index ON)

캐시와 인덱스를 적용한 결과 QPS가 눈에 띄게 준 효과를 볼 수 있었다.

이를 통해 Redis가 Hot/Warm 트래픽의 대부분을 흡수함으로써, DB 부하를 준 것을 확인할 수 있었다.

추가로 Redis의 사용률은 다음과 같다.

비교표

응답 시간

응답 시간 : 실제 서버 성능을 파악하기 위해 K6의 내장 메트릭, 서버 응답 시간 기준 (http_req_waiting)을 사용

P95 Latency로 보아, 최종적으로 약 0.64초(639ms)가 걸리는 걸로 확인을 했다. 병목이 걸린 이유는 다음 글을 통해서 확인하고자 한다.

처리량

데이터베이스

최종적으로 각 성능을 비교했을 때, Cache와 Index를 같이 적용했을 때 비교적 효과를 볼 수 있었고 추가로 DB에 부하를 줄일 수 있었음을 확인하였다.

결론

단순하게 해당 테스트를 진행할 때는 Index와 캐시를 사용했을 때, 유의미한 지표가 나올거라고 생각했다. 그러나 DB 부하를 줄이는 측면에서 유의미한 결과를 냈지만, 응답 시간에 대해서는 크게 유의미한 결과를 내지 못했다.

고로 다음에는 Scale out으로 200ms 이내에 응답 시간을 노려볼 예정이다.

Salang은 1:1 매칭 음성 채팅 플랫폼이다.
해당 업무를 맡게 되면서, 먼저 떠오른 생각은 "어떻게 매칭시킬 것인가"였다.

회사에서 요구한 사항은 적어도 1,000명이 동시에 매칭을 시도할 때 매칭이 안정적으로 이루어지게 하는 것이 목표였다.

1,000명이 동시에 매칭을 요청하면 어떤 일이 벌어질까?

어떤 방식으로 시스템을 구조화할지 구체화하면서, 부하 테스트를 통해 안정적으로 매칭이 되는지 알아보았다.

이를 위해 Redis를 활용한 매칭 구조를 구현하기로 했다.

왜 Redis인가?

먼저 고려한 것이 어떻게 빠르게 매칭을 할 것인지, 매칭 대기열을 어떻게 관리할지였다. 이러한 이유로 Redis를 선택하였고, 이유는 다음과 같다.

낮은 지연 시간

• Redis는 인메모리 기반으로 ZADD, ZREM 같은 큐 연산을 수 ms 단위로 처리할 수 있다.

Race Condition의 원자적 처리

• Redis Lua Script를 활용해 중복 매칭을 방지하고, 매칭 과정을 단일 원자 연산으로 보장할 수 있다.

운영 대비 높은 처리량

• 단일 노드로도 수천 건의 동시 요청을 처리할 수 있으며, 필요 시 손쉽게 확장 가능하다.

다음 이유를 바탕으로 실 사용자에게 도입하기 전 Redis를 활용한 매칭 테스트 프로젝트를 구현하게 되었다.

프로젝트 목표

1. 1,000명 동시 사용자 환경에서의 성능 검증

   • 실 서비스에서 Redis 기반 매칭 시스템이 적합한지 확인
   • 1,000 VU 기준으로 처리 속도와 안정성 검증

2. 매칭 성능 목표

   • JoinQueue 응답 시간: 50ms 이하
   • 매칭 결정 평균 시간: 500ms 이하
   • Redis Lua Script Latency: 50ms 이하
   • Redis 매칭 후보 선택 Latenty: 50ms 이하

테스트 환경

테스트 데이터

성별의 비율은 아직 실제 서비스를 하기에 앞서 가정을 두고 테스트 데이터를 구성하였습니다.

시스템 구조

API 호출은 모두 k6 Load Generator를 사용하여 시뮬레이션했습니다.

매칭의 핵심 흐름은 다음 세 가지로 구성된다.

1. Redis

   • 실시간 매칭의 상태 저장소
   • ZSET 기반 대기열
   • 사용자 상태(STATUS, matchedWith, lastJoinAt) 저장
   • 매칭 알고리즘의 Source of Truth

2. Worker(내부 Background Thread)

   • 서버 내부에서 동작하는 50ms 간격 루프
   • Redis ZSET을 기반으로 후보 조회
   • 조건 검사 후 Pair 결정
   • Lua Script로 원자적 MATCH 처리

3. Postgres
   • 매칭 이력 영구 저장소
   • 운영/통계/조회 목적

첫 번째 부하 테스트

테스트 시나리오

빠른 테스트를 위하여 50명의 가상 사용자와 1분 간의 테스트를 진행하였다.
그리고 다음 플로우를 수행하는 과정으로 부하를 생성하였다.

1. Join Queue: POST /queue/join 호출
2. Status Polling: GET /queue/status/{userId} 반복 호출 (MATCHED까지 대기)
3. ACK: 매칭 성공 시 POST /queue/ack 호출
4. 다시 1번으로: 매칭 해지 후 다음 매칭 시도

worker는 한 번에 한 쌍만 매칭했다.

자세한 테스트 시나리오는 아래 링크를 참조 바란다.
https://github.com/team-sallang/matching_poc/blob/main/docs/k6-testing.md

테스트 결과

발견된 문제점

1. 매칭 성공률이 매우 낮다.
   • worker가 한 번에 한 쌍만 매칭하여 처리 속도가 느렸고, 이로 인해 매칭 성공률이 낮았다.
2. 타임아웃 대량 발생(9,713건)
   • 매칭되지 못하고 TimeOut된 사용자가 대량 발생했다.
   • 타임아웃된 사용자를 자동으로 정리하는 로직이 없어, 큐에 불필요한 사용자가 남아 있었다.
3. HTTP 실패율 1.83%
   • 목표인 1% 미만을 초과하였다. 시스템 부하로 인한 일시적 오류로 보였다.

원인 분석

문제의 핵심은 Worker 처리량 부족과 타임아웃된 사용자였다.

1. worker가 한 tick에서 1쌍만 매칭 → 처리 속도가 너무 느림
2. 타임아웃된 사용자 정리 로직 부재 → 타임아웃 사용자가 큐에 남아 Worker가 불필요하게 스캔

이러한 문제들을 개선해 보았다.

개선 과정

1차 개선: worker 배치 처리 및 타임아웃 정리 로직 추가

변경 사항

• Worker가 한 번의 tick에서 최대 10쌍까지 매칭하도록 변경하였다. (이전: 1쌍)

private static final int MAX_MATCHES_PER_TICK = 10; // 한 tick에서 최대 매칭 수

// Worker 로직
for (int i = 0; i < candidates.size() && matchCount < MAX_MATCHES_PER_TICK; i++) {
    // ... 매칭 로직 ...
    if (result == 1L) {
        matchCount++;
        // 최대 10쌍까지 매칭
    }
}

결과

개선된 부분

• 매칭 성공률이 크게 개선되었다. (41.98% → 68.79%)
• 타임아웃 수가 대폭 감소했다. (9,713건 → 2,224건, 약 77% 감소)

여전히 문제인 부분

• 매칭 성공률이 목표(80%)에 미달 (68.79%)
• HTTP 요청 지연이 크게 증가 (p(95) 13.42ms → 2.07s)
• HTTP 실패율 증가 (1.83% → 3.88%)

원인 분석

• 타임아웃된 사용자를 자동으로 처리하는 로직이 없어, 타임아웃 사용자가 큐에 누적되었다.
• 타임아웃된 사용자가 큐에 남아 Worker가 불필요하게 스캔하게 되었고, 실제 매칭 가능한 사용자를 찾는 데 시간이 걸렸다.
• 큐 길이가 증가하면서 Top-50 조회 시 실제 매칭 가능한 사용자 비율이 낮아졌다.

이후 1,000명 VU와 실제 사용자 행동을 최대한 반영해서 테스트를 진행하기로 결정하였다.

2차: 타임아웃 정리 로직 추가 및 사용자 행동 시뮬레이션 반영

변경 사항

• 20초 이상 대기한 사용자를 자동으로 큐에서 제거하는 로직을 추가했다.

private static final long MATCH_TIMEOUT_MS = 20_000L; // 20초

private void cleanupTimeoutUsers(List<String> candidates) {
    long now = System.currentTimeMillis();

    for (String userId : candidates) {
        if (!isWaiting(userId)) continue;

        Long lastJoinAt = redisService.getLastJoinAt(userId);
        if (lastJoinAt == null) continue;

        long waitingTime = now - lastJoinAt;
        if (waitingTime >= MATCH_TIMEOUT_MS) {
            // 큐에서 제거하고 상태를 IDLE로 변경
            redisService.removeFromQueue(userId);
            redisService.setStatus(userId, Status.IDLE.name());
        }
    }
}

• 사용자 행동에 맞춘 시나리오 변경

1. Join Queue: POST /queue/join 호출
2. Status Polling: GET /queue/status/{userId} 반복 호출 (MATCHED까지 대기 또는 타임아웃)
3. 성공 시나리오
   • POST /queue/ack 호출
   • 30초~5분 랜덤 대기 (실제 사용자가 매칭 후 대화/게임 시간 시뮬레이션)
   • 다음 매칭 시도로 이동
4. 타임아웃 시나리오
   • POST /queue/leave 호출 (큐에서 떠남)
   • 5~10초 랜덤 대기
   • 다음 매칭 시도로 이동
5. RAMP_DOWN 단계
   • 테스트 종료 시 자동으로 사용자 정리 (Leave 또는 ACK)

테스트 결과

상세 결과

• 총 iterations: 78,282건
• 총 HTTP 요청: 93,787건
• 평균 iteration duration: 245.94ms
• 실행 시간: 2분 29.8초
• 모든 threshold 통과

K6 테스트 결과

Redis Lua Script latency 결과

다음 결과를 통해 Lua Script를 통해 결정되는 사용자 상태의 Latency가 큰 영향을 끼치지 않는 것을 확인할 수 있었다.

결론

프로젝트 목표

1. 1,000명 동시 사용자 환경에서의 성능 검증

   • 실 서비스에서 Redis 기반 매칭 시스템이 적합한지 확인 (달성)
   • 1,000 VU 기준으로 처리 속도와 안정성 검증 (달성)

2. 매칭 성능 목표

   • JoinQueue 응답 시간: 50ms 이하 (달성)

   • 매칭 결정 평균 시간: 200ms 이하 (미달성)

결과적으로 Redis 기반 매칭 시스템은 전체 구조와 목적에 잘 부합하는 것으로 판단된다. 다만 매칭 결정 평균 시간이 목표 성능에 도달하지 못한 부분이 아쉬웠다. 이는 Worker가 50ms tick을 거치기도 하고, Top-50만 조회하는 구조에서 기인한 것으로 보인다. 이 과정은 실제로 배포하여 사용자 경험을 확보해서, 적절한 성능 목표를 재설정해서 튜닝 및 테스트를 진행하며 개선해야 할 것으로 판단된다.

프로젝트를 하면서 배운 점

1. Worker 배치 처리의 중요성

초기 구현(1쌍/tick)의 매칭 성공률은 41.98%였으나, 배치 처리(10쌍/tick)를 도입하여 최종적으로 99.57%의 성공률을 달성할 수 있었다.
한 tick에서 여러 쌍을 매칭하면 처리량이 크게 향상되지만, 너무 많이 매칭할 경우 worker tick 시간이 증가하므로 사용자 경험을 고려한 적절한 값 선택이 필요하다.

2. 자동 로직의 중요성

초기 테스트에서는 9,713건의 타임아웃이 발생해 큐에 불필요한 사용자가 누적되었고, worker 성능을 저하시켰다.
타임아웃 기반 자동 정리 로직을 추가하자 타임아웃이 11건으로 감소했으며, 20초 타임아웃 설정이 해당 서비스에 비교적 적절한 값으로 보였다.

3. 현실적인 부하 테스트 시나리오의 필요성

초기 시나리오는 단순 반복 구조로, 부하가 지속적으로 높아 실제 사용자 패턴을 반영하지 못해 정확한 성능 검증이 어려웠다.
실제 사용자가 약 30초~5분 간 대화한다고 가정하고 시나리오를 구성하자, 대기 시간으로 부하가 분산되어 보다 현실적인 성능 검증이 가능했다.

실행 중인 프로그램을 의미하는 것입니다. 운영 체제가 메모리에 프로그램을 올리고 실행하며, 그 프로그램은 하나의 프로세스가 되며, 각 프로세스는 독립적인 메모리 공간(코드, 데이터, 스택, 힙)을 할당받으며, 다른 프로세스의 메모리 영역에 직접 접근할 수 없습니다.

Process의 특징

• 독립성 : 각 프로세스는 고유한 메모리 공간과 자원(파일 핸들, 네트워크 포트 등)을 가집니다.
• 오버헤드 : 프로세스를 생성하거나 전환(Context Switching)할 때 상대적으로 많은 자원이 소모됩니다.
• 예시 : 웹 브라우저, 워드 프로세서, 음악 플레이어 각각이 별도의 프로세스입니다.

그에 대한 예시로 빠르게 알아볼 수 있는 방법 중에 하나는

다음과 같이 [작업관리자] 에서 볼 수 있는 프로세스입니다. 다음 프로세스들은 각 프로세스들에게 영향을 끼치지 않으며, 컴퓨터 내에서 필요에 의해 수많은 프로세스들이 돌아갑니다.

Thread란?

프로세스 내에서 실행되는 흐름의 단위입니다. 하나의 프로세스는 하나 이상의 스레드를 가질 수 있습니다. 스레드는 같은 프로세스에 속한 다른 스레드들과 메모리 공간과 자원(파일 핸들, 네트워크 포트 등)을 공유합니다. 스레드는 프로세스 내에서 동시에 여러 작업을 할 수 있게 해줍니다.

Thread의 특징

• 자원 공유 : 같은 프로세스에 속한 스레드들은 코드, 데이터(힙)을 공유합니다. 또한 각 스레드는 고유한 스택(stack)과 레지스터(register)를 지닙니다.
• 경량성 : 스레드를 생성하거나 전환할 때 프로세스보다 적은 자원이 소모됩니다. 이로 인해 효율적인 동시 작업 처리가 가능합니다.
• 예시 : Vscode에서 자동 저장 기능과 auto formatting 기능을 사용할 때, 별도의 스레드로 구성된다는 것을 확인할 수 있습니다.

Multi-processing이란?

단어와 같이 여러 개의 프로세스를 동시에 실행해서 여러 작업을 처리하는 방식입니다.

장점

• 한 프로세스에 오류가 발생해도 다른 프로세스에 영향을 주지 않아 시스템이 안정적임. 여러 CPU 코어를 활용해 진정한 병렬 처리가 가능합니다.

  단점

• 프로세스 간 컨텍스트 스위칭(전환)이 무겁습니다.

Multi-threading이란?

멀티 스레딩은 하나의 프로세스 내에서 여러 스레드를 동시에 실행하여 작업을 처리하는 방식입니다. 스레드들은 같은 프로세스의 메모리 공간을 점유합니다.

장점

• 스레드 간 컨텍스트 스위칭이 가볍고 빠름.

  단점

• 스레드에 오류가 발생하면 메모리를 공유하기 때문에 같은 프로세스 내의 다른 스레드와 전체 프로세스에 영향을 줄 수 있어 안정성이 낮습니다. 공유 자원에 여러 스레드가 동시에 접근할 때 동기화 문제가 발생할 수 있습니다.

궁금점

• 여러 프로세스를 동시에 실행시키는 것인지? : 최신 컴퓨터가 가지고 있는 멀티 CPU를 통해 여러 프로세스를 동시에 실행시킬 수 있다. 이러한 이유 뿐만 아니라, 시분할(Time-sharing)으로 인해 빠른 속도로 전환되어 우리 눈에는 동시에 실행되는 것처럼 보이는 것이다.

JWT(JSON Web Token)에서 클레임은 크게 세 가지 종류로 나눌 수 있습니다: 등록된 클레임(Registered Claims), 공개 클레임(Public Claims), 비공개 클레임(Private Claims). 각 클레임의 특징은 다음과 같습니다.

1. 등록된 클레임 (Registered Claims)

등록된 클레임은 JWT의 표준화된 클레임으로, 특정한 의미를 가지며, 일반적으로 사용됩니다. 주요 클레임은 다음과 같습니다:

• iss (Issuer): 토큰의 발급자., 누가 토큰을 발급했는지 나타냄. 임의로 정의한 문자열 또는 URI(uniform resource identifier)의 형식을 지닌다.
• sub (Subject): 토큰이 대상으로 하는 주체. 일반적으로 주제에 대한 설명을 나타냄. 토큰 주제는 발급자가 정의하는 문맥상 또는 전역으로 유일한 값을 가져야 한다. 문자열 또는 URL 형식을 가진다.
• aud (Audience): 이 토큰을 사용할 수 있는 대상., 주로 보호된 리소스의 URL을 값으로 설정한다.
• exp (Expiration Time): 토큰의 만료 시간., 일반적으로 UNIX epoch 시간을 사용한다.
  • UNIX epoch 시간: 세계 협정시(UTC)부터의 경과 시간을 초로 환산해 정수로 나타낸 시간을 의미함.
• nbf (Not Before): 이 클레임이 설정된 시간 이전에는 유효하지 않음을 나타냄. 토큰이 유효해지는 시간 이전에 미리 발급되는 경우에 사용됨.
• iat (Issued At): 토큰이 발급된 시간.
• jti (JWT ID): 토큰의 고유 식별자. 같은 값을 가질 확률이 없는 암호학적 방법으로 생성돼어야 함. 공격자가 JWT를 재사용하는 것을 방지하기 위함.

이 클레임들은 JWT의 유효성을 검증하고, 정보의 해석을 용이하게 합니다.

2. 공개 클레임 (Public Claims)

공개 클레임은 JWT의 사용자 정의 클레임으로, 다른 시스템에서 이해할 수 있도록 정의된 클레임입니다. 표준 클레임에 덧붙여 공개해도 무방한 페이로드를 칭합니다. URI를 사용하여 충돌을 방지할 수 있으며, 예를 들어 http://example.com/role과 같은 클레임을 사용할 수 있습니다. 이름 충돌을 방지하기 위해 IANA JWT 클레임 저장소에 클레임을 등록하거나 합리적인 예방 조치를 취해야 합니다.

3. 비공개 클레임 (Private Claims)

비공식적인 클레임으로, 특정 애플리케이션이나 서비스 간에만 사용되는 클레임입니다. 비공개 클레임은 충돌을 피하기 위해 고유한 이름을 선택해야 하지만, URI를 사용할 필요는 없습니다. 예를 들어 user_id, user_preferences와 같은 서비스 도메인 내에서 필요한 이름과 값에 해당하는 클레임이 이에 해당합니다. JWT 발급자와 사용자 간에 사용하기로 약속한 클레임이라고 생각하면 편합니다.

요약

• 등록된 클레임: 표준화된 클레임, JWT의 유효성 검증에 사용.
• 공개 클레임: 사용자 정의 클레임, 다른 시스템 간의 데이터 공유에 사용.
• 비공개 클레임: 특정 애플리케이션에서만 이해되는 클레임, 외부 시스템에서는 이해할 수 없음.

이렇게 각 클레임의 용도와 특징을 이해하면 JWT를 더 효과적으로 사용할 수 있습니다.

@router.delete("", status_code=204)
@inject
def delete_user(
    user_id: str, user_service: UserService = Depends(Provide[Container.user_service])
):
    # TODO : 다른 유저를 삭제할 수 없도록 토큰에서 유저 아이디를 구한다.
    user_service.delete_user(user_id)

HTTP DELETE 메서드의 응답 코드를 204로 지정함. MDN 문서에 따르면 HTTP 상태 코드는 다음과 같다.

MDN 웹 문서(영어: MDN Web Docs, 이전 모질라 개발자 네트워크, 모질라 개발자 센터)는 웹 개발자들을 위한 문서 및 학습 자료 사이트

204 코드란?

• 204 No Content
  • HTTP 204 No Content 성공 상태 응답 코드는 요청이 성공했으나 클라이언트가 현재 페이지에서 벗어나지 않아도 된다는 것을 나타냄
  • 예를 들어, “저장 후 편집 계속” 등의 기능을 구현할 때 사용됨.
  • 204 응답은 기본적으로 캐시 가능하며, 캐시에서 가져온 응답일 경우 ETag 헤더를 포함함.

from database import SessionLocal
from user.infra.db_models.user import User
from datetime import datetime
from utils.crypto import Crypto

with SessionLocal() as db:
    crypto = Crypto()
    for i in range(50):
        user = User(
            id=f"UserId-{str(i).zfill(2)}",
            name=f"TestUser{i}",
            email=f"TestUser{i}@test.com",
            password=crypto.encrypt("test"),
            memo=None,
            created_at=datetime.now(),
            updated_at=datetime.now(),
        )
        db.add(user)
    db.commit() # 변경 사항 커밋

다음과 같이 작성하면 한 번에 많은 데이터를 추가할 수 있다.

db_utils.py

from sqlalchemy import inspect


# 자동으로 할당되어 만들어주는 코드로 보인다.
def row_to_dict(row) -> dict:
    return {key: getattr(row, key) for key in inspect(row).attrs.keys()}

User.py

from dataclasses import dataclass
from datetime import datetime

#  id 속성이 없고, 데이터만 가지고 있는 데메인 객체를 값 객체라고 함.
@dataclass
class Profile:
    name: str
    email: str

# 도메인 객체를 다루기 쉽게 하기 위하여 dataclass로 선언하였음.
@dataclass
class User:
    id: str
    profile: Profile
    # name: str
    # email: str
    password: str
    memo : str | None
    created_at: datetime
    updated_at : datetime

user_repo.py

    def find_by_email(self, email: str) -> UserVO:
        with SessionLocal() as db:
            user = db.query(User).filter(User.email == email).first()

        if not user:
            raise HTTPException(status_code=422)

        return UserVo(**row_to_dict(row))

해당 코드를 수행하는 도중 제대로 데이터가 맵핑되지 않는 문제점이 생겼다.

해결 방법

해결하기 위해서 먼저 문제점을 확인할 필요가 있었다. 중요한 거는 VO 객체에서 자동으로 Profile 객체를 찾아가 맵핑을 해주지 못한다는 문제점이 있었다.

이를 해결해주기 위해서 어쩔 수 없이 직접적으로 맵핑을 해주는 코드를 작성해줄 필요가 있었고, 추후에 해당 각 종속 관계에 있는 객체를 명시해서 자동으로 할당해주는 방법을 찾을 필요가 있어 보였다.

다음 코드는 수정 코드이다.

db_utils.py (수정 후)

from datetime import datetime
from sqlalchemy import inspect
from user.domain.user import User as UserVO, Profile


# 자동으로 할당되어 만들어주는 코드로 보인다.
def row_to_dict(row) -> dict:
    return {key: getattr(row, key) for key in inspect(row).attrs.keys()}


# user mapping 함수 # 해당 코드는 나중에 data_mapper.py 로 파일을 따로 만들어서 관리하거나 하자.
def map_user(row) -> UserVO:
    user_dict = row_to_dict(row)

    # Profile 객체 생성
    profile = Profile(name=user_dict["name"], email=user_dict["email"])

    # User 객체 생성
    user = UserVO(
        id=user_dict["id"],
        profile=profile,
        password=user_dict["password"],
        memo=user_dict["memo"],
        created_at=user_dict["created_at"],
        updated_at=user_dict["updated_at"],
    )

    return user

• 서로소 집합(Disjoint Sets) 란 공통 원소가 없는 두 집합을 의미.

  서로소 집합 자료 구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 서로소 집합 자료구조는 두 종류의 연산을 지원.
  • 합집합(union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산.
  • 찾기(find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산.
• 서로소 집합 자료구조는 합치기 차기(Union find)자료구조라고 불리기도 함.

  여러 개의 합치기 연산이 주어졌을 때 동작과정

• 합치기(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인합니다.
  • 1) A와 B의 루트 노드 A',B'를 각각 찾습니다.
  • 2) A'와 B'의 부모 노드로 설정합니다.
• 모든 합집합 (Union) 연산을 처리할 때까지 1번의 과정을 반복합니다.

  서로소 집합 자료구조 : 기본적인 구현 방법

  # 서로소 집합 자료 구조: 기본적인 구현 방법(Python)
  
  

특정 원소가 속한 집합을 찾기

def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != x: return find_parent(parent, parent[x]) return x

두 원소가 속한 집합을 합치기

def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b)

if a < b:
    parent[b] = a
else:
    parent[a] = b

노드의 개수와 간선(union 연산)의 개수 입력 받기

v, e = map(int, input().split()) parent = [0] * (v + 1) # 부모 테이블 초기화

부토 테이블에서 부모를 자기 자신으로 초기화

for i in range(1, v + 1): parent[i] = i

Union 연산을 각각 수행

for i in range(e): a, b = map(int, input().split()) union_parent(parent, a, b)

각 원소가 속한 집합 출력하기

print("각 원소가 속한 집합:", end="") for i in range(1, v + 1): print(find_parent(parent, i), end=" ")

print()

부모 테이블 내용 출력하기

print("부모테이블: ", end="") for i in range(1, v + 1): print(parent[i], end=" ")

## 서로소 집합 자료구조 : 기본적인 구현 방법의 문제점
- 합집합 연산이 편향되게 이루어지는 경우 찾기(Find)함수가 비효율적으로 동작함.
- 최악의 경우에는 find(찾기)함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(v)입니다. 
   - ![](https://velog.velcdn.com/images/j_k_/post/986006f3-b522-4971-a180-b8bc1b395b27/image.png)

### 서로소 집합 자료구조 : 경로 압축
- 찾기(find) 함수를 최적화하기 위한 방법으로 경로 압축(path Compression)을 이용할 수 있습니다.
   - 찾기(find)함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신합니다.
   ```python
    # 특정 원소가 속한 집합을 찾기
    def find_parent(parent, x):
        # 루트 노드를 찾을 때까지 재귀 호출
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
            # return find_parent(parent, parent[x])
        return x
    ```
   - 즉 부모테이블에서 노드의 바로 위 부모 테이블을 가리키게 만든 것임.
## 서로소 집합을 활용한 사이클 판별
- 서로소 집합을 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있습니다
   - 참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있습니다.
### 사이클 판별 알고리즘 개요
1. 각 간선을 하나씩 확인하여 두 노드의 루트 노드를 확인합니다.
   - 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행합니다.
   - 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것입니다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다.

------
# 신장 트리
- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미
   - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함.
   ![](https://velog.velcdn.com/images/j_k_/post/da69a584-3223-48a1-9afc-a2b38b27c381/image.png)
## 최소 신장 트리
**예시**
- N 개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 고려.
   - 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치해야 함.
   ![](https://velog.velcdn.com/images/j_k_/post/113868c5-a309-46e4-93d9-5f89800d7254/image.png)
## 크루스칼 알고리즘
- 대표적인 최소 신장 트리 알고리즘
- 그리디 알고리즘으로 분류됨.
### 크루스칼 알고리즘 동작과정
1. 간선 데이터를 비용에 따라 오름차순으로 정렬합니다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는 지 확인합니다.
   - 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킵니다.
   - 사이클이 발생하는 경우 최소 신장 트리에 포함하지 않습니다.
3. 모든 간선에 대하여 2번의 과정을 반복합니다.
### Python 코드
```python
# 크루스칼 알고리즘

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a > b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)  # 부모 테이블 초기화

# 모든 간성르 담을 리스트와 최종 비용을 담을 함수
edges = []
result = 0

# 부토 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i


for i in range(e):
    a, b, cost = map(int, input().split())
    # 사이클이 발생한 경우 종료
    edges.append((cost, a,b,))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges:
    cost,a,b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent, b):
        union_parent(parent, a,b)
        result += cost

print(result)

크루스칼 알고리즘 성능 분석

• 크루스칼 알고리즘은 간선의 개수가 E개일 때, O(ELogE)의 시간 복잡도를 가집니다.
• 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선의 정렬을 수행하는 부분입니다.
  • 표준 라이브러리를 이용해 E개의 데이터를 정렬하기 위한 시간 복잡도는 O(ElogE)입니다.

위상 정렬

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미

  진입차수와 진출 차수

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

  위상 정렬 알고리즘 동작 과정(with Queue)

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   • 새롭게 진입 차수가 0인 된 노드를 큐에 넣는다.

결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

위상 정렬의 특징

• 위상 정렬은 DAG에 대해서만 수행할 수 있습니다.
  • DAG (Direct Acyclic Graph): 순환하지 않는 방향 그래프
• 위상 정렬에서는 여러 가지 답이 존재할 수 있습니다.
  • 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재합니다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있습니다.
  • 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못합니다.
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있습니다.

위상 정렬 알고리즘 코드

# 위상 정렬 알고리즘

from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for _ in range(v + 1)]

# 방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)  # 정점 a에서 b로 이동 가능
    # 진입 차수를 1 증가
    indegree[b] += 1


# 위상 정렬 함수
def topology_sort():
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)
    # 큐가 빌때까지 반복
    while q:
        now = q.popleft()
        result.append(now)
        # 해당 원소의 연결된 노드들의 진입차수에서 1을 빼기
        for i in graph[now]:
            indegree[i] -= 1
            if not indegree[i]:
                q.append(i)
    # 위상 정렬을 수행한 결과 출력
    for i in result:
        print(i, end=" ")


topology_sort()

위상 정렬 알고리즘 성능 분석

• 위상 정렬을 위해 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거해야 합니다.
  • 위상 정렬 알고리즘의 시간 복잡도는 O(v+e)입니다.

입력

• 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

• 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

• 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

풀이

# [백준] 7576번 토마토
from collections import deque
import sys

input = sys.stdin.readline

n,m = map(int,input().split())

array = []
for _ in range(m):
    array.append(list(map(int,input().split())))
dx = [0,0,-1,1]
dy = [-1,1,0,0]

q= deque()

def bfs():
    while q:
        ax, ay = q.popleft()
        for i in range(4):
            nx = ax + dx[i]
            ny = ay + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if array[ny][nx] == 0: 
                    array[ny][nx] = array[ay][ax] + 1
                    q.append([nx,ny])

for x in range(n):
    for y in range(m):
        if array[y][x] == 1:
            q.append([x,y])

bfs()

day = 0

for line in array:
    for item in line:
        if not item:
            print(-1)
            exit()
    day = max(day, max(line))

print(day-1)

후기

• 좀 더 다양한 방식으로 많이 풀어보는 게 정답일거라고 생각이 든다.

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 103) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

  입력의 마지막 줄에는 0이 두 개 주어진다.

출력

• 각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

풀이

import sys
import heapq
from collections import deque
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    dist =[INF] * (n)

    dist[start] = 0
    q = []
    heapq.heappush(q,(0,start))
    while q:
        distance, now = heapq.heappop(q)
        if dist[now] < distance:
            continue
        for i in array[now]:
            if edges[now][i[0]]: continue
            cost =  distance + i[1]
            if dist[i[0]] > cost:
                dist[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))
    return dist

def bfs():
    q = deque()
    q.append(d)

    while q:
        current = q.popleft()

        if current == s:
            continue
        for node, cost in array_inv[current]:
            if dist[node] + cost == dist[current] and not edges[node][current]:
                edges[node][current] = True
                q.append(node)

result = []
while 1:
    n,m = map(int,input().split())

    if not (n and m):
        break
    s,d = map(int,input().split())

    array =[[] for _ in range(n)]
    array_inv =[[] for _ in range(n)]
    edges = [ [False]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        u,v,p = map(int,input().split())
        array[u].append([v,p])
        array_inv[v].append([u,p])

    dist = dijkstra(s)
    bfs()
    dist = dijkstra(s)
    result.append(-1 if dist[d] == INF else dist[d])

for a in result:
    print(a)

후기

• 솔직히 해당 문제는 풀이를 보면서 풀은 문제이기도 하고, bfs를 오랜만에 풀어봤더니 알고리즘이 잘 생각나지 않아 잘 풀지 못했던 문제이다. BFS에 다시 익숙해지고 나서 풀어야 겠다.

입력

• 첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다
  • 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
  • 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
  • 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
  • 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

    교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

• 테스트 케이스마다

  입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

풀이

# 백준 9370 미확인 도착지
import heapq
import sys
input = sys.stdin.readline
INF =int(1e9)

def dijkstra(start, distance):
    distance[start] =0
    q =[]
    heapq.heappush(q,(0,start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in array[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost                
                heapq.heappush(q,(cost,i[0]))



T = int(input())
result = [[] for _ in range(T)]
for c in range(T):
    n,m,t = map(int,input().split())
    s,g,h = map(int,input().split())
    array = [[] for _ in range(n+1)]
    distance =[INF for _ in range(n+1)]
    dist_g = [INF for _ in range(n+1)]
    dist_h = [INF for _ in range(n+1)]
    ends= []
    for _ in range(m):
        a,b,d = map(int,input().split())
        array[a].append([b,d])
        array[b].append([a,d])
    for _ in range(t):
        heapq.heappush(ends,int(input()))
    dijkstra(s, distance)
    dijkstra(g, dist_g)
    dijkstra(h, dist_h)
    for end in ends:
        if (distance[end] == distance[g] + dist_g[h] + dist_h[end]) or (distance[end] == distance[h] + dist_h[g] + dist_g[end]):
            heapq.heappush(result[c], end)

for i in result:
    i.sort()
    print(*i)

후기

• 해당 문제를 푸는 데에 있어서 가장 어려웠던 점은 아이디어를 떠올리는 점하고 시간 복잡도를 고려하고 푸는 것과 그리고 정렬하여 어떻게 출력하는 데에 있어서 시간이 오래 걸렸다. 으어 언제쯤에 적응할 수 있을까. 걱정이 된다.

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

해당 문제는 메타코드 M의 강의 기출 문제 관련 참고집입니다.

1. 소프트웨어 개발 프레임워크와 관련된 설명으로 거리가 먼 것은?

• 소프트웨어 개발 프레임워크
  • 애플리케이션 개발을 위한 구조적 토대와 공통된 기능을 제공하는 재사용 가능한 플랫폼
  • 특징
    • 개발해야할 애플리케이션의 일부분이 이미 구현되어 있어 동일한 로직 반복을 줄일 수 있음.
    • 생산성 향상과 유지보수성 향상 등의 장점이 있음.
    • 애플리케이션의 흐름을 개발자가 아닌 프레임워크가 제어하는 제어의 역행 방식 IoC, Inversion of Control

5. 암호화 키와 복호화 키가 동일한 암호화 알고리즘은?

• AES : 대칭키 알고리즘,
• RSA, ECC, Diffie-Hellman : 모두 공개키(비대칭키)알고리즘임.

9. DES는 몇 비트의 알고리즘인가?

• 64비트의 알고리즘임.

10. 테일러링 개발방법론의 내부 기준에 부합하지 않은 것은?

• 국제 품질 기준은 외부 기분에 해당하므로 내부 기준이 아님.

22. 각 시스템 간에 공유 디스크를 중심으로 클러스터링으로 엮어 다수의 시스템을 동시에 연결할 수 있고, 조직 및 기업의 기간 업부 서버 등의 안정성을 높이기 위해 사용되는 기술은?

• HACMP(High Availablity Cluster Multi-Processing)는 고가용성을 제공하는 IBM사의 클러스터링 기술임. 공유 디스크를 중심으로 여러 시스템을 연결하여 하나의 시스템이 실패하더라도 서비스가 중단되지 않도록 보장함.

23. 소프트웨어 비용산정 기법 중 개발 유형으로

Organic, Semi-detach, Embedded로 구분되는 것은?

• COCOMO는 보헴(Boehm)이 제안한 비용 산정 모형으로, 개발 유형을 조직형(Organic), 반분리형(Semi-detached), 내장형(Embedded)으로 구분함

24. Hadoop과 관계형 데이터베이스 간에 데이트를 전송할 수 있도록 설계된 도구는?

• Sqoop은 Hadoop과 관계형 데이터베이스 간의 데이터 전송을 위한 도구임. 대용량 데이터를 효율적으로 이동시킬 수 있으며, 양방향 데이터 전송을 지원함.

25. 해시(Hash) 기법에 대한 설명으로 틀린 것은?

• 해시 함수(Hash Functions)
  • 입력 데이터를 고정된 길이의 고유한 해시 값으로 변환하는 함수
  • 주로 데이터 무결성 확인에 사용
  • 특징
    • 임의 길이의 데이터를 입력받아 고정된 길이의 해시값으로 변환
    • 해시 함수는 일방향 함수
    • 레인보우 테이블 공격에 취약 → Salt Key 추가
• 해시 함수는 일방향 함수로, 임의 길이의 입력을 고정 길이의 출력으로 변환함. 주로 무결성 검증이나 전자 서명에 사용되며, 공개키 암호화 방식의 키 생성에는 사용되지 않음.

28. 소프트웨어 개발 표준 중 소프트웨어 품질 및 생산성 향상을 위해 소프트웨어 프로세스를 평가 및 개선하는 국제 표준은?

• SPICE : 소프트웨어 프로세스 평가 및 개선을 위한 국제 표준임. ISO/IEC 15504로도 알려져 있으며, 프로세스의 능력 수준을 평가하고 개선하는데 사용됨.

30. DoS(Denial of Service) 공격과 관련한 내용으로 틀린 것은?

• Dos
  • 서비스 거부 공격으로, 단일 공격자(시스템)가 특정 시스템이나 네트워크 서비스의 가용성을 방해하는 공격
  • 주로 대량의 트래픽을 보내거나 시스템 자원을 고갈시켜 서비스를 마비시키는 방식으로 이루어짐.

31. PUTNAM 모형을 기초로 해서 만든 자동화 추정 도구는?

• SLIM(Software Lifecycle Management)은 Putnam이 제안한 소프트웨어 생명주기 모형을 기초로 만든 자동화 추정 도구임. Rayleigh-Norden 곡선을 이용하여 프로젝트의 자원과 시간을 산정함.

32. 국내 IT 서비스 경쟁력 강화를 목표로 개발

되었으며 인프라 제어 및 관리 환경, 실행 환경, 개발 환경, 서비스 환경, 운영 환경으로 구성된 개방형 클라우드 컴퓨팅 플랫폼은?

• PaaS-TA는 한국 정부에서 개발한 개방형 클라우드 플랫폼임. 인프라 제어/관리, 실행, 개발, 서비스, 운영 환경 등으로 구성되어 있으며, 국내 IT 서비스 경쟁력 강화를 목표로 함.

36. 침입탐지 시스템(IDS, Intrusion Detection

System)에 대한 설명으로 틀린 것은?

• Anomaly Detection(이상 탐지)는 정상적인 행위 패턴을 기준으로 비정상적인 행위를 탐지함

37. 기기를 키오스크에 갖다 대면 원하는 데이터

를 바로 가져올 수 있는 기술로, 10cm 이내 근 접 거리에서 기가급 속도로 데이터 전송이 가능 한 초고속 NFC 기술은?

• Zing

38. TCP/IP 기반 네트워크에서 동작하는 발행-구

독 기반의 메시징 프로토콜로 최근 IoT 환경에서 많이 사용되고 있는 프로토콜은?

• MQTT(Message Queuing Telemetry Transport)는 발행-구독 기반의 경량 메시징 프로토콜임. 제한된 네트워크 대역폭과 리소스를 가진 IoT 환경에서 많이 사용되며, 신뢰성 있는 메시지 전달을 보장함.

39. 소프트웨어 각 기능의 원시 코드 라인 수의 비관치, 낙관치, 중간치를 측정하여 예측치를 구하고 이를 이용하여 비용을 산정하는 기법은?

• LOC 기법은 소프트웨어 각 기능의 원시 코드 라인 수에 대한 비관치, 낙관치, 중간치를 측정하여예측치를 구함. 예측치는 (낙관치 + 4*중간치 + 비관치)를 6으로 나눈 값

41. 실무적으로 검증된 보안 개발 방법론 중 하나로써, SW 보안의 모범 사례를 SDLC(Software Development Life Cycle)에 통합한 소프트웨어 개발 보안 생명주기 방법론은?

• Seven Touchpoints는 소프트웨어 개발 생명 주기에 보안을 통합한 방법론임. 코드 검토, 아키텍처 분석, 침투 테스트 등 7가지 보안 강화 포인트를 제시하여 안전한 소프트웨어 개발을 지원함.\

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

해당 문제는 메타코드 M의 강의 기출 문제 관련 참고집입니다.

6. IPv6에 대한 설명으로 틀린 것은?

• IPv6는 16비트 씩 8 부분으로 구성되며 16진수로 표현됨.
• IPv4는 8비트 씩 4 부분의 10진수로 표현됨.

39. 은행가 알고리즘은 교착 상태의 해결 방법 중 어떤 기법에 해당하는 가?

• 은행가 알고리즘은 교착 상태 회피(Avoidance) 기법의 대표적인 예시임. 시스템이 안전상태를 유지하도록 자원 요청을 검사하고, 자원 할당 전에 미리 교착 상태 가능성을 검사하여 예방하는 방식임.

42. 다음 중 java 언어에서 접근제어자가 아닌 것은?

• static : 접근제어자가 아닌 변수나 메소드의 특성을 지정하는 제어자임.

43. IPv6의 전송 방식으로 거리가 먼 것은?

• : IPv6는 IPv4와 달리 Broadcast 주소를 사용하지 않음. IPv6에서는 Broadcast 대신 Multicast를 사용하여 그룹 통신을 수행함.

해당 단원은 생각보다 틀린 게 없어서, 오답 노트가 적음.

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

해당 문제는 메타코드 M의 강의 기출 문제 관련 참고집입니다.

1. 데이터베이스의 인덱스(INDEX)와 관련한 설명으로 틀린 것은?

• 인덱스의 추가는 CREATE INDEX, 삭제는 DROP INDEX 명령어를 사용함. TRUNCATE는 테이블의 모든 데이터를 삭제하는 명령어이므로 인덱스 삭제와는 관계가 없음.

7. 한 릴레이션의 기본 키를 구성하는 어떤 속성 값도 null 값이나 중복값을 가질 수 없음을 의미하는 무결성의 종류는?

• 개체 무결성은 기본 키를 구성하는 모든 속성은 NULL 값이나 중복값을 가질 수 없다는 규칙임.

9. 분산 데이터베이스 목표 중 데이터베이스의 분산된 물리적 환경에서, 특정 지역의 컴퓨터 시스템이나 네트워크에 장애가 발생하여도 데이터 무결성이 보장된다는 것은?

• 장애 투명성

11. 릴레이션 내 모든 튜플에 대하여 유일성은 만족시키지만 최소성은 만족시키지 못하는 키는?

• 슈퍼키 : 튜플을 유일하게 식별할 수 있는 속성 또는 속성의 집합임. 유일성은 만족하지만, 꼭 필요하지 않은 속성이 포함될 수 있어, 최소성은 만족하지 않을 수 있음.

13. 병렬 데이터베이스 환경 중 수평 분할에서 활용되는 분할 기법이 아닌 것은?

• 파티셔닝 기법
  • 대용량의 데이터를 파티션이라는 작은 논리 단위로 나누어 성능을 최적화하는 것
  • 특징
    • 수평 분할(행)에서 주로 활용되는 분할 기법
  • 종류
    • 범위 분할
    • 목록 분할
    • 해시 분할
    • 조합 분할
    • 라운드 로빈

14. 물리적 데이터베이스 설계에 대한 설명으로 거리가 가장 먼 것은?

• 트랜잭션의 인터페이스 설계는 논리적 설계 단계에서 다룸.

15. 관계 대수에 대한 설명으로 옳지 않은 것은?

• 관계 대수는 절차적, 관계 해석은 비 절차적
• 관계 대수는 데이터를 어떻게 처리할 지 명시적으로 정의
• 관계 해석은 무엇을 원하는 지 명시
• 관계 대수
  • 관계형 데이터베이스를 다루는 수학적 연산 체계로, 데이터베이스 검색에 대한 이론적 기반이 됨.
  • 특징
    • 릴레이션 조작을 위한 연산의 집합으로, 피 연산자와 결과가 모두 릴레이션
    • 질의에 대한 해를 구하기 위해 수행해야 할 연산의 순서를 명시
    • 일반 집합 연산과 순수 관계 연산으로 구분

16. SQL의 분류 중 DDL 에 해당하지 않은 것은?

• DDL : 데이터의 구조를 정의하고 변경
  • 도메인, 스키마, 테이블, 뷰, 인덱스 등의 데이터베이스 객체를 생성, 수정, 삭제하는 작업 수행
  • 종류 : Create, ALTER, DROP, TRUNCATE
• UPDATE는 DML(Data Manipulation Language)에 속하는 명령어임.

19. 뷰에 대한 설명으로 옳지 않은 것은?

• 뷰는 실제 데이터를 가지고 있지 않은 가상 테이블이기 때문에 데이터의 삽입, 삭제, 갱신 연산에 많은 제약이 따름. 특히 여러 테이블을 조인한 뷰나 그룹함수를 사용한 뷰는 데이터 갱신이 거의 불가능함.

21. 후보 키에 대한 설명으로 옳지 않은 것은?

• 외래키 : 참조 무결성 제약조건을 표현하는데 사용됨.\

22. 데이터 제어어(DCL)의 기능으로 옳지 않은 것은?

• DCL : 데이터 보안, 병행 수행 제어, 무결성 유지
• DML : 데이터 추가, INSERT 명령어 사용

24. 병행 제어를 위한 직렬화 기법으로, 트랜잭션 간의 순서를 미리 정하는 기법

• 타임스탬프 기법은 트랜잭션이 시스템에 들어온 시간을 기준으로 트랜잭션 간의 실행 순서를 미리 정하는 기법임. 각 트랜잭션에 고유한 타임스탬프 랎을 부여하여 충동이 발생하지 않도록 함.

26. COMMIT과 ROLLBACK 명령에 의해 보장받는 트랜잭션의 특성은?

• COMMIT은 모든 변경사항을 확정하고, ROLLBACK은 모든 변경사항을 취소하여 원자성을 보장함.
• 원자성(Atomicity)은 트랜잭션의 모든 연산이 전부 실 행되거나(COMMIT) 전혀 실행되지 않아야 (ROLLBACK) 한다는 특성임.

32. 데이터 베이스 전체를 정의한 것으로 데이터 개체, 관계, 제약 조건, 접근 권한, 무결성 규칙 등을 명세화한 것.

• 개념 스키마

35. 다음 중 정규화를 거치치 않아 발생하는 이상 현상이 아닌 것은?

• 정규화를 거치지 않아, 발생하는 대표적인 이상 현상은 삽입(insertion), 삭제(Deletion) , 갱신(Updata) 이상이 있음.

36. 정규화된 엔티티, 속성, 관계를 시스템 성능 향상과 개발 운영의 단순화를 위해 중복, 통합, 분리 등을 수행하는 데이터 모델링 기법은?

• 반 정규화
  • 정규회된 데이터 모델을 시스템의 성능 향상을 위해 의도적으로 중복, 통합, 분리하는 과정임. 데이터를 중복하거나 테이블을 통합/분리하는 등의 방법으로 조회 성능을 향상시키지만, 데이터의 무결성이 저하될 수 있는 단점이 있음.

38. 하나의 애트리뷰트가 가질 수 있는 원자 값들의 집합

• 도메인

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

해당 문제는 메타코드 M의 강의 기출 문제 관련 참고집입니다.

1. 자료구조에 대한 설명으로 틀린 것은?

• 자료구조의 분류
  • 선형 구조: 리스트, 스택, 큐, 데크 (deque)
  • 비선형 구조 : 트리, 그래프
  • 스택 : 서브루틴 호출, 인터럽트 처리, 수식 계산 및 수식 표기법에 응용된다.

2. 다음 중 디지털 저작권 관리(DRM) 구성 요소가 아닌 것은?

• DRM(Digital Rights Management)
  • 디지털 콘텐츠의 불법 복제와 무단 사용을 방지하는 기술
  • 디지털 미디어의 생명주기 동안 발생하는 사용 권한 관리, 과금, 유통 단계를 제어하고 관리하는 기술
  • 크랙 방지, 정책 관리, 암호화, 키 관리, 식별 기술, 저작권 표현, 암호화 파일 생성, 인증 등의 기술 요소가 있음.

3. 알고리즘 시간 복잡도 O(1)의 의미는?

• 입력 데이터 수와 관계 없이 항상 일정한 시간 소요

4. 하향식 통합 테스트를 위해 일시적으로 필요한 조건만을 가지고 임시로 제공되는 시험용 모듈은?

• 하향식 통합 테스트
  • 상위 모듈부터 하위 모듈로 테스트를 진행하는 방식
  • Stub는 아직 개발되지 않은 하위 모듈을 대신해 임시로 사용되는 모듈
  • Stub는 상위 모듈이 필요로 하는 기본 기능만 있으며 Test driver보다 작성하기 쉬움.

5. n개의 노드로 구성된 유향 그래프의 최대 간선 수는?

• 유향 그래프 : 방향이 있는 그래프
• 최대 간선 수는 n(n-1), 무향 그래프는 n(n-1)/2임.

6. 소프트웨어 프로젝트 일정이 지연된다고 해서 프로젝트 말기에 새로운 인원을 추가 투입하면, 프로젝트는 더욱 지연된다는 법칙은?

• Brooks의 법칙
• Pareto의 법칙 : 소프트웨어 테스트에서 오류의 80%는 전체 모듈의 20%에서 발견된다는 법칙

10. 다음 중 인터페이스 구현 검증 도구가 아닌 것은?

• 인터페이스 검증 도구
  • STAF
    • 서비스 호출, 컴포넌트 재사용 등 다양한 환경을 지원하는 테스트 프레임워크
    • 다양한 언어와 플랫폼을 지원하는 분산 소프트웨어 시스템의 재사용 가능한 테스트 케이스를 생성
  • Watir(Web application testing in Ruby)
    • Ruby로 작성된 웹 앱 테스트를 위한 오픈소스 브라우저 자동화 도구
  • xUnit
    • 여러 프로그래밍 언어의 단위 테스트를 지원하는 테스트 프레임워크
  • FitNesse
    • 웹 기반의 협업 테스트 도구
  • NTAF
    • FitNesse와 STAF의 장점을 결합해 개발된 테스트 자동화 프레임워크
  • Selenium
    • 다양한 브라우저와 플랫폼에서 웹앱을 테스트할 수 있는 오픈소스 브라우저 자동화 프레임워크
• SVN은 버전 관리 시스템임

11. Alpha Test, Beta test와 연관이 가장 깊은 테스트 단계는?

• 시스템 테스트
  • 시스템의 모든 기능이 통합된 상태에서 제대로 동작하는 지 테스트
• 인수 테스트
  • 시스템이 최종 사용자의 요구사항을 만족하는 지 확인하기 위한 테스트
  • 알파 테스트, 베타 테스트와 밀접한 연관
  • 알파 테스트
    • 내부 팀 또는 선택된 사용자가 통제된 개발자 환경에서 진행되는 테스트
  • 베타 테스트
    • 개발자 없이 실제 사용자가 소프트웨어를 사용해보고 피드백을 제공하는 테스트

12. 인터페이스 구현시 사용하는 기술 중 다음 내용이 설명하는 것은?

• 인터페이스 시 데이터 교환을 위한 기술
  • REST : 웹과 같은 환경에서 HTTP를 통해 클라이언트와 서버 간의 상호 작용을 정의함.
  • AJAX : JavaScript 를 사용한 비동기 통신 기술로 클라이언트와 서버 간의 xml 데이터를 주고받는 기술

13. 다음 중 디지털 저작권 관리(DRM) 구성 요소에 대한 설명이 틀린 것은?

• 콘텐츠 제공자 : 콘텐츠를 제공하는 저작권자
• 클리어링 하우스 : 키 관리 및 라이선스 발급 관리 수행
• 콘텐츠 분배자 : 암호화된 콘텐츠를 유통하고 배포하는 역할을 담당
• 패키지 : 콘텐츠를 메타데이터와 함께 배포 가능한 단위로 묶는 도구
• 보안 컨테이너 : 콘텐츠를 암호화하여 무단 접근을 방지

18. IDE(Integrated Development Environment) 도구의 각 기능에 대한 설명으로 틀린 것은?

• Complile : 저급 언어 프로그램을 고급 언어 프로그램으로 변환하는 기능

23. 다음 중 스택에 대한 설명으로 거리가 먼 것은?

• 스택은 TOP이라는 하나의 포인터만을 사용하여 데이터의 삽입과 삭제가 이루어짐. Head와 Tail 두개의 포인터를 사용하는 것은 큐(Queue)의 특징임.

24. 화이트 박스 검사 기법에 해당하는 것만으로만 짝지어 진 것은?

• 화이트 박스 테스트
  • Source code의 모든 문장을 한 번 이상 수행함으로써 진행됨.
  • 모듈 안의 작동을 직접 관찰할 수 있음.
  • 산출물의 각 기능 별로 적절한 프로그램 코드를 수행함으로써 논리적 경로를 점검함
  • 데이터 흐름 검사, 루프 검사
• 블랙 박스 테스트
  • 프로그램의 구조와 코드를 고려하지 않음.
  • 경계값 분석, 오류 예측, 동등 분할 기법(동치 클래스 분해), 원인 결과 그래프 등

25. 다음 주 해싱 함수(Hashing Function)의 종류가 아닌 것은?

• 해싱 함수
  • 입력 데이터를 고정된 크기의 고유값(해시)로 변환하는 함수
  • 시간 복잡도 O(1)
  • 제곱법 (mid-square)
    • 키 값을 제곱한 후 그 결과의 중간 부분을 해시 값으로 사용
  • 제산법 (division)
    • 키를 특정 숫자로 나눈 나머지로 해시 값으로 사용
  • 폴딩법(Folding)
    • 키를 여러 부분으로 나누고, 각 부분을 더하거나 특정 연산을 통해 해시 값으로 구하는 방식
  • 숫자 분석법(digit analysis)
    • 키의 특정 자리 숫자들을 선택하여 해시 값으로 사용하는 방식

32. 테스트 케이스 자동 생성 도구를 이용하여 테스트 데이터를 찾아내는 방법이 아닌 것은?

• 테스트 수행을 위한 보조 도구 : 드라이버
• 테스트 케이스 자동 생성 도구 : 자료 흐름도, 랜덤 테스트, 기능 테스트, 입력 도메인 분석 등

33. 다음 중 빌드 자동화 도구에 대한 설명으로 틀린 것은?

• JENKINS는 java 기반의 오픈 소수 도구이며, 주로 지속적 통합(CI) 서버로 사용됨. Groovy 기반의 안드로이드 앱 개발용 빌드 도구는 Gradle임.

34. 다음 중 테스트 드라이버에 대한 설명으로 틀린 것은?

• 상향식 통합 테스트
  • 하위 모둘에서 상위 모듈로 테스트를 진행하는 방식
  • Test driver는 아직 개발되지 않은 상위 모듈을 대신해 하위 모듈을 호출하는 역할
  • Test driver는 필요에 따라 매개 변수를 전달하고 모듈을 수행한 후에 결과를 보여줄 수 있음.
  • 테스트 대상 모듈이 호출하는 상위 모듈의 역할을 한다.

37. 블랙박스 테스트를 이용하여 발견할 수 있는 오류가 아닌 것은?

• 블랙박스 테스트는 내부 로직을 보지 않고 입출력 결과만으로 테스트하는 기법.
• 반복 조건과 루프 내의 문장 실행 여부는 프로그램의 내부 로직과 관련된 것으로, 이는 화이트 박스 테스트로 발견할 수 있는 오류임.

40. 다음 그래프에서 정점 A를 선택하여 깊이 우선 탐색(DFS)로 운행한 결과는?

• 깊이 우선 탐색(DFS)은 한 방향으로 최대한 깊이 탐색한 후, 더 이상 갈 수 없을 때 다른 방향을 탐색함. A에서 시작하여 가능한 경로를 따라가면 A→ B → D → F → E → C 순서로 탐색이 이루어짐.

41. 소프트웨어 형상관리에 대한 설명으로 가장 거리가 먼 것은?

• 대표적인 형상 관리 도구로 And, Gradle, Jenkins는 빌드 자동화 도구이며, 형상 관리 도구가 아님. 대표적인 형상 관리 도구로는 Git, SVN, CVS 등이 있음.

47. 제어 흐름 그래프가 다음과 같을 때, McCabe의 Cyclomatic 수는?

• 맥케이브 회전 복잡도(McCabe Cyclomatic Complexity)
  • 소프트웨어의 복잡도를 측정하는 지표로 프로그램의 제어 흐름 그래프를 기반으로 계산됨.
• 제어 흐름 그래프의 cyclomatic 수
  • CC = E - N + 2
    • CC 는 복잡도, E는 간선의 수, N은 노드의 수
  • 오른쪽 예시에서는 CC = 6 -5 + 2 = 3

48. 패키지 소프트웨어의 일반적인 제품 품질 요구사항 및 테스트를 위한 국제 표준은?

메타코드 M 해당 강의 보러가기 (환급형 강의)

!https://velog.velcdn.com/images/j_k_/post/d8be0d7a-a68f-486d-9f9a-0d5f014f35ff/image.png

메타코드 M 해당 강의 보러가기 (일반형 강의)

!https://velog.velcdn.com/images/j_k_/post/c64f8c60-3726-42b9-9e69-db3ada6c9894/image.png

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

해당 문제는 메타코드 M의 강의 기출 문제 관련 참고집입니다.

1. UML 다이어그램에서 순차 다이어그램에 대한 설명으로 틀린 것은?

UML 다이어그램이란?

• 주로 객체 지향 소프투웨어 개발 시 산출물을 명세화, 시각화하기 위한 표준화된 모델링 언어
• 사물 / 관계 / 다이어그램으로 구성

시퀀스 다이어그램(Sequence, 순차)

• 시스템의 동적 측면을 모델링하며, 객체 간의 상호 작용을 시간 순서에 따라 시각적으로 보여줌
• 시간의 흐름에 따라 객체들이 주고 받는 메시지의 전달 과정을 강조

2. 요구사항 분석에서 비기능적 요구 사항에 해당하는 것은?

• 비 기능적 요구사항과 기능적 요구 사항
  • 기능적 요구사항은 시스템이 (무엇을?) 해야 하는지 초점
  • 비기능적 요구사항은 시스템이 (어떻게) 해야 하는지 초점

3. GoF(Gang of Four) 디자인 패턴 중 싱글톤(singleton) 패턴에 대한 설명으로 옳은 것은?

• GOF : 디자인 패턴을 생성, 구조, 행위의 3가지 구분과 23개의 패턴으로 구분
  • 생성패턴 : 객체를 어떻게 생성하고 초기화할지에 대한 패턴
    • Factory method : 객체를 생성하기 위한 인터페이스를 정의하여 어떤 클래스가 인스턴스화 될 것인지, 서브 클래스가 결정하도록 하는 것
    • Prototype 패턴 : prototype 을 먼저 생성하고 인스턴스를 복제하고 사용하는 구조
    • singleton 패턴
      • 한 클래스에 한 객체만 존재하도록 제한
      • 생성된 객체를 어디에서든지 참조할 수 있도록 함.
    • Builder 패턴 : 객체의 생성과 표현을 분리한다.
  • 구조 패턴 : 클래스와 객체를 더 큰 구조로 조합하는 방법에 대한 패턴
    • adapter : 기존 클래스를 새로운 인터페이스에 맞게 변환한다.
  • 행위 패턴 : 객체 간의 상호 작용과 책임 분배에 대한 패턴
    • Strategy 패턴
      • 다양한 알고리즘을 캡슐화하여 알고리즘 대체가 가능하도록 한 행위 패턴
    • Mediator 패턴
      • 객체 간의 통제와 지시의 역할을 하는 중재자를 두어 객체 지향의 목표를 달성하도록 함.
  • iterator 패턴: 객체 집합을 순회하는 방법을 제공함.

4. 애자일(Agile) 소프트웨어 개발 방법론의 가치 중 옳지 않은 것은?

• Agile 방법론
  • 고객의 요구사항 변화에 빠르게 적응하고, 개발 과정에서 지속적으로 개선해 나가는 것
• 특징
  • 프로젝트의 요구사항을 모듈 중심이 아닌 기능 중심으로 개발
• 핵심 가치 4가지
  • 개인과 상호작용
  • 작동하는 소프트웨어
  • 고객과의 협력이 우선
  • 계획에 따르는 것보다는 변화에 대응하는 것이 우선

5. UML의 관계 중 일반화 관계에 대한 설명으로 가장 적절한 것은?

• 연관(Association) : 서로 어떤 방식으로 연결되어 있는지를 표현함.
• 일반화(Generalization) : 상위 개념과 하위 개념 간의 관계(과일 → 사과)
  • 하위 클래스가 상위 클래스의 속성과 기능을 물려받는 관계
• 의존(Dependency) : 한 요소가 다른 요소에게 종속적일 때의 관계(주문과 결제) : 한 요소의 변화가 다른 요소에게도 영향을 줌
• 실체화(Realization) : 추상화된 개념과 실제로 이를 구현하는 개념 사이의 관계
• 포함 (Composition)
  • 전체와 부분 간의 강한 관계(집과 방)
  • 전체 객체가 사라지면 부분 객체도 사라짐.
• 집합(Aggregation)
  • 전체와 부분 간의 느슨한 관계(도서관과 책)
  • 전체 객체와 부분 객체가 독립적으로 존재할 수 있음.

8. 럼바우(Rumbaugh) 객체지향 분석 기법의 모델링 종류가 아닌 것은?

• 럼바우(Rumbaugh) 방법론
  • 객체 모델 → 동적 모델 → 기능 모델로 나누어 순서대로 분석을 수행하는 방법
  • Object : 객체 / Dynamic : 동적 / Function : 기능
  • 객체 모델 : 시스템에 필요한 객체를 찾아내어 속성과 관계를 규정하여 다이어그램으로 표시
  • 동적 모델 : 상태 다이어그램, 사건 흐름 다이어그램 등을 통해 객체 간의 상호작용을 시간 순으로 표현
  • 기능 모델 : 시스템의 기능을 자료 흐름도(DFD)를 통해 표현

9. 객체지향 설계 원칙(SOLID) 중 개방-페쇄 원칙(Open-Closed Principle)에 대한 설명으로 옳은 것은?

• 객체 지향 설계의 원칙(SOLID)
  • 객체 지향 설계를 위한 5가지 원칙으로, 유지보수성과 확장성에 도움을 줌
  • 단일 책임의 원칙
    • 하나의 클래스는 하나의 책임만, 즉 하나의 기능이나 역할만 담당해야 함.
  • 개방-폐쇄의 원칙 (Open-closed Principle)
    • 클래스는 확장에 대해 열려 있어야 하며, 변경에 대해 닫혀있어야 함.
    • 즉 새로운 기능을 추가할 때는 기존 코드를 수정하지 말아야 함.

10. 유스케이스 다이어그램에 관련된 내용으로 틀린 것은?

• 시스템과 상호작용하는 외부시스템은 액터가 될 수 있다.
• 액터가 인식할 수 없는 시스템 내부의 기능을 하나의 유스케이스로 파악해서는 안된다.
• 하나의 액터는 여러 유스케이스와 연결될 수 있다.

15. GoF 디자인 패턴의 구조 패턴에 해당하지 않는 것 은?

• 구조 패턴
  • 클래스와 객체를 더 큰 구조로 조합하는 방법에 대한 패턴
  • Adapter, Bridge, Proxy, Decorator, Facade, Flyweight, Composite
• 생성 패턴
  • 객체를 어떻게 생성하고 초기화할지에 대한 패턴
  • Builder, Singleton, Prototype, Abstract Factory, Factory Method

16. 모듈의 응집도(Cohesion) 유형 중 가장 낮은 것은?

18. 객체 지향 설계의 SOLID 원칙 중 인터페이스 분리 원칙(ISP)에 대한 설명으로 옳은 것은 ?

• 인터페이스 분리의 원칙(Interface Segregation Principle)
  • 클라이언트는 자신이 사용하지 않는 메소드에 의존하지 않아야 함.

19. DFD의 구성요소가 아닌 것은?

• DFD : 시간의 흐름을 명확히 표현할 수 없음.(논리적 흐름 위주)
• DFD(Data Flow Diagram)의 구성 요소
  • 처리기
  • 데이터 흐름
  • 데이터 저장소
  • 단말(Terminator)

23. 애자일 개발 방법론의 스크럼(Scrum)에서 사용되는 용어와 설명이 잘못 연결된 것은?

25. 사용자 인터페이스의 기본 원칙 중 누구나 쉽게 이해하고 사용할 수 있어야 한다는 원칙은?

• 직관성 : 누구나 쉽게 이해하고 사용할 수 있어야 함.
• 유효성 : 정확하고 완벽하게 사용자의 목표가 달성되어야 함.
• 학습성 : 모두가 쉽게 배우고 사용할 수 있게 제작되어야 함.
• 유용성 : 사용자의 실수를 방지할 수 있게 제작되어야 함.

26. 다음 중 모듈의 결합도(Coupling)가 가장 높은 것은?

29. CASE(Computer-Aided Software Engineering)에 대한 설명으로 알맞은 것은?

• CASE(Computer-Aided Software Engineering)
  • 소프트웨어 생명주기의 전 단계를 연결해주고 자동화하는 소프트웨어 도구
  • SW, HW, Database, 테스트 등을 통합하여 소프트웨어를 개발하는 환경을 조성
  • 개발 과정의 속도를 향상시키며, 소프트웨어 부품의 재사용을 가능하게 함.
• CASE의 기능
  • 그래픽 지원
  • 소프트웨어 생명주기 전 단계의 연결
  • 다양한 소프트웨어 개발 모형 지원
  • 표준화된 개발환경 구축 및 문서 자동화 기능

32. XP(eXtreme Programming)의 5가지 가치가 아닌 것은?

• XP(eXtreme Programming)
  • 소프트웨어 품질을 높이고, 개발 팀이 변화에 빠르게 대응할 수 있도록 하는 데 중점을 둔 방법론
  • 기술적인 실천과 지속적인 코드 개선 등 실용성에 중점을 둔 방법론
  • XP의 5가지 가치 : 용기, 단순성, 의사소통, 피드백, 존중

33. 다음 중 자료 사전에서 자료의 선택을 의미하는 것은?

34. 코드화 대상 항목의 무게, 면적 등 물리적 수치를 이용해 만든 코드는?

• 코드 설계: 데이터의 분류나 사물의 표현을 위해 코드를 설계하는 것
• 코드의 기능: 간소화, 표준화, 분류, 식별, 배열, 연상, 암호화, 오류 검출 등
• 코드 설계의 종류
  • 연상 코드 : 약호를 통해 코드만 보도고 대상을 연상할 수 있도록 만든 코드
  • 블록 코드 : 공통성이 있는 것끼리 블록으로 구분하고, 각 블록 내에서 일련 번호를 부여하는 코드
  • 순차 코드 : 기준에 따라 순서대로 일련번호를 부여하는 코드
  • 표의 숫자 코드 : 코드화 대상 항목의 무게, 면적 등 물리적 수치를 이용해 만든 코드

36. 미들웨어 솔루션의 유형에 포함되지 않는 것은?

• WAS : 웹 애플리케이션을 실행하기 위한 소프투웨어 환경을 제공
• TP Monitor : 트랜잭션이 올바르게 처리되고 있는지 데이터를 감시하고 제어하는 미들웨어
• RPC (Remote Procedure Call) : 응용 프로그램의 프로시저를 사용하여 원격 프로시저를 로컬 프로시저처럼 호출하는 방식의 미들웨어
• 메시지 지향 미들웨어(MOM : Message Oriented Middleware)
  • 느리고 안정적인 응답을 필요로 할 때 적합
• 객체 기반 미들웨어(ORB : Object Request Brokes)
  • CORBA 표준 스펙을 구현한 객체 지향 미들웨어

38. HIPO(Hierarchy Input Process Output)에 대한 설명으로 옳지 않은 것은?

• HIPO(Hierarchy Input Process Output)
  • 하향식 소프트웨어 개발을 위한 문서화 도구
  • 보기 쉽고 이해하기 쉬움
  • 기능과 자료의 의존 관계를 동시에 표현할 수 있음
  • 가시적 도표, 총체적 도표, 세부적 도표의 세 종류

40. 요구사항 명세서를 미리 배포하여 사전 검토한 후 짧은 검토 회의를 통해 오류를 조기에 검출하는 데 목적을 두는 방법은?

• 워크 스루 : 요구사항 명세서를 미리 배포하여 사전 검토한 후 짧은 검토 회의를 통해 오류를 조기에 검출하는 데 목적을 두는 방법
• 동료 검토 : 요구사항 명세서 작성자가 요구사항 명세서를 설명하고 이해관계자들이 설명을 들으면서 결함을 발견
• 인스펙션 : 소프트웨어 요구, 설계, 원시 코드 등의 저작자 외의 다른 전문가나 팀이 검사하여 오류를 찾아내는 검토 방법

41. 객체 지향 기법에서 클래스들 간의 공통된 특성을 추출하여 상위 클래스를 만드는 기법으로, ‘is-a’ 관계로 설명되는 관계성을 나타내는 기법은?

• 연관화 : 객체 간의 일반적인 관계 (is-member-of)
  • 학생 - 교수
• 분류화 : 객체를 공통된 특성에 따라 그룹화 (is-instance-of)
  • 동물을 포유류, 조류, 어류로 그룹화
• 집단화 : 전체와 부분의 관계로, 부분은 독립적으로 존재 가능(is-a-part-of)
  • 팀과 선수
• 일반화 : 여러 클래스의 공통된 특성을 추출하여 상위 클래스를 만드는 것(is-a)
  • 개와 고양이의 특성을 조합해 동물 클래스를 만듦.
• 특수화 : 상위 클래스를 기반으로 더 구체적이고 특수한 하위 클래스를 만드는 것 (is-a)
  • 동물 클래스를 특수화하여 개와 고양이 클래스를 만듦.

42. 소프트웨어 설계에서 자주 발생하는 문제에 대한 일반적이고 반복적인 해결 방법

• 디자인 패턴 : 소프트웨어 설계에서 자주 발생하는 문제에 대한 일반적이고 반복적인 해결 방법

50. 통신을 위한 프로그램을 생성해 포트를 할당하고, 클라이언트의 통신 요청 시 클라이언트와 연결하는 송수신 연계 기술

• Socket

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

입력

• 첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

• 첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

풀이

# [백준] 1781번 컵라면
import heapq
import sys

input = sys.stdin.readline

n = int(input())
# 정보를 담아놓을 리스트
array = []

for i in range(1,n+1):
    d,c = map(int,input().split())
    array.append((d,c))
array.sort()

q = []
for i in array:
    heapq.heappush(q,i[1])
    # 데드라인을 넘어선 문제는 빼낸다.
    if i[0] < len(q):
        heapq.heappop(q)
print(sum(q))

후기

처음에 문제를 풀 때는 어떤 알고리즘을 써야 해결할 수 있을까가 제일 고민이었는데, 이 알고리즘은 최소 힙 자료구조를 사용해야 풀 수 있는 문제였다. 항상 생각하지만 시간초과를 극복하는게 제일 어려운 거 같다. 아마 그 이유는 아직 시간 복잡도를 계산하는게 익숙하지 않아서 그런 거 같다. 추가로, 이 아이디어를 떠올리는게 참 어려웠다. 조금 더 연습해야지

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

5-4-1. 시스템 보안 설계

보안 공격 기법

• 컴퓨터 시스템, 네트쿼, 애플리케이션 등의 보안 취약점을 이용해 시스템에 접근한거나 손상을 입히는 방법

DoS(Denial of Service) 공격

• 서비스 거부 공격으로, 단일 공격자(시스템)가 특정 시스템이나 네트워크 서비스의 가용성을 방해하는 공격
• 주로 대량의 트래픽을 보내거나 시스템 자원을 고갈시켜 서비스를 마비시키는 방식으로 이루어짐.

DDoS(Distributed DOS)공격

• DOS의 다른 형태로 여러 대의 컴퓨터를 이용하여 특정 대상에 동시 다발적으로 서비스 거부를 유도하는 공격

Dos 관련 공격 기법

Smurfing

• DDos의 일종으로 IP 또는 ICMP 의 특성을 악용하여 특정 대상에 다수의 응답으로 보내어 그 시스템을 마비시키는 기법

Ping Flood

• 다량의 ICMP Echo Request 패킷을 보내어 대상 서비스를 마비시키는 기법

Ping of Death(PoD)

• 정상 크기보다 큰 ICMP 패킷을 작은 조각으로 쪼개어 공격 대상이 조각화된 패킷을 처리하게 만드는 공격 방법

SYN Flooding

• TCP 연결 설정 과정에서 대량의 SYN 패킷(연결 요청)을 보내 서비의 리소스를 고갈시켜 서비스 거부를 유도하는 DoS 공격

Land Attack

• 패킷 전송 시 출발지 IP 주소와 목적지 IP 주솟값을 똑같이 만들어서 공격 대상에 보내는 공격 방법

Tribe Flood Network

• 여러 공격자를 동원해 대규모 DDOS 공격을 수행하는 기법

보안 공격 기법

Key Logger Attack

• 컴퓨터의 사용자의 키보드 움직임을 탐지해 ID, 패스워드 등 개인의 중요한 정보를 몰래 빼가는 해킹 공격

Ransomware (Ransom 은 몸값이란 의미임.)

• 사용자의 파일을 암호화하고, 해동키를 제공하는 대가로 금전을 요구하는 악성 코드 공격

Exploit

• 소프트웨어나 시스템의 취약점을 이용하여 비인가된 액세스를 얻거나 악성 코드를 실행하는 공격

Worm

• 악성 코드의 유형 중 다른 컴퓨터의 취약점을 이용하여 스스로 또는 메일로 전파되며 스스로를 증식하는 것

Phishing

• 신뢰할 수 있는 기관이나 유명인을 가장하여 사용자의 로그인 정보나 개인 정보를 탈취하는 기법

보안 탐지 및 보호 기술

백도어 탐지

• 악성 소프트웨어나 해커가 시스템에 비밀스럽게 접근하기 위해 설치한 백도어를 식별하고 차단하는 과정
• 무결성 검사, 열린 포트 확인, 로그 분석, SetUID 파일 검사 등을 통해 백도어를 탐지

세션 하이재킹(Session Hijacking) 탐지

• 사용자의 세션을 도청하거나 탈취하는 세션 하이재킹 공격을 방지하고 식별하는 과정
• 비동기화 상태 탐지, ACK Storm 탐지, 패킷 이상 탐지, 세션 타임아웃 설정 등을 통해 세션 하이재킹을 탐지

스택 가드(Stack Guard)

• 메모리의 버퍼 크기를 초과하는 데이터를 입력하여 오류가 발생하는 Buffer Overflow를 방지하는 보호 기술
  • 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장하고, 이 값이 변경되면 오버플로우로 간주하여 프로그램을 중단

트립와이어(Tripwire) (덫이란 뜻)

• 백도어나, 설정 파일을 변경 등 시스템 변경을 감시 및 분석하는 도구

접근 통제

• 적절한 권한을 가진 인가자만 특정 시스템이나 정보에 접근할 수 있도록 통제하는 방법

벨-라파둘라 모델(Bell-Lapadula Model)

• 군대의 보안 레벨처럼 정보의 기밀성에 따라 상하 관계가 구분된 정보를 보호하기 위해 사용되는 모델
• 사용자는 자신보다 높은 수준의 데이터를 읽을 수 없는 ‘No Read Up’ 규칙
• 자신보다 낮은 보안 수준의 데이터에 쓸 수 없는 ‘No Write Down’ 규칙

사용자 인증 및 보안 기법

인증(Authentication)

• 자신의 신원을 시스템에 증명하는 과정
• 아이디와 패스워드를 입력하는 과정이 가장 일반적인 예시

SSO(Single Sign On)

• 시스템이 몇 대가 되어도 하나의 시스템에서 인증에 성공하면 다른 시스템에 대한 접근 권한도 얻는 시스템

네트워크 보안 솔루션

방화벽(Firewall)

• 네트워크 트래픽을 필터링하여 허용된 데이터만 통과시키고, 무단 접근으로부터 네트워크를 보호하는 보안 장치

가상 사설망(VPM, Virtual Private Network)

• 이용자가 인터넷과 같은 공중망에서 사설망을 구축하여 마치 전용망을 사용하는 효과를 가지는 보안 솔루션

Secure OS

• 컴퓨터 운영체제의 커널에 보안 기능을 추가한, 보안성이 강화된 운영체제
  • 운영체제의 보안상 결함으로 인하여 발생 가능한 각종 해킹으로부터 시스템을 보호하기 위하여 사용됨.
  • 보안 기능으로 식별 및 인증, 임의적 접근 통제(DAC),강제적 접근 통제(MAC), 감사 기능 등이 있음.

침입 탐지 시스템(IDS, Intrusion Detection System)

• 컴퓨터 시스템, 네트워크, 또는 애플리케이션에서 비정상적인 행동이나 침입을 탐지하고 경고하는 보안 장치

IDS의 유형

네트워크 기반 IDS (NIDS)

• 주로 네트워크 경계 (DMZ)에 배치되어 네트워크 패킷을 분석하고 침입을 탐지
• Snor등

호스트 기반 IDS(HIDS)

• 개별 호스트나 시스템에서 발생하는 이벤트를 모니터링하고 추적함.

IDS의 탐지 기법

사전 정의된 규칙 기반 탐지 (Misuse Detection, Signature-based Detection)

• 미리 정의된 공격 패턴을 기반으로 비정상적 활동을 탐지

이상 탐지 (Anomaly Detection)

• 정상적인 행동 패턴을 학습하고, 정상 패턴에서 벗어난 비정상적인 활동을 감지

로그 관리 및 보안 도구

wtmp

• 시스템에 로그인한 사용자, 로그아웃한 사용자 및 시스템 부팅과 같은 이벤트의 기록을 저장하는 파일

nmap(Network Mapper)

• 네트워크의 열린 포트 및 서비스 등을 스캔하여 보안 취약점을 탐지하는 오픈 소스 도구

TCP Wrapper

• 네트워크 서비스에 대한 접근을 제어하고 로깅하는 소프트웨어
• 특정 IP 주소에 대해 접근을 허가하거나 차단하는 기능을 제공하는 접근 제어 유틸리티

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

시작하면서

해당 글은 메타 코드 M에서 지원하는 정처기 필기 장학생에 합격하여 글을 작성하게 되었습니다.

메타 코드 해당 강의 보러 가기

참고 사항

• 플랫폼 => 이 뜻은 참고할 주제라는 뜻입니다.
• 이렇게 형관펜이 되어 있는 곳은 시험에 나오거나, 강조하고 싶은 부분이 있을 때 표시할 것입니다.

5-3-1. 소프트웨어 개발 보안 설계

정보보안

• 정보의 기밀성, 무결성, 가용성을 보호하여 무단 접근, 수정, 파괴로부터 데이터를 안전히 지키는 것.

정보보안의 3요소

기밀성

• 시스템 내의 정보와 자원은 인가된 사용자만 접근이 허용
• 정보가 전송 중에 노출되더라도 데이터를 읽을 수 없음.

무결성

• 시스템 내의 정보는 오직 인가된 사용자만 수정할 수 있는 보안 요소
• 전송 중인 정보는 수정되지 않음.

가용성

• 인가된 사용자는 가지고 있는 권한 범위 내에서 언제든 자원 접근이 가능

보안 취약점 유형

XSS(Cross Site Scripting)

• 악성 스크립트를 웹 페이지에 삽입하여 사용자의 브라우저에서 실행되도록 하는 보안 취약점
• 사용자의 쿠키를 탈취하거나 피싱공격을 할 수 있음.

SQL Injection

• 임의로 작성한 SQL 구문을 애플리케이션에 삽입하여 허가되지 않은 정보를 조회하거나 조작하는 공격 방식
• SQL Injection 취약점이 발생하는 곳은 주로 웹 애플리케이션과 데이터베이스가 연동되는 부분
• 데이터베이스에 따라 공격 기법이 다름.

Buffer Overflow Attack

• 메모리 버퍼의 한계를 넘는 데이터를 입력해 시스템을 장악하는 공격
• 시스템을 비 정상적으로 종료시킬 수 있음.

암호 알고리즘

• 데이터를 안전하게 암호화하고 복호화하여 무단 접근을 방지하는 기법

암호 관련 용어

• 평문 : 암호화되기 전 원본 메시지
• 암호문 : 암호화가 적용된 메시지
• 암호화 : 평문 → 암호문
• 복호화 :암호문 → 평문
• 키 : 적절한 암호화를 위해 사용되는 값

암호 알고리즘의 종류

대칭 키 암호화(Symmetric Key Encryption)

• 암호화와 복호화에 동일한 키를 사용하는 알고리즘
• 빠르지만 키를 안전하게 공유하는 것이 중요

비대칭 키 암호화 (Asymmetric Key Encryption)

• 암호화와 복호화에 서로 다른 키를 사용하는 암호화 방식
• 하나의 키(공개 키)는 암호화에, 다른 하나의 키(개인 키)는 복호화에 사용됨.
• 키 관리가 쉽지만, 대칭 키 방식보다 속도가 느림.

해시 함수(Hash Functions)

• 입력 데이터를 고정된 길이의 고유한 해시 값으로 변환하는 함수
• 주로 데이터 무결성 확인에 사용

대칭 키 암호화(Symmetric Key Encryption, 비밀 키 암호화)

• 암호화와 복호화에 동일한 비밀 키를 사용하는 방식

대칭 키 암호화의 특징

• 비대칭 키 암호화보다 속도가 빠르기 때문에 다양한 암호의 핵심 함수로 사용될 수 있음.
• 같은 키를 공유하기 때문에 비밀키 전달을 위한 키 교환을 안전하게 진행하는 것이 중요
• 키 개수는 n(n-1)/2개

대칭 키 암호화 방식

블록 암호 방식

• 데이터를 고정된 크기(블록)으로 나누어 암호화
• DES(64bit), IDEA(64bit), AES(128bit), SEED(128bit)

스트림 암호 방식

• 비트 /바이트/ 단어들을 순차적으로 암호화
• RC4

비대칭 키 암호화 (Asymmetric Key Encryption, 공개 키 암호화 방식)

• 암호화와 복호화에 서로 다른 키(공개키, 개인 키)를 사용하는 방식

비대칭 키 암호화의 특징

• 공개 키로 암호화된 메시지는 비공개된 개인 키로만 복호화 가능
  • 키 분배가 용이하고 관리할 키 개수가 적음(2n개)
• 비대칭 암호 알고리즘은 자신만이 보관하는 비밀 키를 이용하여 인증, 전자서명 등에 적용이 가능
• 대칭 키 암호화에 비해 연산 속도가 느림. → (그래서 비대칭 키와 대칭키를 동시에 사용하는 경우도 있음.)

비대칭 키 암호화의 예시

• RSA(소인수 분해 문제 기반), 디피-헬만(Diffie-Hellman)

해시 함수

• 입력 데이터를 고정된 길이의 고유한 해시 값으로 변환

해시 암호화 방식의 특징

• 임의 길이의 데이터를 입력받아 고정된 길이의 해시값으로 변환
• 해시 함수는 일방향 함수
• 레인보우 테이블 공격에 취약 → Salt Key 추가(Salt key: 임의의 문자), 이를 추가함으로써 다른 해시값을 만듦으로써, 레인보우 테이블에 대비할 수 있음.
  • 레인보우 테이블 : 다양한 비밀번호와 그에 대응하는 해시 값을 미리 계산해 저장한, 해시 암호를 빠르게 역산하기 위한 테이블

해시 암호화 방식의 예시

• MD4, MD5, SHA-1, HAVAL

메타코드 M 해당 강의 보러가기 (환급형 강의)

메타코드 M 해당 강의 보러가기 (일반형 강의)

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력

• 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. T는 10,000보다 작거나 같은 자연수 또는 0이다.

  • 두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

출력

• TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

풀이

# [백준] 1865번 웜홀 실패 코드(이유: 시간 복잡도가 너무 큼)
import sys
input = sys.stdin.readline

tc = int(input())

INF= int(1e9)

def solve():
    for node in range(n):
        for cur,next_node,cost in line:
            if graph[next_node] > graph[cur] + cost:
                graph[next_node] = graph[cur] + cost
                if node == n-1:
                    return True
    return False 
result =[]

for _ in range(tc):
    n,m,w = map(int,input().split())
    line = []
    graph =[INF] *(n+1)
    for _ in range(m):
        s,e,t = map(int,input().split())
        line.append((s,e,t))
        line.append((e,s,t))
    for _ in range(w):
        s,e,t = map(int,input().split())
        line.append((s,e,-t))

    go = solve(1)
    result.append(go)

for i in result:
    print("YES" if i else "NO")

해당 문제의 핵심은 굳이 출발 노드를 설정하지 않아도 된다는 점이다. 오히려 출발 노드를 설정함으로써, 오히려 알고리즘을 실행하지 못하는 경우의 수가 등장할 수 있다. 이 점을 주의하면 금방 풀린다. (내가 그거 때문에 여러 번 틀렸다. 슬프다.)

오답 풀이

# [백준] 1865번 웜홀 실패 코드(이유: 시간 복잡도가 너무 큼)
import sys
input = sys.stdin.readline

tc = int(input())

INF= int(1e9)

def solve(start):
    graph[start] = 0
    for node in range(n):
        for cur,next_node,cost in line:
            if graph[cur] != INF and graph[next_node] > graph[cur] + cost:
                graph[next_node] = graph[cur] + cost
                if node == n-1:
                    return True
    return False 
result =[]

for _ in range(tc):
    n,m,w = map(int,input().split())
    line = []
    graph =[INF] *(n+1)
    for _ in range(m):
        s,e,t = map(int,input().split())
        line.append((s,e,t))
        line.append((e,s,t))
    for _ in range(w):
        s,e,t = map(int,input().split())
        line.append((s,e,-t))

    go = solve(1)
    result.append(go)

for i in result:
    print("YES" if i else "NO")

if graph[cur] != INF and graph[next_node] > graph[cur] + cost: 해당 코드가 문제가 되었다.

후기

• 으어 이건 좀 어렵게 풀었다. 그래도 벨만 포드 알고리즘을 알게 되어서 좋다.