데이터베이스와 대화하기 위한 언어.

SQL의 기본 구조

SELECT: 어떤 정보를 가져올 것인가 FROM: 어디(테이블)에서 가져올 것인가 WHERE: 어떤 조건에 맞는 데이터만 가져올 것인가

문제

요구하는 조건 4가지

1. 필터링: 자동차 종류가 SUV인 데이터만 골라낸다.
2. 계산: 그 자동차들의 평균 일일 대여 요금
3. 반올림: 평균값을 소수 첫번째 자리에서 반올림 (int만들기)
4. 이름짓기: 결과 컬럼의 이름을 AVERAGE_FEE로 표시

SELECT ROUND(AVG(DAILY_FEE),0) AS AVERAGE_FEE
FROM CAR_RENTAL_COMPANY_CAR
WHERE CAR_TYPE = 'SUV'

재구매는 같은 회원이 같은 상품을 2번 이상 구매

1. USER_ID, PRODUCT_ID 묶어서 살펴보기 (그룹화)
2. 묶음 안에 데이터가 2개 이상 들어있는지 확인 (조건 설정)

SQL 문법 ① GROUP BY (그룹화) 데이터를 특정 컬럼 기준으로 그룹으로 묶음

• GROUP BY USER_ID, PRODUCT_ID라고 쓰면, "A라는 사람이 B라는 물건을 산 내역"을 하나의 덩어리로 뭉쳐줍니다. ② HAVING (그룹 필터링) WHERE는 전체 데이터에서 행을 골라낼 때 쓰지만, HAVING은 GROUP BY로 묶인 그룹 중에서 조건을 만족하는 그룹만 골라낼 때 사용합니다.
• HAVING COUNT(*) > 1 : 이 묶음 안에 데이터가 1개보다 많은(즉, 2개 이상인) 그룹만 남김

단계별 쿼리 작성 1단계: 어떤 컬럼을 보여줄까? (SELECT) 재구매한 회원 ID와 상품 ID를 출력

2단계: 어떤 기준으로 묶을까? (GROUP BY) 동일한 회원이 동일한 상품을 산 내역을 찾아야 하므로 두 컬럼을 함께 묶기

3단계: 재구매(2건 이상)인 데이터만 남기기 (HAVING) 묶인 그룹들 중에서 데이터 개수가 1개 초과인 것만 필터링

4단계: 정렬하기 (ORDER BY) 문제 조건: 회원 ID 기준 오름차순(ASC), 같다면 상품 ID 기준 내림차순(DESC).

전체 코드

from collections import deque

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

bfs()
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)

전체 로직은 익은 토마토(1)에서 BFS를 시작해, 인접한 익지 않은 토마토(0)를 하루씩 지나가며 익히는 방식 !!

📦 코드 전체 설명

from collections import deque

• deque: BFS를 위한 큐 자료구조.
  → 일반 list보다 pop(0) 대신 popleft()로 더 빠르게 동작. pop(0)을 하면 시간 복잡도가 증가해서 popleft()를 써야함

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

• 입력값 M, N을 받아 각각 가로 세로 칸수로 저장.

matrix = [list(map(int, input().split())) for _ in range(n)]

• 창고의 토마토 상태를 2차원 리스트로 입력.
• matrix[i][j]:
  • 1: 익은 토마토
  • 0: 익지 않은 토마토
  • -1: 토마토가 없는 빈칸

queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

• queue: 익은 토마토의 위치를 담을 큐
• dx, dy: 상, 하, 좌, 우 방향 이동용 배열

res = 0

• 마지막 결과(걸린 날짜)를 저장할 변수

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

• 처음부터 익어 있는 토마토들의 위치를 queue에 저장
• 이들을 BFS의 시작점으로 삼음 → 동시에 퍼짐 (다중 BFS 시작)

🔁 BFS 함수 정의

def bfs():
    while queue:
        x, y = queue.popleft()

• queue가 빌 때까지 반복 (더 이상 익힐 수 없을 때까지)

        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y

• 상, 하, 좌, 우 방향으로 이동한 위치 계산

            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:

• 범위 체크 (0 <= nx < n, 0 <= ny < m)
• 아직 익지 않은 토마토(0)만 탐색 대상으로 삼음

                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

• 현재 토마토의 값(= 날짜) + 1 → 익은 날짜로 기록
• 새로 익은 토마토도 큐에 추가 → 다시 주변을 익히기 가능

🔍 BFS 수행 후 결과 확인

bfs()

• 위에서 정의한 BFS 실행

for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)

• BFS 이후에도 0이 남아 있으면 → 못 익은 토마토가 존재하는거
• 이런 경우엔 절대 모두 익을 수 없음 → -1 출력

    res = max(res, max(i))

• 현재 행에서 가장 큰 값(=가장 늦게 익은 토마토 날짜)을 res에 저장

print(res - 1)

• 처음 익은 토마토는 1로 시작했기 때문에, 실제 걸린 날짜는 -1해서 출력

✅ 예시 입력

6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1

출력

4

모든 토마토가 익는 데까지 총 4일 걸립니다.

💡 핵심

성능 요약

메모리: 108632 KB, 시간: 1260 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 3월 27일 13:55:51

문제 설명

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

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

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

출력

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

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
anslist = [0]*n
anslist[0] = 1

if n>=2:
  anslist[1] = 2
  for i in range(2,n):
    anslist[i] = anslist[i-1] + anslist[i-2]
print(anslist[n-1]%10007)

dp 배열만들기 anslist = [0]*n

초기값 설정 anslist[0] = 1 anslist[i]는 2×(i+1) 직사각형을 채우는 방법의 수를 저장한다. n=1일 때는 한 가지 방법밖에 없다. (2×1 타일 하나) if n >= 2: anslist[1] = 2 n=2일 때는 두 가지 방법(가로 1×2 두 개, 세로 2×1 두 개)이 있다.

for i in range(2, n): anslist[i] = anslist[i-1] + anslist[i-2] 2×n 직사각형을 채우는 방법은 2×(n-1) + 2×(n-2)의 조합이다.

분류

다이나믹 프로그래밍

제출 일자

2025년 3월 25일 12:34:23

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

NxN 격자를 순회하면서 만약 아직 방문하지 않은 집을 발견하면, 그 주변(상하좌우)으로 이어진 모든 1을 하나의 덩어리(단지)로 묶어 표시한다. BFS나 DFS를 통해 연결된 집들을 전부 방문 처리(0 또는 방문체크)한 뒤, 그 개수를 세어 반환한다. 찾은 단지가 여러 개 나오면, 각각의 집 개수를 기록하고, 정렬하여 출력한다.

[Silver I] 단지번호붙이기 - 2667

문제 링크

나의 풀이

from collections import deque

N = int(input())

graph = [list(map(int, input())) for _ in range(N)]

def bfs(graph,x,y):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0  
    cnt = 1
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny <0 or ny >= N:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
                cnt += 1
    return cnt

count = [bfs(graph, i, j) for i in range(N) for j in range(N) if graph[i][j] == 1]

count.sort()
print(len(count))

for i in range(len(count)):
    print(count[i])

input()이 '11100'이면 공백이 없어서 '11100' 한 덩어리로 보기때문에 문자를 하나씩 int로 변환해야한다. input().strip()은 '11100'다. list('11100')은 ['1','1','1','0','0']이 되고 이걸 map(int,['1','1','1','0','0'])라고 해야 ['1','1','1','0','0']형태가 돼서 2차원 배열이 된다! N → 지도의 크기, graph → NxN 2차원 리스트(각 원소 0/1)

반복문에서 만약 graph[i][j] == 1은 새 단지 시작 -> bfs() 호출하여 연결된 모든 집 방문 & 개수 반환 -> 개수를 counts 리스트에 저장

len(counts) → 전체 단지 수를 정렬 후 출력한다. 이 로직에서 중요한 점은 그래프의 어떤 원소를 방문하면 인접한 1을 모두 탐색하고 그 탐색 범위를 0으로 바꿔서 중복 탐색을 막는다는 것이다.

성능 요약

메모리: 34952 KB, 시간: 60 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 27일 13:52:58

문제 설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

import sys
input = sys.stdin.readline
n = int(input())
for i in range(n):
    clo = {}
    num = int(input().strip())
    for _ in range(num):
        name, type = input().strip().split()
        if type in clo:
            clo[type].append(name)
        else:
            clo[type] = [name]

    cnt = 1

    for x in clo:
        cnt *= (len(clo[x]) + 1)

    print(cnt-1)

알몸이 아닌 경우의 수 구하기 각각을 안 입는 경우까지 고려하면 (A+1), (B+1), (C+1) 이를 전부 곱하면 (A+1) * (B+1) * (C+1)가지가 됨. 하지만 이 중 알몸은 1가지라서 1을 빼준다. (A+1) * (B+1) * (C+1) - 1.

[Silver III] 패션왕 신해빈 - 9375

문제 링크

성능 요약

메모리: 32412 KB, 시간: 32 ms

분류

조합론, 자료 구조, 해시를 사용한 집합과 맵, 수학

제출 일자

2025년 2월 26일 15:49:46

문제 설명

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

[level 2] 조이스틱 - 42860

나의 풀이

def solution(name):
    answer = 0
    alp = 0
    cur = len(name) -1
    for i, j in enumerate(name):
        alp += min(ord(j)-ord('A'), ord('Z')-ord(j)+1)
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1
        cur = min([cur,2*i+len(name)-next,i+2*(len(name)-next)])
    return alp+cur

min(ord(j)-ord('A'), ord('Z')-ord(j)+1) 앞으로(▲): ex) 'A' → 'C'라면 2번 누르고 뒤로(▼): ex) 'A' → 'Z'라면 1번 누름 cur변수(커서 이동 횟수)를 alp변수(알파벳 변경 수)에 누적시킨다.

cur=len(name) - 1은 현재까지 찾은 최소 이동 비용이다. next는 각 인덱스 i에서 연속된 A들을 건너뛰는 시점이다.

문제 링크

성능 요약

메모리: 10.3 MB, 시간: 0.05 ms

구분

코딩테스트 연습 > 탐욕법（Greedy）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 02월 26일 13:32:29

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

출처

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2022년 1월 14일 지문 수정 및 테스트케이스가 추가되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 링크

나의 풀이

def solution(n, lost, reserve):
    reserved = set(reserve) - set(lost)
    losted = set(lost) - set(reserve)

    for r in reserved:
        if r-1 in losted:
            losted.remove(r-1)
        elif r+1 in losted:
            losted.remove(r+1)

    return n - len(losted)

문제 개념과 접근 (Greedy)

“현재 시점에서 줄 수 있는 학생이 있다면 최우선으로 빌려주는” 방식으로 진행. 단, 중복으로 빌려줄 수 없게 하는 조건을 잘 처리해야 함. 이미 도난당했으나 여벌을 갖고 있는 학생은 사실상 lost에서 제외(혹은 reserve에서 제외)해야 함(즉, 본인 체육복만 사용).

코드 아이디어

reserved와 losted 집합 분리 reserved: 원래 reserve에 있었지만, lost에도 포함된 경우(즉, 도난당한 학생 중 일부가 여벌이 있었던 경우)는 이미 본인 체육복을 잃어버려서 여벌이 1벌뿐이다. 결국 “남에게 빌려줄 수 있는 상황”이 아니게 되므로, 이들을 제외하기 위해 set(reserve) - set(lost)를 사용. losted: 원래 lost에 있었지만, reserve에도 있던 학생은 이미 자기 체육복은 보전되었으므로 최종적으로 잃은 상태가 아님. 그러므로 set(lost) - set(reserve)를 통해 “실제로 여벌 없이 잃은 학생”만 남김.

빌려주기(Greedy) for r in reserved를 돌면서, 여벌이 있는 학생 r이 다음을 확인: r-1 in losted: 내 앞번호 학생이 체육복이 없는가? 있다면 그 학생에게 빌려주고, losted 집합에서 제거 r+1 in losted: 뒷번호 학생이 체육복이 없는가? 있다면 빌려주고 제거 한 번 빌려주면 더 이상 그 학생에게 빌려줄 수 없으므로 if-elif 구문으로 처리 (한 명에게만 빌려주면 종료).

최종 인원 최종적으로 losted에 남아 있는 학생들은 체육복을 못 구한 상태. 전체 인원(n) - 체육복 못 구한 인원(len(losted))

성능 요약

메모리: 10.2 MB, 시간: 0.01 ms

구분

코딩테스트 연습 > 탐욕법（Greedy）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 02월 25일 15:02:01

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

문제가 잘 안풀린다면😢

힌트가 필요한가요? [코딩테스트 연습 힌트 모음집]으로 오세요! → 클릭

※ 공지 - 2019년 2월 18일 지문이 리뉴얼되었습니다.
※ 공지 - 2019년 2월 27일, 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2021년 7월 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2021년 8월 30일 테스트케이스가 추가되었습니다.
※ 공지 - 2022년 11월 30일 테스트케이스가 추가되었습니다.
※ 공지 - 2023년 6월 12일 테스트케이스가 추가되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

Sequenece containers

array: Array class vector: Vector deque: Double ended queue forward_list: Forward list list: List

Container adaptors

stack: LIFO stack queue: FIFO stack priority_queue: Priority queue

Associative containers

set: Set multiset: Multiple-key set map: Map multimap: Multiple-key map

Unordered associative containers

unordered_set: Unordered Set unordered_multiset: Unordered Multiset unordered_map: Unordered Map unordered_multimap: Unordered Multimap

Iterator

포인터와 비슷한 개념으로 컨테이너의 원소를 가리킨다. 가리킨 원소에 접근해서 다음 원소를 가리키는 기능을 수행한다. Traversal(순회)이 가능하게 한다.

Algorithm

정렬, 삭제, 검색, 연산을 실행하는 일반화(generic)된 함수 템플릿

Function Object

함수처럼 동작하는 객체로 operator() 연산자를 오버로딩 한 객체를 의미한다.

Container Adaptor

객체의 인터페이스를 수정해서 새로운 인터페이스를 제공하는 요소로 변경.

Container Adaptor = { stack, queue, priority_queue } 어떤 경우엔 일반적인 container로 분류하기도 함.

Allocator

컨테이너의 메모리 할당을 담당하는 객체 모든 컨테이너는 각 객체별 전용 할당기를 가지고 있음.

Template와 Generic programming

한 함수를 “어떤 타입 T”에 대해서도 동작하도록 일반화 예: getmax(x, y), getmax(d1, d2), getmax(s1, s2) 사용자가 정의한 타입(복소수, 행렬 등)에 대해서도 연산자 오버로드를 통해 활용 가능. Class Template vs Function Template Class Template: template <typename T1, typename T2>로 pair, vector 등 Function Template: template T getmax(T x, T y) {...}

나의 풀이

dp로 푸는 문제다. 그러나 나는 왜인지 모르게 재귀함수를 써서 풀고싶었다. 그래서 틀렸다.. 다시 dp로 풀어보도록 하자.

import sys
input = sys.stdin.readline
t = int(input())
cases = [int(input()) for _ in range(t)]

dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4,11):
    dp[i] = dp[i-1] + dp [i-2] + dp[i-3]

for i in cases:
    print(dp[i])

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 24일 17:51:24

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

import sys
input = sys.stdin.readline
n = int(input())
fin = []
for i in range(n):
    b, p, q, r = map(int, input().split())
    score = p*q*r
    rank = p+q+r
    fin.append([b, score, rank])
fin.sort(key=lambda x: (x[1], x[2], x[0]))

for i in range(3):
    print(fin[i][0], end=' ')

lambda 매개변수 : 표현식 으로 람다 표현식을 이용해서 점수, 순위합, 등번호 낮은 순으로 정렬해주는 것을 떠올리면 풀 수 있다!

x[1]: 점수가 낮은 순으로 정렬. x[2]: 점수가 같으면 순위 합이 낮은 순으로 정렬. x[0]: 점수와 순위 합이 같으면 등번호가 낮은 순으로 정렬.

문제 설명

스포츠 클라이밍은 1986년에 시작된 실내 암벽 등반 스포츠입니다. 선수들은 원래 리드 클라이밍 종목에서만 겨루었는데, 1989년에 스피드 클라이밍이 추가되었고, 10년 후인 1999년에 볼더링 종목이 추가되었습니다. 올림픽 게임에서는 금, 은, 동메달을 결정하기 위해 선수들은 세 종목에서 겨루어 종합 순위를 매깁니다. 종합 순위는 세 종목에서 거둔 순위를 곱한 점수로 결정됩니다. 예를 들어, 어떤 선수가 리드에서 1위, 스피드에서 5위, 볼더링에서 2위를 했다면 점수는 10점이 됩니다. 점수가 낮을수록 순위가 높습니다.

선수 n명의 등번호와 이들이 세 종목에서 거둔 순위가 주어질 때, 금, 은, 동메달을 받을 선수를 결정하는 프로그램을 작성하세요.
만약 두 선수의 점수가 같다면, 세 종목 순위의 합산 점수가 낮은 선수가 더 높은 순위를 차지합니다.
만약 점수와 순위의 합산 점수가 모두 같다면, 등번호가 낮은 선수가 더 높은 순위를 차지합니다.

입력

• 첫 줄에 선수의 명수 n (3 ≤ n ≤ 100)이 주어집니다.
• 이후 n개의 줄 각각에 네 정수 b, p, q, r가 주어집니다.
  • b: 선수의 등번호 (1 ≤ b ≤ 999, 서로 다름)
  • p, q, r: 해당 선수가 리드, 스피드, 볼더링에서 거둔 순위 (1 ≤ p, q, r ≤ n)

출력

금, 은, 동메달을 받을 선수의 등번호를 순서대로 한 줄에 출력하세요.

예제 입력 1

5
101 1 2 3
102 2 2 2
103 1 1 4
104 1 3 3
105 2 1 3

예제 출력 1

103 101 105

풀이

입력 처리 및 점수 계산

import sys
input = sys.stdin.readline

n = int(input())
players = []

for _ in range(n):
    b, p, q, r = map(int, input().split())
    score = p * q * r
    sum_rank = p + q + r
    players.append((b, score, sum_rank))

• 선수들의 등번호 b, 각 종목 순위 p, q, r를 입력받아 점수(score)와 순위의 합산(sum_rank)을 계산합니다.

정렬 조건

players.sort(key=lambda x: (x[1], x[2], x[0]))

1. 점수(x[1])가 낮은 순서대로 정렬.
2. 점수가 같으면, 순위 합산(x[2])이 낮은 순서대로 정렬.
3. 점수와 순위 합산이 같으면, 등번호(x[0])가 낮은 순서대로 정렬.

출력

for i in range(3):
    print(players[i][0], end=' ')

• 정렬된 결과에서 상위 3명의 등번호를 출력합니다.

예제 실행 결과

입력

5
101 1 2 3
102 2 2 2
103 1 1 4
104 1 3 3
105 2 1 3

출력

103 101 105

문제 링크

문제 풀이

import sys
input = sys.stdin.readline
a = input().strip()
lth = len(a)
ha, hb = a[:lth//2], a[lth//2:]
dt = {'A':0, 'B':1, 'C':2, 'D':3, 'E':4, 'F':5, 'G':6, 'H':7, 'I':8, 'J':9, 'K':10, 'L':11, 'M':12, 'N':13, 'O':14, 'P':15, 'Q':16, 'R':17, 'S':18, 'T':19, 'U':20, 'V':21, 'W':22, 'X':23, 'Y':24, 'Z':25}
ra=0
rb=0
ra = sum(dt[ch] for ch in ha)
rb = sum(dt[ch] for ch in hb)

def rotate(string, rotation_value):
    rotated = ''
    for ch in string:
        rotated += chr((((ord(ch)-ord('A'))+rotation_value)%26)+ord('A'))
    return rotated
ha_rotated = rotate(ha, ra)
hb_rotated = rotate(hb, rb)
result = ''
for i in range(len(ha_rotated)):
    merged_ch = chr((((ord(ha_rotated[i])-ord('A'))+(ord(hb_rotated[i])-ord('A')))%26)+ord('A'))
    result += merged_ch
print(result)

(1) 입력 처리 및 분할 input().strip()으로 개행 문자 제거. 문자열을 반으로 정확히 나눔. (2) 회전 값 계산 각 문자열의 문자 값의 합계를 계산하여 회전 값을 구함. (3) 문자열 회전 각 문자열을 회전 값만큼 회전: 알파벳 문자 범위를 벗어나지 않도록 모듈러 연산(% 26)을 사용. (4) 문자열 병합 두 문자열을 병합하며 최종 결과 생성: 각 문자에서 두 번째 문자열의 해당 문자 값만큼 추가 회전. (5) 출력 최종 복호화된 결과를 출력.

성능 요약

메모리: 32412 KB, 시간: 40 ms

분류

구현, 문자열

제출 일자

2025년 1월 19일 12:10:50

문제 설명

DRM Encryption is a new kind of encryption. Given an encrypted string (which we’ll call a DRM message), the decryption process involves three steps: Divide, Rotate and Merge. This process is described in the following example with the DRM message “EWPGAJRB”:

• Divide – First, divide the message in half to “EWPG” and “AJRB”.
• Rotate – For each half, calculate its rotation value by summing up the values of each character (A = 0, B = 1, . . . Z = 25). The rotation value of “EWPG” is 4 + 22 + 15 + 6 = 47. Rotate each character in “EWPG” 47 positions forward (wrapping from Z to A when necessary) to obtain the new string “ZRKB”. Following the same process on “AJRB” results in “BKSC”.
• Merge – The last step is to combine these new strings (“ZRKB” and “BKSC”) by rotating each character in the first string by the value of the corresponding character in the second string. For the first position, rotating ‘Z’ by ‘B’ means moving it forward 1 character, which wraps it around to ‘A’. Continuing this process for every character results in the final decrypted message, “ABCD”.

입력

The input contains a single DRM message to be decrypted. All characters in the string are uppercase letters and the string’s length is even and ≤ 15 000.

출력

Display the decrypted DRM message.

문제 링크

나의 풀이

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(a,b):
    queue = deque()
    queue.append([a,b])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx>= n or ny >= m or nx<0 or ny<0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append([nx,ny])
    return graph[n-1][m-1]
print(bfs(0,0))

성능 요약

메모리: 34936 KB, 시간: 68 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 18일 20:09:06

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

문제 링크

성능 요약

메모리: 40508 KB, 시간: 136 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2025년 1월 17일 22:46:48

나의 풀이

import sys
from collections import deque
input = sys.stdin.readline
n, m, v = map(int,input().split())
graph = [[False]*(n+1)for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] *(n+1)
visited2 = visited1.copy()

def bfs(v):
    queue = deque([v])
    visited2[v] = True
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i]:
                queue.append(i)
                visited2[i] = True

def dfs(v):
    visited1[v] = True
    print(v, end=" ")
    for i in range(1, n+1):
        if not visited1[i] and graph[v][i]:
            dfs(i)

dfs(v)
print()
bfs(v)

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

1. 아래에서 위로 올라가기

   def solution(triangle):
    floor = len(triangle) - 1

   floor은 삼각형의 마지막 층이다. (index)

    while floor > 0:
        for i in range(floor):
            triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
        floor -= 1 

   바닥에서 위층으로 올라간다. (N층부터 1층까지) 각 층의 모든 숫자를 탐색한다. 현재 칸에 아래칸의 두 숫자 중 큰 값을 더한다. 위층으로 이동한다.

    return triangle[0][0] 

2. 위에서 아래로 내려오기

   def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])): 
            if j == 0:
                triangle[i][j] += triangle[i-1][0]  # 위층의 첫 번째 값만 더하기
            elif j == len(triangle[i]) - 1:  # 오른쪽 끝인 경우
                triangle[i][j] += triangle[i-1][-1]  # 위층의 마지막 값만 더하기
            else:  # 그 외의 경우
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])  # 위층의 두 값 중 큰 값 더하기
   
    return max(triangle[-1])

   두 번째 층부터 시작한다. 현재 층의 모든 숫자를 탐색한다. 왼쪽 끝인 경우는 j == 0이고 이 때는 위 층의 첫번째 값만 더한다. 오른쪽 끝인 경우는 j == len(triangle[i]) - 1이고 위층의 마지막 값만 더한다. 둘 다 아닐 경우에는 위층의 두 값 중 큰 값을 더한다.

문제 링크

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

def solution(N, number):
    dp = [[] for _ in range(9)]

dp리스트는 dp을 위한 리스트다. dp[i]는 숫자 N을 i번 사용해서 만들 수 있는 모든 수의 []를 저장한다.dp 길이는 9로 설정되어 있는데 N을 8번까지 사용할 수 있기 때문에 9로 설정한다.

    for i in range(1, 9):

숫자 N을 i번 사용했을 때의 경우를 계산한다. i는 1부터 8까지 반복되며, 최소 사용 횟수를 찾는다.

        comb_list = set()

comb_list는 중복을 제거하기 위해 사용되는 집합이다. 현재 i번 사용해서 만들 수 있는 모든 가능한 결과를 저장한다.

        comb_list.add(int(str(N) * i))

숫자 N을 i번 반복하여 만든 숫자를 comb_list에 추가한다.

        for j in range(1, i):

j는 현재 i를 나눠서 두 부분으로 쪼개는 역할을 한다. i번 사용한 경우를 두 부분으로 나누어 j번 사용한 경우와 i-j번 사용한 경우를 조합한다.

점화식을 세워보자 dp[i]의 원소 = dp[ i - j ]의 원소 (사칙연산) dp[j] 문제의 kick은 무엇을 기준으로 dp를 쓸지 정하는 것이다. N으로 할지 number로할지 range(N)으로 할지 잘 파악해야 한다. 보통 제한 범위가 짧은 것을 하는게 좋다.

            for comb1 in dp[i - j]:
                for comb2 in dp[j]:

dp[i - j]에는 i-j번 사용하여 만들 수 있는 숫자들이 저장되어 있다. dp[j]에는 J번 사용해서 만들 수 있는 문자들이 저장되어 있다. 두 경우를 조합해서 가능한 숫자를 계산하는 것이다.

                    plus = comb1 + comb2
                    minus = comb1 - comb2
                    mul = comb1 * comb2
                    if comb2 != 0:
                        div = comb1 / comb2
                        if div & 2 == 0:
                            comb_list.add(int(div))

comb1과 comb2를 더하기, 빼기, 곱하기 연산으로 새로운 숫자를 만든다. 나누기는 comb2가 0이 아닐 때만 계산하고 문제 조건에서 정수 나누기 결과만 사용하므로 int()로 변환한다.

                    comb_list.add(plus)
                    comb_list.add(mul)
                    if minus >= 0:
                        comb_list.add(minus)

plus, mul은 항상 결과를 추가한다. 빼기는 음수가 되면 안되므로 minus >=0 일 때만 추가한다.

        if number in comb_list:
            return i

현재 comb_list에 목표 숫자 number가 포함되어 있다면 헌재 i가 최소 사용 횟수이다. 따라서 i를 반환한다.

        for q in comb_list:
            dp[i].append(q)

현재 comb_list에 있는 숫자들을 dp[i]에 저장한다. 저장한건 다음 i+1 단계에서 사용할 수 있다.

    return -1

8번까지 숫자 N을 사용해도 number를 만들 수 없다면 -1를 반환한다.

성능 요약

메모리: 10.5 MB, 시간: 14.59 ms

구분

코딩테스트 연습 > 동적계획법（Dynamic Programming）

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 01월 16일 16:44:13

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

문제 링크

나의 풀이

import sys
input = sys.stdin.readline
case = int(input())
for i in range(case):
    n, m = map(int, input().split())
    king = list(map(int, input().split()))

    num = 1
    while case:
        if king[0] < max(king):
            king.append(king.pop(0))
        else:
            if m == 0:
                break

            king.pop(0)
            num += 1

        m = m-1 if m>0 else len(king)-1

    print(num)

맨 앞 문서가 리스트에서 제일 큰 수가 아니라면 제일 뒤로 이동한다. 이 과정을 반복하면 제일 큰 수가 제일 앞에 오게되고 그 때의 num을 출력하면 된다.

성능 요약

메모리: 32412 KB, 시간: 40 ms

분류

자료 구조, 구현, 큐, 시뮬레이션

제출 일자

2025년 1월 13일 14:32:16

문제 설명

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

문제 링크

나의 풀이

import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * 1000001
for i in range(2, n+1):
    dp[i] = dp[i-1] +1
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
print(dp[n])

1로 만들기 위한 최소 연산 횟수를 계산하는 다이나믹 프로그래밍(DP) 방식이다. dp[i]는 정수 𝑖를 1로 만들기 위한 최소 연산 횟수를 저장하는 배열이다. 초기화 dp[1] = 0 (이미 1이므로 연산이 필요 없음), dp[2], dp[3]부터 계산 점화식 각 정수𝑖에 대해 최소 연산 횟수는 3가지 연산 중 최솟값을 선택한 결과다. dp[i-1] + 1: 1을 빼는 연산 dp[i//2] + 1: 2로 나누어 떨어지면 2로 나누는 연산 dp[i//3] + 1: 3으로 나누어 떨어지면 3으로 나누는 연산

성능 요약

메모리: 40224 KB, 시간: 484 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 12일 18:23:38

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 10⁶보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

문제 링크

나의 풀이

import sys
input = sys.stdin.readline
n = int(input())
ch = 666
cnt = 0
while cnt < n:
    if '666' in str(ch):
        cnt += 1
    ch +=1
print(ch-1)

666이 포함된 수 중에 n번째를 찾아야한다. 처음에는 쉽노 ㅋ 하면서 앞에 print(f"{a}666") 했는데 생각해보니까 그게 아니다.. 666, 1666,2666,...,6660,6661,6666,7666 n에 666에 포함되어있으면 cnt를 1 증가시켜야한다. cnt == n이 되면 종료하고 현재 ch를 출력하면 된다. n번째 종말의 수를 찾고 나서 1 증가했으므로, 최종적으로 1을 뺀 ch-1을 출력한다.

성능 요약

메모리: 32412 KB, 시간: 676 ms

분류

브루트포스 알고리즘

제출 일자

2025년 1월 10일 18:54:25

문제 설명

666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

문제 링크

나의풀이

import sys
input = sys.stdin.readline
m, n = map(int, input().split())
for i in range(m,n+1):
    if i == 1:
        continue
    for k in range(2,int(i**0.5)+1):
        if i % k == 0:
            break
    else:
        print(i)

에라토스테네스의 체로 분류된 문제다. 2부터 i의 제곱근보다 작거나 같은 수 까지 i에서 나눠줘서 몫이 0이면 소수가 아니니까 break하고, 그렇지 않으면 i를 프린트 하면 된다.

성능 요약

메모리: 32412 KB, 시간: 5972 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2025년 1월 7일 14:36:11

문제 설명

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

import sys
input = sys.stdin.readline
n, k = map(int, input.split())
answer = 1
for i in range(k):
    answer *= n
    n -= 1
div = 1
for i in range(2,k+1):
    div *= i

print(answer//div)

이항 계수 계산 프로그램

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $K$가 주어진다.
$1 \leq N \leq 10$, $0 \leq K \leq N$

출력

$\binom{N}{K}$를 출력한다.