Itertools

python Itertools에는 여러가지 유용한 클래스들이 들어있다.

• products : 중복 순열
• permutations : 순열
• combinations : 조합
• combinations_with_replacement : 중복 조합
• accumulate : 이터레이터의 값들을 앞 인덱스에서부터 누적
• batched : 이터레이터를 정해진 숫자 길이만큼 분할해서 보여줌
• compress : 이터레이터들의 원소를 선택할 수 있음

Permutations

• Permutations 내부 구현

  iterable에서 연속된 길이 r 순열을 반환한다.

  r이 지정되지 않았거나 None이면, r의 기본 값은 iterable의 길이이고 가능한 모든 최대 길이 순열이 생성된다.

  → 즉 r 값을 주지 않으면 N! 개의 결과가 나온다는 사실

  순열(permutation) 튜플은 입력 iterable의 순서에 따라 사전식 순서로 방출된다.

  따라서 입력 iterable이 정렬되어 있으면, 순열 튜플이 정렬된 순서로 생성된다.

  요소는 값이 아니라 위치로 고유성을 다룬다. 따라서 입력 요소가 고유하면, 각 순열에 반복 값이 없다.

  → iterable의 각 원소의 값을 기준으로 순열을 생성하는 것이 아닌, 인덱스를 기준으로 순열을 생성한다는 말인 듯

  def permutations(iterable, r=None):
      # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
      # permutations(range(3)) --> 012 021 102 120 201 210
      pool = tuple(iterable)
      n = len(pool)
      r = n if r is None else r
      if r > n:
          return
      indices = list(range(n))
      cycles = list(range(n, n-r, -1))
      yield tuple(pool[i] for i in indices[:r])
      while n:
          for i in reversed(range(r)):
              cycles[i] -= 1
              if cycles[i] == 0:
                  indices[i:] = indices[i+1:] + indices[i:i+1]
                  cycles[i] = n - i
              else:
                  j = cycles[i]
                  indices[i], indices[-j] = indices[-j], indices[i]
                  yield tuple(pool[i] for i in indices[:r])
                  break
          else:
              return

combinations

• Combinations 내부 구현

  입력 iterable에서 요소의 길이 r 서브 시퀀스들을 반환한다.

  조합(combination) 튜플은 입력 iterable의 순서에 따라 사전식 순서로 방출된다.

  따라서 입력, iterable이 정렬되어 있으면, 조합 튜플이 정렬된 순서로 생성된다.

  요소는 값이 아니라 위치로 고유성을 다루며, 입력 요소가 고유하면, 각 조합에 반복 값이 없다.

  → 인덱스 값이 고유하면 같은 값으로 취급

  def combinations(iterable, r):
  # combinations('ABCD', 2) --> AB AC AD BC BD CD# combinations(range(4), 3) --> 012 013 023 123pool = tuple(iterable)
      n = len(pool)
  if r > n:
  returnindices = list(range(r))
  yield tuple(pool[i]for iin indices)
  whileTrue:
  for iin reversed(range(r)):
  if indices[i] != i + n - r:
  breakelse:
  returnindices[i] += 1
  for jin range(i+1, r):
              indices[j] = indices[j-1] + 1
  yield tuple(pool[i]for iin indices)

예시

from itertools import combinations, permutations

list1 = [1,2,3,4]
perm1 = list(permutations(list1))
comb1 = list(combinations(list1,3))

print("##############permutations##############")
for i in perm1:
    print(i)

print("##############combinations##############")
for i in comb1:
    print(i)

##############permutations##############
(1, 1, 3, 4)
(1, 1, 4, 3)
(1, 3, 1, 4)
(1, 3, 4, 1)
(1, 4, 1, 3)
(1, 4, 3, 1)
(1, 1, 3, 4)
(1, 1, 4, 3)
(1, 3, 1, 4)
(1, 3, 4, 1)
(1, 4, 1, 3)
(1, 4, 3, 1)
(3, 1, 1, 4)
(3, 1, 4, 1)
(3, 1, 1, 4)
(3, 1, 4, 1)
(3, 4, 1, 1)
(3, 4, 1, 1)
(4, 1, 1, 3)
(4, 1, 3, 1)
(4, 1, 1, 3)
(4, 1, 3, 1)
(4, 3, 1, 1)
(4, 3, 1, 1)
##############combinations##############
(1, 1)
(1, 3)
(1, 4)
(1, 3)
(1, 4)
(3, 4)

입력 iterable의 원소 순서만 바꿈

from itertools import combinations, permutations

list1 = [3,1,2,4]
perm1 = list(permutations(list1))
comb1 = list(combinations(list1,3))

print("##############permutations##############")
for i in perm1:
    print(i)

print("##############combinations##############")
for i in comb1:
    print(i)

결과

##############permutations##############
(3, 1, 1, 4)
(3, 1, 4, 1)
(3, 1, 1, 4)
(3, 1, 4, 1)
(3, 4, 1, 1)
(3, 4, 1, 1)
(1, 3, 1, 4)
(1, 3, 4, 1)
(1, 1, 3, 4)
(1, 1, 4, 3)
(1, 4, 3, 1)
(1, 4, 1, 3)
(1, 3, 1, 4)
(1, 3, 4, 1)
(1, 1, 3, 4)
(1, 1, 4, 3)
(1, 4, 3, 1)
(1, 4, 1, 3)
(4, 3, 1, 1)
(4, 3, 1, 1)
(4, 1, 3, 1)
(4, 1, 1, 3)
(4, 1, 3, 1)
(4, 1, 1, 3)
##############combinations##############
(3, 1)
(3, 1)
(3, 4)
(1, 1)
(1, 4)
(1, 4)

즉, 입력 iterable의 원소 순서가 바뀌면 출력된 순열/조합의 결과도 바뀐다.

또한, 순열, 조합의 각 경우들은 tuple 형태로 저장된다.

사용 예

[14889번 - 스타트와 링크](https://www.notion.so/14889-a052764506244978b8599c939e67920c?pvs=21)

문제

주제 - 덱, 큐, 스택

• 2346번 풍선 터뜨리기
• 24511번 queuestack
• 1464번 뒤집기 3
• 3078번 좋은 친구
• 17298번 오큰수

문제 공지

Lv.1

• 공원 산책

Lv.2

• 124 나라의 숫자
• [1차] 뉴스 클러스터링
• 리코쳇 로봇

Lv.3

• 가장 긴 팰린드롬

안건

• 스터디 인원 제한
  • 대면 회의이기 때문에 최대 인원을 정해둬야 할 것 같다.
  • 6명 or 8명
  • 6명 ✅
• 인원 추가 시점
  • 알잘딱
  • 중간에 받되 너무 후반이면 받지 않는걸로
• 문제 난이도
  • 조금 올려도 될 것 같다.
  • 쉬움 1 / 보통 2 / 어려움 2
• 깃허브 꼬인 거 수정하기
  • 스쿼시 머지를 하기 때문에 매주 브랜치를 새로 파야한다.
  • 브랜치 전략 문서화 하기 @bada308

발표

민규의 팁! @ps9319

• 알고리즘 시간복잡도 미리 계산해보기

• 파이썬에서 이쁘게 출력하기

print(*a)

바다의 팁! @bada308

• 반복문에 레이블을 달아봐요!

outer: while(true){
  inner: while(true){
    break outer;
  }
}

종민이의 팁! @rlajm1203

• 파이썬 자료형 List 와 Set

문제 공지

Lv.1

• 핸드폰 번호 가리기�
• 이상한 문자 만들기�

Lv.2

• 더 맵게
• 호텔 대실

Lv.3

• 부대복귀

문제 공지

Lv.1

• 덧칠하기

Lv.2

• 시소 짝궁
• 귤 고르기

Lv.3

• 단속카메라
• 디스크 컨트롤러

문제

DP

주제 -

• 신나는 함수 실행 9184번
• 쉬운 계단 수 10844번
• 계단 오르기 2579번
• 파도반 수열 9461번
• 스티커 9465번

문제

주제 - 백트래킹

• 카드 놓기 5568번
• N과 M (3) 15651번
• 스도쿠 2580번
• 연산자 끼워넣기 14888번
• 스타트와 링크 14889번

문제

주제 - dp

• 가장 긴 바이토닉 부분 수열 11054번
• 전깃줄 2565번

주제 - 누적합

• 구간 합 구하기 4 11659번
• 수열 2559번
• 인간-컴퓨터 상호작용 16139번

• 역할 분배
  • 문서화 : 강바다
  • 문제지기 : 박민규
  • 깃 관리 : 김수민
  • 총무 : 이지호
  • 기강 잡이 : 김종민

• 제출 날짜 정하기
  • 금요일 19시 00분 이전

• 문제 선정 방법 정하기
  • 매주 주제 정하기

• 플랫폼 결정
  • 백준
    • 문제 수 많고 접근성 좋다
  • 프로그래머스
    • 문제 수가 별로 없다
    • 잘할 때 넘어가도 될듯
  • 앨리스
    • 잘 모르겠다.
  • 구름 Level
    • 프로그래머스처럼 기출 문제 모아 놓은 사이트
    • 프로그래머스랑 겹치는 문제가 많은지는 모르겠다.

• 각 시즌 기간 정하기
  • 주제 리스트 선정
    [단계별로 풀어보기](https://www.acmicpc.net/step)
    • 12 [브루스 포스] ~ 40 [동적 계획법 3]
    • 매주 5개씩
    • 난이도 조절은 문제지기(주먹밥)이!

• 비대면 회의

  • 대면

  • 평일에 수업 다 끝나고 이야기

  • 금요일 7시~8시

  • 1명 랜덤으로 뽑기 + 공유하고 싶은 거 있는 사람 발표!

  • 주제는 아래서 하나씩 정하기!

    1. 문제 풀이 방법
    2. 문법 꿀팁
    3. 개념
    

• 벌칙
  • 벌금 : 안 푼 문제 당 5000원
  • 기한은 매우 엄격히,,,
  • 벌금 제대로 안 내면 감정회고

• 1시간 이상 문제를 못 풀면 답보고 풀어오기

문제 공지

Lv.1

• 개인정보 수집 유효기간
• 바탕화면 정리

Lv.2

• 피로도
• 더 맵게

Lv.3

• 섬 연결하기

문제 공지

• 1092 #배
• 11478 #서로 다른 부분 문자열의 개수
• 1764 #듣보잡
• 2002 #추월
• 22233 #가희와 키워드

문제 공지

브루트 포스

• 영화감독 숌 #1436번
• 숫자 정사각형 #1051번
• 문서검색 #1543번

어려운 브루트 포스 문제는 백트래킹이 다 섞여있어서 구현이나 문자열 문제로 구해봤어요

문제 공지

브루트포스 2문제 + 정렬 3문제

• 팰린드롬 만들기 #1254번
• 주사위 쌓기 #2116번
• 소트인사이드 # 1427번
• 좌표 정렬하기 # 11650번
• 좌표 압축 # 18870번

파이썬 자료형 List 와 Set

오늘은 백준 10815번을 풀다가 List와 Set에 대한 차이가 궁금했다.

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

나의 코드

위의 문제는 입력 받은 데이터들(카드) 안에 원하는 숫자 카드가 있는지 없는지를 출력하라는 문제이다.

문제 해결의 핵심은 데이터가 포함되어 있는지 즉, 멤버십 연산(in)을 통해 True이면 1, False 이면 0을 반환하는 문제이다.

실패 코드

import sys

N = int(sys.stdin.readline())

cards = list(map(int,sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline())

numbers = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(len(numbers)):
  if numbers[i] in cards:
    numbers[i] = 1
  else:
    numbers[i] = 0
for i in numbers:
	print(i)

성공 코드

import sys

N = int(sys.stdin.readline())

cards = set(map(int,sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline())

numbers = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(len(numbers)):
  if numbers[i] in cards:
    numbers[i] = 1
  else:
    numbers[i] = 0

for i in numbers:
  print(i, end=" ")

차이가 보이는가?

cards = set(map(int,sys.stdin.readline().rstrip().split())) # 성공

cards = list(map(int,sys.stdin.readline().rstrip().split())) # 실패

바로 입력 받은 카드들을 리스트로 저장하느냐 Set으로 저장하느냐의 차이이다.

실패 코드를 제출하면 시간 초과가 뜬다.

그 이유는 리스트에서의 멤버십 연산 때문인데, 리스트에서 원하는 원소가 포함되어 있는지 아닌지를 판별하려면 리스트의 모든 원소들을 일일이 한번 씩 비교하며 순회해야 한다. 이는 시간 복잡도가 O(n)에 해당한다.

in 연산을 감싸고 있는 for문 또한 n번 수행하므로 결국엔 시간 복잡도가 n^2이 되는 것이다.

반면에 Set은 멤버십 연산(in)의 시간 복잡도가 O(1)이다. 이를 n번 수행해봤자 시간 복잡도는 O(n)이다.

이러한 이유는 Set이 해시 테이블 (Hash Table)로 구현되어 있기 때문이다. 해시 테이블은 딕셔너리 형태와 비슷하다고 생각하면 된다.

어떤 데이터 값을 해시 함수에 넣으면 함수에 맞는 연산을 수행하여 그 결과에 맞는 데이터로 바뀌어 출력된다. (출력 결과를 해시값이라고 한다.)

Set은 해시 함수를 통해 해싱한 후 나온 결과 값을 배열의 인덱스로 사용하여, 해당 위치에 데이터를 저장하는 방식이다.

리스트는 멤버십 연산을 위해 리스트의 모든 원소를 뒤지는 반면, Set은 찾는 데이터를 해시 함수에 입력하여 인덱스에 바로 접근함으로써 아주 빠르게 존재의 유무를 판별할 수 있다.

물론 Set도 최악의 경우 x in s 연산의 시간 복잡도가 O(n)이 될 수 있다.

예를 들어, 해시 테이블에서 10살의 사람들만 세트에 저장했다고 생각해보자. 그러면 해시 함수를 통해 인덱스에 접근하더라도 인덱스가 가리키는 데이터는 10살인 사람들의 배열이므로 배열 안에서 멤버십 연산을 수행해야 하는 것이다.

(세트의 단일 원소로 배열을 넣으면 안될 듯)

리스트와 세트는 in 연산 외에도 원소를 삭제하는 remove 연산의 시간 복잡도도 다르다. 평균적으로 리스트는 O(n)이지만, 세트는 O(1)이다.

출처 : [https://velog.io/@ready2start/Python-세트set의-시간-복잡도](https://velog.io/@ready2start/Python-%EC%84%B8%ED%8A%B8set%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84)

안건

• 충돌난 pr 해결
• 시험기간 스터디 2주 휴식

발표

javascript에서 console.log를 최대한 줄이자.

가희와 키워드(22233) 문제에서 시간초과가 났는데, 알고리즘 상 문제가 아니라 비교적 시간이 오래 걸리는 I/O를 루프 문 안에서 선언해서 생긴 문제였다.

때문에, 입출력에서 드는 시간을 줄이기 위해 루프 문 안에서 console.log를 선언하는 것이 아니라 루프 문 밖에서 선언하는 것을 추천한다.

💡 현우님’s:
“최대한 키보드를 늦게 잡으려 하고, 위 순서대로 먼저 글 작성 후 코드를 작성했다.
저 방법대로 작성하고 나서 실력 좀 늘은 것 같다.
그리고 문제 맞으면 한 문장마다 왜 코드를 이렇게 짰는지 주석으로 다 작성하고 노션에 기록한다.

이렇게 하는 이유는 네카라 코테를 보면 문제들의 길이가 길다.
그래서 문제를 요약하고, 어떤 자료구조가 좋은지, 어떻게 풀어야 하는지 읽으면서 파악하는 게 가장 좋다.
그래서 문제 요약하고 논리 순서 확정하고 자료 연산 및 자료구조를 파악하는 연습을 하는 것이다.

물론 이 방법이 정답이 아닐 수도 있다. 알고리즘 공부를 하면서 여러 방법을 많이 시도해 보았지만 이 방법이 나에게 잘 맞았고, 알고리즘 풀이 능력이 가장 많이 늘었다고 생각해서 공유해본다. ”

알고리즘 공부 방법

문제 요약

• 각 대기실 별 거리두기가 잘 되는지 확인
  • 파티션으로 막혀 있거나
  • 맨허튼 거리가 2이하면 X→ 3 이상이 거리두기가 된 것

논리적 순서 확정

• 대기실은 완탐하면서 P가 나오면 bfs를 수행
  • bfs를 수행하면서 P를 보면 거리가 몇인지 구한다.
  • 이때, 파티션이 보이면 다음으로 이동 X
  • 0일 때만 이동한다.

필요한 자료연산 리스트업

• bfs
  • 4방향으로 이동하면서 count 늘리기
  • 만약 P를 만났는데 count가 2이하면 false를 반환

이에 제일 유리한 자료구조 선택

• info에 좌표와 count 넣기

구현

static String getBinary(int num, int n) {

	//이진수를 이루는 숫자의 개수가 n개보다 작으면 앞에서부터 0을 채워야함
	// 그래서 앞뒤로 채우기 쉬운 덱을 사용

	Deque<Integer> q = new ArrayDeque<>();

	//이진수 만들기
	while (num > 0) {
		q-offerFirst (num % 2);
		num = num / 2;
	｝

	//size가 n보다 작으면 앞에서부터0을 채워넣어줘야함
	while (q-size() < n) {
	 q.offerFirst(0);
	｝
	String rel = "";
	//앞에서부터 하나씩 poLL하여 이진수를 합쳐준다 //여기서 rel을 숫자로 하게 되면 더하기 때문에 자릿수를 알 수 없게 된다
	while (!q.isEmpty()) {
		rel += q-pollFirst();
	｝

	return rel;

｝

오답노트(새롭게 알게 된 점)

Stringll result = new String[n];
	for (int i = 0; i < n; i++) {
	//자바에서 제공하는 이진수로 변환하는 메서드가 존재 //tooctalstring, toHexstring도 존재한다 //or(1) 비트 논리 연산 수행
	//비트연산을 하게 되면 5자리가 안되는 이진수의 나머지를 채울 필요가 없이 0으로 계산된다
	String s = Integer.toBinaryString(arr1[il| arr2[il);

	//n자리의 문자열 형태로 포맷을 변경 //n자리가 안되는 이진수의 나머지는 공백으로 채움 
	// 공백은 어차피 나중에 공백으로 출력하기 때문에 그대로 두면 된다 
	//n자리가 안되는 경우는 arrl[1], arr2[1] 모두 n-1이하일 경우
	S= String.format("은" + n + "s", s);

	System.out.println("s = " + s);

	s=s.replaceALL（"1","#"）；
	s=s.replaceAll("0", " ");

	System.out.println("replace s = " + s) ;

	result[i] = s;
｝
return result;

안건

• dp 난이도 어땠나?
  • 어려웠다,,,,
  • 다음주엔 더 난이도 높은 dp 문제

발표

민규의 파이썬 팁

파이썬 출력 형식 format

파도반 수열

점화식이 두 종류가 나온다..!!!!!

• dp[i] = dp[i-1][i-5]
• dp[i] = dp[i-2][i-3]

문제

주제 - 안알랴줌

• 1743 음식물 피하기
• 2293 동전1
• 1744 수 묶기
• 15988 1, 2, 3 더하기 3
• 1926 그림