본문 바로가기

전체 글

 (151)
[Python/백준] 16922. 로마 숫자 만들기 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기순열과 조합https://www.acmicpc.net/problem/169221차 시도) 실패import sysfrom itertools import combinations_with_replacementinput = sys.stdin.readline# 로마 숫자 문젠데, 그냥 단순히 더하기로 한다.# 로마 숫자 N개를 사용해 만들 수 있는# 서로 다른 수의 개수는?# 즉, 1, 2, 3, 4의 숫자가 있을 때, (실제론 0 1 2 3)# 이 숫자들로 순서 고려하지 않고, 중복 허용해서 n개 뽑아# 만들 수 있는 모든 수의 경우의 수를 구하면 됨.# 즉, 중복 조합 4Hn을 구하면 됨.# 입력 ..
[Python/백준] 6603. 로또 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기순열과 조합https://www.acmicpc.net/problem/6603풀이import sysinput = sys.stdin.readline# 1, 2, ..., 49에서 6개를 고를 건데,# 49가지 중 k개 먼저 뽑아서 집합 S 만들거고,# 그 S를 가지고 6개를 뽑을 거임.# 입력 : k랑 S에 포함되는 수 일렬로# 출력 : 6개 수 고른 모든 방법.# 이거 49개 중에서 순서를 고려하지 않으며, 중복을 고려하지 않는,# 즉 조합 문제임. S 집합을 가지고 kC6을 하면 됨.def combinations(current, start): if len(current) == 6: ..
게임에도 사용 가능한 OCR 툴, 'lookupper' 소개!!! 안녕하세요!~!~~! 커피러브입니다. 영어로 스팀 게임을 하다가 모르는 영어단어가 있을 때,알트탭 눌러서, 인터넷 사전에 입력해서, 엔터 누르고...이랬던 기억 있지 않으셨나요~?~?? 전 MORT라는 OCR 번역기 프로그램을 안 후로는, 이걸 나름 유용히 써먹고 있었는데...문제는... 도트 게임을 하니까 도트가 인식이 잘 안됩니다 ㅠ전혀 다른 문자로 인식이 돼요 ㅠㅠㅠㅠㅠㅠㅠ아무래도 일정 영역을 통째로 읽어 인식하는 거고, 도트는 OCR들 training set에 별로 포함되어 있지 않았는지... ㅠ 또 이건 여담이지만, 해당 프로그램은 문장을 통째로 번역해주는데, 보통은 문장 내 단어 한 두개만 알면 해석이 되는 경우가 많아서 스포당하는(ㅋㅋ) 기분도 있구요. 결국 그래서 ㅠㅠㅠ 도트겜은 악깡버로 ..
[Python/DailyAlgo] 99, 100, 101, 102. 순열, 조합, 중복순열, 중복조합 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기순열과 조합 https://dailyalgo.kr/ko/problems/99https://dailyalgo.kr/ko/problems/100https://dailyalgo.kr/ko/problems/101https://dailyalgo.kr/ko/problems/102순열과 조합 기본 유형 4문제라서 한꺼번에 묶었습니당~~~순열더보기재귀로 직접 구현 풀이def solution(n, m): def permutations(current): # 만약 목표 길이 도달했으면 -> return # 아니라면 -> 계속 함수 실행 if len(current) == ..
[알고리즘 코딩캠프 6일차] 순열, 조합, 중복순열, 중복조합, 백트래킹 제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.목차 :순열과 조합순열조합중복순열중복조합백트래킹순열과 조합더보기직접 구현할 경우, 재귀를 사용해 구현.순열과 조합의 직접 구현 2단계뽑고 싶은 만큼 뽑았다면 종료한다.그렇지 않다면, 재귀를 돌면서 수를 더 뽑는다.(참고로, bfs와 달리 재귀 및 재귀를 사용한 dfs는 종료 조건이 action 부분에 있어도 ㄱㅊ. 오히려 코드 깔끔해짐.) 코테에선 대부분의 경우 `itertools 모듈` 내 함수들을 import해서 쓰게 됨.왜냐? 그게 당연히 더 빠르기도 하고, 순열조합은 보통 문제의 과정으로서 등장하기에 알고리즘 자체에 변형을 가할 일은 별로 없기 때문.순열더보기# 순열(pe..
[Python/백준] 7562. 나이트의 이동 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기DFS/BFShttps://www.acmicpc.net/problem/7562풀이1차 풀이: 고전적으로 dist정보 큐에 같이 넣기from collections import dequeimport sysinput = sys.stdin.readline# 이거 BFS로 델타 탐색 쓰긴 쓰되, 델타값 정의를 좀 특수하게 하면 될듯함. 2칸 1칸씩.iteration = int(input())for _ in range(iteration): l = int(input()) sx, sy = map(int, input().split()) tx, ty = map(int, input().split(..
[Python] 튜플을 큐(덱)에 넣을 때 할 수 있는 실수 - 원소가 한 개인 튜플. https://www.acmicpc.net/problem/7562 해당 문제를 풀던 중, 다음과 같이 코드를 짜고 있었다. 일반적으로 덱에 튜플을 정의할 때 많이 쓰는 코드 뭉치이다.queue = deque([(sx, sy, 0)])근데, 의문점이 생겼다.  저거 튜플 하나가 메모리에 잡히고, 그 튜플을 감싸는 리스트가 메모리에 잡히게 된 다음에, 그걸 deque에 일종의 append를 하는 과정이 압축되어 있는 건데, 리스트보단 튜플이 아주 미미하지만 오버헤드 때문에 메모리 사용량이 더 크므로(더블링을 위한 정보 등을 저장해야 하니까),그냥 튜플로 튜플을 감싸서 deque에 넣으면 안 될까? 즉, 아래처럼 말이다.queue = deque(((sx, sy, 0)))근데... 이렇게 하면, `sx`, `s..
[Python/백준] 7569. 토마토 3차원 문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.문제 유형 보기더보기DFS/BFShttps://www.acmicpc.net/problem/7569풀이유사 3차원 실제는 2차원 풀이from collections import dequeimport sysinput = sys.stdin.readlineM, N, H = map(int, input().split())# 아래 반복문 list comprehension으로 개선하기!!box = []for _ in range(N * H): box.append(list(map(int, input().split())))# 층을 고정한 상태에서, 행을 고정한 상태에서, 열을 기준으로 먼저 돌린다!!queue = deque((i..

티스토리툴바