본문 바로가기

분류 전체보기

 (87)
인구 이동 [백준 16234번] 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 내 풀이 BFS를 사용해서 국경선을 공유하는 그룹을 찾고, 국경선을 공유하는 그룹에는 몇 개의 나라가 있는지 리턴하는 함수를 만들었다. 인구 이동이 며칠 동안 이루어지는지 구해야 하므로 while 반복문을 사용했고, 여기서 while문을 중단시키기 위한 조건이 중요하다. 국경선을 공유하는 그룹이 1개 이상인 경우 flag를 True로 만들었다. flag가 계속 False라면 인..
치킨 배달 [백준 15686번] 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 내 풀이 나도 combinations 써서 구현할까 하다가 재귀 함수 연습할 겸 재귀로 풀어보았다. 재귀 함수 백트래킹을 사용하여 치킨집 중에서 M개를 선택하였다. 선택된 치킨집과 집과의 거리를 구하였다. import sys, math input = sys.stdin.readline N, M = map(int, input().strip().split()) city, ho..
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문을 ..

티스토리툴바