본문 바로가기

Algorithms & Languages

 (78)
[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: ..
[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..
[Python] 이미 동적 타입 언어인 파이썬에 제네릭을 사용하는 이유. 제네릭 프로그래밍을 설명할 때 흔히 '타입을 미리 정하지 않고, 사용될 때 그 타입을 결정하는 방식'이라고 설명한다. 하지만, 나는 이게 상당히 C++나 자바틱한 설명이라고 생각한다.왜냐하면, 사실 파이썬은 이미 동적 타입 언어(Dynamically typed language)이기 때문에, 저 설명을 들으면 '사용될 때 정해진단 거, 런타임 때 정해진단 거 아니야? 파이썬은 이미 런타임 때 타입이 결정되는데, 제네릭을 쓰는 의미가 있나? 동적 타이핑은 이미 파이썬에 있는 기능 아닌가?'하는 의문이 들 수 있기 때문이다. 사실 내가 그랬고, 자바에서 제네릭을 간단히 배우긴 했지만 그 때는 코드 따라치기에 급급했지 제대로 이해하진 못했었다.그래서 이번 글로 정리해보려고 한다.우선 제네릭을 이해하기 위해 잠시..

티스토리툴바