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

문제

입력

출력

풀이방법

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

이 문제와 비슷하게 풀면 됩니다.

dx, dy 뿐만 아니라 dz 까지 추가해서 동, 서, 남, 북, 상, 하까지 6가지 방법으로 BFS를 사용해서 출구를 찾으면 됩니다. 대신에 출구를 찾지 못하면 Trapped!를 출력하면됩니다.

코드

import sys
from collections import deque

input = sys.stdin.readline

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

def bfs():
    while s:
        item = s.popleft()
        z, x, y, cnt = item
        if E[0] == x and E[1] == y and E[2] == z:
            return cnt
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]

            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
                if not visited[nz][nx][ny] and (matrix[nz][nx][ny] == '.' or matrix[nz][nx][ny] == 'E'):
                    visited[nz][nx][ny] = True
                    s.append([nz, nx, ny, cnt + 1])

    return -1


while True:
    h, n, m = map(int ,input().rstrip().split())
    matrix = []
    if h == n == m == 0:
        break

    # 행렬 입력
    for __ in range(h):
        if __ > 0:
            input()
        temp = [list(list(input().rstrip())) for _ in range(n)]
        matrix.append(temp)

    visited = [[[False] * m for _ in range(n)] for __ in range(h)]

    s = deque([])

    roof = False
    for k in range(h):
        for i in range(n):
            for j in range(m):
                if matrix[k][i][j] == 'S':
                    s.append([k,i,j,0])
                    visited[k][i][j] = True
                if matrix[k][i][j] == 'E':
                    E = [i,j,k]

    # s 위치 찾기
    result = bfs()

    if result == -1:
        print("Trapped!")
    else:
        print(f"Escaped in {result} minute(s).")
    input()

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

문제

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return 하도록 solution 함수를 완성해 주세요. ※ 각 원 위의 점도 포함하여 셉니다.

입출력( + 추가적인 Test Case)

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

1. 한 사분면에 대해 두 원 사이에 있는 점을 구한 뒤에 4를 곱하면 총점의 개수입니다.

2. x는 1부터 r2(큰원까지) 순회하면서 점을 구합니다.

* 각각의 x에 대해서 총 2가지 case(큰 원 위에 점이 있는 경우와 없는 경우)가 존재합니다.

3. x가 r1 보다 작을 때입니다.

  3-1 r2 안에 있는 점들을 모두 구합니다. (이때 r2 원 위에 점이 있는지 없는지를 구합니다.) 

  3-2 r1 안에 있는 점들을 구한뒤 r2 점 개수 - r1 점 개수를 하고 총합에 더합니다.

4. x가 r1 과 같거나 큰 경우입니다.

  4-1 r2 밑에 있는 점들을 구한 뒤 총합에 더합니다.

5. 점의 총합에 4를 곱한 뒤 반환합니다.

코드

from math import isqrt


def solution(r1, r2):
    r2_dots = 0
    # x 좌표로 계산
    for x in range(1, r2 + 1):
        y2 = isqrt(r2 ** 2 - x ** 2)

        # x와 평행한 선을 기준으로 r1과 r2가 모두 걸칠 때
        if x < r1:
            y1 = isqrt(r1 ** 2 - x ** 2)
            # 선 위에 점이 있는 경우
            if r1 ** 2 - x ** 2 == y1 ** 2:
                y1 = y1 - 1

        else:
            y1 = 0
            r2_dots += 1

        r2_dots = r2_dots + y2 - y1
    # 상하좌우 대칭이므로 4를 곱한다.
    return r2_dots * 4

결론

for 문 하나 만으로 풀 수 있는 간단한 문제였다. 시간복잡도가 O(n)이다.

처음에 dp를 생각해서 풀었지만, 계속 오류가 발생했다. 그 이유는 원 위에 있는 점들을 계산하지 못하면서 오류가 발생했다.

원 위에 있는 점들을 생각하면서 위와 같은 식들을 생각해 냈다.

1. 원 위에 점이 있는지 없는지를 구하는 것

2. 원은 상하좌우 대칭이기에 한 사분면만 구하고 4를 곱해서 시간을 아낄 것

두 가지를 생각해 내서 푼 문제였다. 처음에 접근하는데 시간이 오래 걸려서 1시간 넘게 풀었던 문제다.

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

문제

USED_GOODS_BOARD 테이블에서 2022년 10월 5일에 등록된 중고거래 게시물의 게시글 ID, 작성자 ID, 게시글 제목, 가격, 거래상태를 조회하는 SQL문을 작성해주세요. 거래상태가 SALE 이면 판매중, RESERVED이면 예약중, DONE이면 거래완료 분류하여 출력해주시고, 결과는 게시글 ID를 기준으로 내림차순 정렬해주세요.

출력

SQL문을 통해서 다음과 같이 출력 되어야 한다.

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

1. USED_GOODS_BOARD 테이블에서 참고하기 때문에 FROM 부터 작성했습니다.

FROM USED_GOODS_BOARD

2. CREATED_DATE 가 2022-10-05인 데이터를 조회했습니다.

WHERE CREATED_DATE = "2022-10-05"

3. 게시글 ID기준으로 내림차순 정렬하는 코드를 작성했습니다.

ORDER BY BOARD_ID DESC

4. 마지막으로 STATUS 상태에 따라서 "예약중", "판매완료", "판매중" 을 CASE 문을 쓰면서 SELECT문을 작성했습니다.

SELECT BOARD_ID, WRITER_ID, TITLE, PRICE, 
CASE WHEN STATUS='SALE' THEN '판매중'
	WHEN STATUS='DONE' THEN '거래완료'
    ELSE '예약중'
    END AS STATUS

코드

SELECT BOARD_ID, WRITER_ID, TITLE, PRICE, 
CASE WHEN STATUS='SALE' THEN '판매중'
	WHEN STATUS='DONE' THEN '거래완료'
    ELSE '예약중'
    END AS STATUS
FROM USED_GOODS_BOARD
WHERE CREATED_DATE = "2022-10-05"
ORDER BY BOARD_ID DESC;

결론

CASE문을 처음작성하느라 조금 낯설었지만 충분히 해결할 수 있는 문제다.

나머지 SELECT, FROM, WHERE, ORDER BY 모두 데이터베이스 수업시간에 들었던 내용들이라 어려움없이 해결할 수 있었다.

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

문제

더보기

프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이"원쿠션"(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 "원쿠션" 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. "원쿠션" 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

위 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

위 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

입출력( + 추가적인 Test Case)

제한사항

풀이방법

정답률과 별개로 생각보다 단순한 문제였다는게 허무했습니다. (정답률 보고 어려울까봐 많이 걱정했습니다.)

풀이방법은 다음과 같습니다.

1.  검은 공을 상, 하, 좌, 우 대칭이동을 합니다.

2. 검은 공이 흰공이 쿠션을 못하도록 막는 경우를 제외시킵니다.(start와 end의 좌표를 계산합니다.)

3. 나머지 경우에 대해서 최소 값을 구하여 리스트에 추가합니다.

코드

import math


def cal_distance(x1, y1, x2, y2):
    result = math.sqrt(math.pow(x1 - x2, 2) + math.pow(y1 - y2, 2))
    return result


def solution(m, n, startX, startY, balls):
    answer = []
    for endX, endY in balls:
        dots = []
        # 상
        if not (startX == endX and startY < endY):
            dots.append(cal_distance(startX, 2 * n - startY, endX, endY))
        # 하
        if not (startX == endX and startY > endY):
            dots.append(cal_distance(startX, -startY, endX, endY))
        # 좌
        if not (startX > endX and startY == endY):
            dots.append(cal_distance(-startX, startY, endX, endY))
        # 우
        if not (startX < endX and startY == endY):
            dots.append(cal_distance(2 * m - startX, startY, endX, endY))

        answer.append(round(math.pow(min(dots), 2)))

    return answer

결론

정답률보고 쫄지말고 일단 해봐야겠습니다. 평행이동만 할 줄 알면 엄청 쉬운문제입니다.

근데 2시간 넘게 걸렸네요.. 스펠링하나 잘못써서 X를 Y라고 써서 괜한 시간을 많이써서 다음엔 더 주의하겠습니다. 

(아까운 내 2시간 ㅠㅠㅠㅠㅠㅠ)

Sort() 함수

sort() 함수는 리스트를 오름차순으로 정렬하는 함수이다. (반환 X)

리스트만 사용할 수 있기 때문에 sorted() 함수에 비해서는 덜 편리한 편이다.

str_N =['1','7','10','4','5','6','3']	#string 형
int_N =[ 1 , 7 , 10 , 4 , 5 , 6 , 3 ]	#int 형

int_N.sort()
str_N.sort()
# 원소의 위치를 오름차순으로 바꾼다.

print(int_N)
# [ 1 , 3 , 4 , 5 , 6 , 7, 10 ]

print(str_N)
# ['1','10','3','4','5','6','7']

# 원소들이 int 형이 아닌 string 형이다.
# 그러므로 크기가 아닌 사전순으로 정렬된다.

Sorted() 함수 그리고 내림차순

sort함수는 리스트만 쓸 수 있는 것에 비해 sorted 함수는 다른 객체에서도 사용이 가능해서 더욱 편리하다.

str_N =['1','7','10','4','5','6','3']	#string 형
int_N =[ 1 , 7 , 10 , 4 , 5 , 6 , 3 ]	#int 형

# 오름차순
print(sorted(int_N))
# [ 1 , 3 , 4 , 5 , 6 , 7, 10 ]

print(sorted(str_N))
# ['1','10','3','4','5','6','7']

# 내림차순

print(list(reversed(sorted(int_N))))
# [ 10 , 7 , 6 , 5 , 4 , 3 , 1 ]

print(list(reversed(sorted(str_N))))
# ['7','6','5','4','3','10','1']

딕셔너리 등 다루는 것들은 추후에 추가할 예정.

오류 있으면 댓글 부탁드립니다.

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

문제

고려대학교에 입학한 새내기 호돌이는 안암역을 지나다가 한 붕어빵 장수를 만났어요.

“안녕, 안녕, 안녕하십니까, 아저씨! 붕어빵 두 개 주세요.”

“안녕을 세 번 외쳤으니 붕어빵 세 개!”

붕어빵 두 개의 값을 내고 세 개를 받은 호돌이는 기분이 좋았어요. 호돌이가 붕어빵 하나를 꺼내어 한 입 물었는데…. 너무 뜨거워서 그만 붕어빵을 떨어뜨리고 말았어요ㅠㅠ

붕어빵은 자유 낙하운동을 하면서 땅에 떨어졌는데 신기하게도 좌우가 뒤집힌 모양으로 착지했답니다. 호돌이가 붕어빵을 한 입 물기 전의 모양이 입력으로 주어지면, 땅에 떨어졌을 때에는 어떤 모양일지 출력하세요.

입력

출력

풀이방법

각 줄을 반대로 출력하면 간단하게 풀리는 문제다.

코드

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

for i in range(N):
    Bread=input() 	# 각 줄을 입력받음
    print(Bread[::-1])	# 각 줄을 반대로 출력한다.

1. 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 다음과 같이 불리기도 한다.

• 욕심쟁이 방법
• 탐욕적 방법
• 탐욕 알고리즘 

이렇게 불리는 이유는 단어의 정의 때문이다.

Greedy
1. 욕심 많은
2. 탐욕적인

최적화 문제를 해결하는 알고리즘 중 하나이다. 각 단계에서 선택가능한 해들 중에서 가장 좋은 해를 찾는 문제이다. 데이터 간의 관계를 고려하지 않고 수행 과정에서 단계에 최적해인 최솟값 또는 최댓값을 가진 데이터를 선택한다.이를 '근시안적 선택'이라고 말하기도 한다.  

각각의 단계에서의 선택(부분해)을 모아서 문제의 최적해를 도출한다.

2. 그리디 알고리즘의 특징

섬 A에서 섬 C를 가는 최소 경로를 구하는 문제를 통해 알아보겠다.

섬 A 에서 섬 C로 가려면 A to B, B to C로 가야한다.

A to B 의 부분해, B to C 의 부분해를 구해서 문제의 최적해를 구한다.

여기서 특징을 알 수 있다. 각 단계에서 구한 답은 절대로 번복하지 않으며, 이후 단계는 이전 단계의 데이터를 통해 계산하지 않는다.(독립적)

다시 특징을 정리하자면

1. 한번 선택한 해답 (각각의 단계에서 구한 부분해)은 절대로 번복하지 않는다. 즉, 선택한 데이터를 버리고 다른 것을 취하지 않는다.

2. 알고리즘은 단순하며, 매우 제한적인 문제들만 그리디 알고리즘으로 해결가능하다.

3. 다른 알고리즘에 비해 계산시간이 매우 빠른 편이다.

그리디 알고리즘을 문제를 해겷하기 위해선 각각의 최적해들이 항상 최적임을 보장해야한다. 

3. 그리디 알고리즘과 동적 계획법의 차이

( Greedy Algorithm vs Dynamic Programming(DP))

4. 그리디 알고리즘 예시 

다음은 그리디 알고리즘을 사용하는 예시이다.

4.1 동전 거스름돈 ( Coin Change)

https://giliit.tistory.com/61

4.2 최소신장 트리 ( MST, Minimum Spanning Tree)

• Kruskal MST
• Prim MST

4.3 최단경로 찾기 ( Shortest Path)

• Dijkstra Shortest Path

4.4 부분 배낭 문제 ( Fractional Knapsack)

4.5 부분 집합 문제 ( Set Covering)

4.6 작업 스케줄링 ( Task Scheduling)

4.7 허프만 압축 ( Huffman Coding)