본문 바로가기

전체 글

 (85)
Greedy Algorithm (그리디 알고리즘) 그리디 알고리즘이란? 그리디 알고리즘은 눈앞의 이익만을 좇는 알고리즘이다. 그리디 알고리즘은 앞의 선택이 이후 선택에 영향을 주지 않는 문제에 잘 작동한다. 그리고 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 알고리즘이다. 대부분의 경우 계산 속도가 빠르므로 매우 실용적이다. 배낭 문제 문제 현재 15kg를 담을 수 있는 배낭, A (12kg, 4달러), B (1kg, 2달러), C (4kg, 10달러), D (1kg, 1달러), E (2kg, 2달러)가 있다. 달러의 가치가 최대가 되도록 배낭에 넣을 짐을 골라보자. 풀이 단가가 가장 높은 짐부터 배낭에 담으면 된다. 동전 바꾸기 문제 문제 현재 알바생에게 10원, 50원, 100원이 존재한다. 160원을 동전의 개수..
회의실 배정 [백준 1931번] 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 내 풀이 그리디 알고리즘이다. 가장 먼저 끝나는 회의를 선택한 후, 그 회의를 기점으로 시작하는 시간이 금방 다가오는 회의를 선택하는 방법으로 풀었다. 여기서 중요한 것은 정렬이다. 끝나는 시간을 기준으로 오름 차순 정렬하고, 끝나는 시간이 같다면 시작하는 시간을 기준으로 오름 차순 정렬해야 한다. "끝나는 시간으로만 정렬하면 안되나요?"라는 질문을 했을 때의 답변은 "안됩니다."이다. 2 3 3 1 3 의 예제를 생각해보자. 1. 끝나는 시간으로만 정렬하면 [(3, 3), (1, 3)]이 되기 때문에 답은..
TabError: inconsistent use of tabs and spaces in indentation 배경 Tab을 사용해서 들여 쓰기를 했는데 탭 에러가 났다. 칸 띄우기만 하면 되는거 아니냐고!!! 아니다. 그렇다면 어떻게 해결해야 할까? 파이썬에서 들여쓰기를 할 때 Tab or Space 4칸이다. 둘 중 하나만 해야 한다. 혼용하면 안 된다. 나는 전부 Space 4칸으로 들여 쓰기 한 코드에 Tab을 사용했더니 에러가 난 것이었다. Tab으로 들여쓰기 했던 부분을 Space 4칸으로 간단히 해결~
sys.path에 대해 알아보자 sys.path에 대해 알아보게 된 배경 파이썬 코딩을 하다가 python scripts/train.py를 실행시켰는데 에러가 났다. 원인은 train.py에 있던 from datasets.train_dataset import CustomDataset이었다. ModuleNotFoundError: No module named 'datasets' 분명히 경로 설정을 했는데, 왜 'datasets' 모듈을 못 찾는 것인지 이해할 수 없었다. 그래서 열심히 다른 코드를 뒤지던 중, 해결방법을 찾았다. import sys sys.path.append(".") sys.path.append("..") 이 코드를 추가하니 바로 해결이 되었다. 그렇다면 sys.path는 무엇인가? import문을 통해 다른 파이썬 파일..
퇴사 [백준 14501번] 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 내 풀이 처음에 배열로 다이나믹 프로그래밍을 하려다가, 머리가 안 돌아가서 재귀 함수를 사용하였다. 여기서 포인트는 i일을 선택할 것인지 또는 선택하지 않을 것인지 구현하는 것이다. 만약 i일을 선택할 경우, time[i]도 고려해야 한다. import sys input = sys.stdin.readline N = int(input()) time, pay = [0], [0] for i in range(N): t, p = map(int, input().split()) time.append(t); pay.append(p) MAX =..
테트로미노 [백준 14500번] 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 내 풀이 ㅗ를 제외한 나머지 테트로미노는 dfs로 만들 수 있다. 그러나 ㅗ는 모양이 요상하게 생겼기 때문에 따로 만들어야 한다. 1. ㅗ를 제외한 나머지 테트로미노 늘 사용하는 dfs 코드로 짰다. 백트래킹이기 때문에 재귀를 다 돌리고 난 후 check를 다시 False로 만들어주어야 한다. 2. ㅗ ㅗ로 총 4가지 모양을 만들 수 있다. ㅗ, ㅜ, ㅓ, ㅏ 그래서 제일 처음에 for문을 ..
로봇 청소기 [백준 14503번] 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 내 풀이 dir를 딕셔너리로 만들고, 문제에서 주어진대로 '북, 동, 남, 서' 방향을 적었다. 현재 방향을 기준으로 왼쪽 방향을 탐색하기 때문에, 현재 방향에서 왼쪽으로 가려면 거꾸로 가야 한다. (ex. 현재 방향이 북쪽인 경우 : 북 -> 서 -> 남 -> 동) 그래서 d = (d - 1) % 4를 해서 왼쪽 방향을 탐색하도록 하였다. 네 방향을 탐색해야 하기 때문에 range(4)로..
플레이페어 암호 문제 https://softeer.ai/practice/info.do?idx=1&eid=804 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 내 풀이 입력으로 메시지와 키를 입력받는다. 원래 입력 받을 때 input()을 사용했었지만, 소프티어 사이트에서는 sys를 사용하길 원하는 것 같아서 sys를 사용한 입력으로 코드를 수정하였다. (시간이 더 빨라짐) key를 가지고 표를 만들었다. key에 있는 알파벳 먼저 배치한 후, 빈 곳은 사용하지 않은 알파벳을 사용하여 채워 넣었다. 1차원인 board 리스트에 알파벳을 냅다 쑤셔 넣었기 때문에 nboard라는 새로운 리스트를 선언하여 5x5 크기의 2차원 리스트로 만들었다. 메시지를 쪼갠 후 같은 알파벳이 연속으로 나..

티스토리툴바