BOJ_2231 분해합 -Python3

문제분석

1. 관찰
- 분해합: N을 이루는 각 자리수의 합
- m을 증가시켜가며 sum 을 N과 비교한다.
- N과 같을 때 출력하고
- N과 같은 경우가 없는 경우 for - else 구문으로 0을 출력한다.

2. 복잡도
- O(N) = 1,000,000 >> 가능

3. 자료구조
- 각자리수 분해 : int[] -> list(map(int, str(i)))

해결코드

import sys
si = sys.stdin.readline

N = int(si())
for i in range(1,N):
    s = i + sum(list(map(int,str(i))))
    if s == N:
        print(i)
        break 
else: # 생성자가 없는 경우 0 출력, for - else 구문
    print(0)

'Etc > PS' 카테고리의 다른 글

BOJ_7568 덩치 -Python3  (0) 2022.08.05
BOJ_1436 영화감독 숌 -Python3  (0) 2022.08.05
BOJ_2798 블랙잭 -Python3  (0) 2022.08.04
BOJ_1065 한수 -Python3  (0) 2022.08.03
BOJ_20207 달력 -Python3  (0) 2022.08.03

순열(permutations)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서대로 나열하는 경우의 수

순열 구현

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([],used)

조합(Combinations)

서로 다른 n개의 원소에서 r개를 뽑는 경우의 수

조합 구현

def combination(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
                chosen.append(arr[nxt])
                used[nxt] = 1
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])

순열, 조합 파이썬 라이브러리

itertools

import itertools
pool = ['A','B','C']
print(list(map("".join, itertools.permutaions(pool, 2)))) # 순열
print(list(map("".join, itertools.combinations(pool, 2)))) # 조합

참고

BOJ_2798 블랙잭 -Python3

문제분석

1. 관찰
- N장의 카드 중에서 3장의 카드를 골라 M과 최대한 가까운 수를 만든다.
- 주어진 카드에서 3장을 뽑을 수 있는 모든 조합을 탐색한다.

2. 복잡도
- O(nC3) = 100! / (3!*97!) = (100*99*98)/(3*2*1) >> 가능

3. 자료구조
- 카드 = int[]

해결코드 1

from itertools import combinations
import sys
si = sys.stdin.readline

N, M = map(int, si().split())
cards = list(map(int, si().split()))


picked = []

ans = 0

for picked in combinations(cards, 3):
    sum_pick = sum(picked)
    if sum_pick <= M:
        ans = max(ans, sum_pick)

print(ans)

해결코드 2

import sys
si = sys.stdin.readline

N, M = map(int, si().split())
cards = list(map(int, si().split()))
ans = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            sum_c = cards[i]+cards[j]+cards[k]
            if sum_c <=M:
                ans = max(ans,sum_c)

print(ans)

 

'Etc > PS' 카테고리의 다른 글

BOJ_1436 영화감독 숌 -Python3  (0) 2022.08.05
BOJ_2231 분해합 -Python3  (0) 2022.08.05
BOJ_1065 한수 -Python3  (0) 2022.08.03
BOJ_20207 달력 -Python3  (0) 2022.08.03
BOJ_17836 공주님을 구해라! -Python3  (2) 2022.08.03

BOJ_1065 한수 -Python3

문제분석

1. 관찰
- 한수: x의 각 자리가 등차수열을 이루는 수
- 범위가 1000 미만의 수에 한정되어있으므로 세자리 수 까지 고려한다.
- 2자리 수 까지는 모두 한수
- 3자리 수는 값의 차이를 직접 비교하여 맞는 경우만 카운트한다.

2. 복잡도
- O(N) = 999 >> 가능

3. 자료구조
- 한수: int

해결코드

import sys
si = sys.stdin.readline

N = int(si())

num = 0
ans = 0
while num < N:
    num += 1
    if num < 100: # 2자리수 까지는 모두 한수
        ans+=1
    if 100 <= num: # 3자리 한수는 차이를 비교
        a,b,c = num//100, (num%100)//10, num%10

        if a-b == b-c:
            ans+=1

print(ans)

'Etc > PS' 카테고리의 다른 글

BOJ_2231 분해합 -Python3  (0) 2022.08.05
BOJ_2798 블랙잭 -Python3  (0) 2022.08.04
BOJ_20207 달력 -Python3  (0) 2022.08.03
BOJ_17836 공주님을 구해라! -Python3  (2) 2022.08.03
BOJ_15787 기차가 어둠을 헤치고 은하수를 -Python3  (0) 2022.08.02

BOJ_20207 달력 -Python3

문제분석

1. 관찰
- 우선 달력을 만들어준다.
- 일정이 겹치는 경우 행의 수를 +1
- 연속된 일정에서는 일정의 길이 +1로 카운트하며 행의 최대값을 구한다.
- 3의 값으로 직사각형의 크기를 구한다.

- 달력에서 row의 최대값과 col의 길이를 카운트 한 값을 곱해 박스값을 구한다.
!!주의. 끝이 0으로 끝나지 않는 경우가 있다. 이를 마지막에 더해주어야 한다.!!

2. 복잡도
- O(N*(E-S+1)+S) = 365*1000 ... >> 4만정도 가능

3. 자료구조
- 달력 int[]

해결코드

import sys 
si = sys.stdin.readline

N = int(si())
clndr = [0]*365

for _ in range(N):
    s, e = map(int, si().split())
    for i in range(s-1,e): # 겹치는 일정 높이 +1
        clndr[i] += 1

sum_area = 0
l, h = 0, 0

for i in clndr:
    h = max(h,i) 
    if i:
        l += 1
    else:
        sum_area += l*h
        l, h = 0, 0

sum_area += l*h # 끝이 0으로 끝나지 않는 경우

print(sum_area)

'Etc > PS' 카테고리의 다른 글

BOJ_2798 블랙잭 -Python3  (0) 2022.08.04
BOJ_1065 한수 -Python3  (0) 2022.08.03
BOJ_17836 공주님을 구해라! -Python3  (2) 2022.08.03
BOJ_15787 기차가 어둠을 헤치고 은하수를 -Python3  (0) 2022.08.02
BOJ_15649 N과 M (1) - Python3  (0) 2022.08.01

BOJ_17836 공주님을 구해라! -Python3

문제분석

1. 관찰
- bfs로 공주에게 도달하는 시간을 구한다.
- 그람까지 bfs + 벽을 무시하고 공주에게 도달하는 최단거리를 구한다.
- !! 그람을 발견하면 공주와의 거리는 사칙연산으로 구할 수 있다. 시간복잡도를 줄이자.
- 둘 중의 작은 값이 T보다 작으면 최소값 출력
- 구출하지 못하는 경우 fail

2. 복잡도
- O(N*M) = 100*100 >> 1만 가능

3. 자료구조
- 성 int[][]
- 방문여부 int[][]

해결코드

import sys
from collections import deque
si = sys.stdin.readline

N, M, T = map(int, si().split())
castle = [list(map(int, si().split())) for _ in range(N)]
check = [list(0 for _ in range(M)) for _ in range(N)]

q = deque()
q.append((0,0,0))
result = float('inf')
while q:
    x, y, t = q.popleft()
    if x == M-1 and y == N-1: # 공주위치 도착
        result = min(result, t)
        break
    if t+1>T: #시간초과
        break 
    for i,j in [(-1,0),(1,0),(0,-1),(0,1)]:
        nx, ny = x + i, y + j
        if 0 <= nx < M and 0 <= ny < N and not check[ny][nx]:
            if castle[ny][nx] ==1:
                continue
            elif castle[ny][nx]==0:
                check[ny][nx]=1
                q.append((nx,ny,t+1))
            else:    
                check[ny][nx]=1
                gramT = t + 1 + abs((N-1)-ny) + abs((M-1)-nx)
                if gramT<=T: 
                    result=gramT


if result>T: 
    print("Fail")
else:
    print(result)

'Etc > PS' 카테고리의 다른 글

BOJ_1065 한수 -Python3  (0) 2022.08.03
BOJ_20207 달력 -Python3  (0) 2022.08.03
BOJ_15787 기차가 어둠을 헤치고 은하수를 -Python3  (0) 2022.08.02
BOJ_15649 N과 M (1) - Python3  (0) 2022.08.01
BOJ_15686 치킨 배달 - Python3  (2) 2022.08.01

JPA 소개

현대 웹 애플리케이션에서 Oracle, MySQL, MSSQL 등의 RDB를 쓰지 않은 경우가 드물다. 따라서, 객체를 관계형 데이터베이스에서 관리하는 것이 중요하다.
하지만, 기존 iBatis, MyBatis 등의 SQL Mapper로 쿼리를 매핑하는 방식은 아래와 같은 문제점이 있었다.
관계형 데이터베이스는 SQL만 인식할 수 있기 때문에, 각 테이블마다 CRUD SQL을 매번 생성하다보면 SQL의 비중이 높아진다. 그에 따라 유지보수의 어려움이 있다.
또한, 관계형 데이터베이스와 객체지향 프로그래밍 언어의 패러다임이 서로 다름으로 인한 여러 문제가 발생한다. 상속, 1:N 등 다양한 객체 모델링을 데이터베이스로는 구현할 수 없다.
이러한 문제점을 해결하기 위해 JPA 가 등장하였다.

Spring Data JPA

JPA는 인터페이스로서 자바 표준명세서이다.
따라서, 인터페이스인 JPA를 사용하기 위해서는 구현체가 필요하다. 대표적으로 HIbernate, Eclipse Link 등이 있다.
하지만, Spring에서 JPA를 사용할 때 구현체들을 직접 다루지 않는다.
구현체들을 더 쉽게 사용하고자 추상화시킨 Spring Data JPA라는 모듈을 이용하여 JPA를 다룬다.

JPA <= Hibernate <= Spring Data JPA

 

Spring Data JPA 등장 이유

1. 구현체 교체의 용이성
Hibernate 외에 다른 구현체로 쉬게 교체하기 위하여 Spring Data JPA를 사용한다. 기술의 변화함에 따라 구현체를 교체해야할 때, Spring Data JPA 내부에서 구현체 매핑을 지원해 줌으로 쉽게 교체가 가능하다.
2. 저장소 교체의 용이성
Spring data JPA에서 DB의 의존성만 교체하면 쉽게 DB 교체가 가능하다. Spring Data 하위의 프로젝트들은 기본적인 CRUD 인테페이스(save(), findAll, finOne() 등)가 같이 때문에, 저장소가 교체되어도 기본적인 기능은 변경할 것이 없어 교체가 쉽다.

프로젝트에 Spring Data Jpa 적용하기

build.gradle에 spring-boot-starter-data-jpa, h2 의존성 등록

dependencies {
    implementation('org.springframework.boot:spring-boot-starter-web')
    implementation('org.projectlombok:lombok')
    implementation('org.springframework.boot:spring-boot-starter-web') // 추가
    implementation('org.h2database:h2') // 추가
    annotationProcessor('org.projectlombok:lombok') 
    testImplementation('org.springframework.boot:spring-boot-starter-test')
}

spring-boot-starter-data-jpa

- 스프링 부트용 Spring Data Jpa 추상화 라이브러리
- 스프링 부트 버전에 맞춰 자동으로 JPA 관련 라이브러리 버전을 관리

h2

- 인메모리 관계형 데이터베이스로 별도의 설치없이 프로젝트 의존성만으로 관리 가능
- 메모리에서 실행되기 때문에 애플리케이션을 재시작할 때마다 초기화된다는 점을 이용하여 테스트 용도로 많이 사용
- JPA의 테스트, 로컬 환경에서의 구동에 사용

DB 테이블과 매칭될 Entity 클래스 작성

기존에 MyBatis같은 쿼리 매퍼의 경우 dao 클래스에서 오로지 xml 쿼리의 결과만 담던일을 Entity 클래스에서 모두 해결

import lombok.Builder;
import lombok.Getter;
import lombok.NoArgsConstructor;

import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;

@Getter
@NoArgsConstructor
@Entity
public class Posts {

    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(length = 500, nullable = false)
    private String title;

    @Column(columnDefinition = "TEXT", nullable = false)
    private String content;

    private String author;

    @Builder
    public Posts(String title, String Contnet, String author) {
        this.title = title;
        this.content = content;
        this.author = author;
    }

}

@Entity

- 테이블과 링크될 클래스임을 나타낸다.
- 기본값으로 클래스와 카멜케이스 이름을 언더스코어 네이밍으로 테이블 이름을 매칭한다.
ex) SalesManager.java -> sales_manager table

@id

- 해당 테이블의 PK 필드를 나타낸다.

@GeneratedValue

- PK의 생성 규칙을 나타낸다.
- 스프링 부트 2.0에서는 GenerationType.IDENTITY 옵션을 추가해야만 auto_increment가 된다.
!! 웬만하면 Entity의 PK는 Long 타입의 Auto_increment를 추천!!

@Column

- 테이블의 칼럼을 나타내며 굳이 선언하지 않더라도 해당 클래스의 필드는 모두 칼럼이 된다.
- 기본값 외에 추가로 변경이 필요한 옵션이 있으면 사용한다.
ex) 문자열의 경우 VARCHAR(255)가 기본값인데, 사이즈를 500으로 늘리고 싶거나, 타입을 TEXT로 변경하고 싶은 경우 등에 사용

@NoArgsConstructor

- 기본 생성자 자동 추가
- public Post(){}와 같은 효과

@Getter

- 클래스 내 모든 필드의 Getter 메소드 자동 생성

@Builder

- 해당 클래스의 빌더 패턴 클래스를 생성
- 생성자 상단에 선언 시 생성자에 포함된 필드만 빌더에 포함

DB Layer 접근자 Repository 생성

ibatis나 MyBatis 등에서 Dao라고 불리는 DB Layer 접근자를 JPA에선 Repository라고 부르며 인터페이스로 생성한다.

import org.springframework.data.jpa.repository.JpaRepository;

public interface PostsRepository extends JpaRepository<Posts, Long> {
    
}

!!Entity 클래스와 기본 Entity Repository는 함께 위치해야 한다.!!
단순히 페이스를 생성 후, JpaRepository<Entity 클래스, PK 타입> 를 상속하면 기본적인 CRUD 메소드가 자동으로 생선된다.

위의 Entity 클래스와 기본 Repository는 도메인별로 함께 움직여야 하므로 동일한 도메인 패키지에서 함께 관리한다.

Spring Data JPA 테스트 코드 작성

import com.choee.service.springboot.domain.posts.Posts;
import com.choee.service.springboot.domain.posts.PostsRepository;
import org.junit.After;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;

@RunWith(SpringRunner.class)
@SpringBootTest
public class PostsRepositoryTest {

    @Autowired
    PostsRepository postsRepository;

    @After
    public void cleanup() {
        postsRepository.deleteAll();
    }

    @Test
    public void 게시글저장_불러오기() {
        //given
        String title = "테스트 게시글";
        String content = "테스트 본문";

        // 빌더를 활용한 빌드 패턴
        postsRepository.save(Posts.builder()
                .title(title)
                .content(content)
                .author("rhksh99@gmail.com")
                .build());

        //when
        List<Posts> postsList = postsRepository.findAll();

        //then
        Posts posts = postsList.get(0);
        assertThat(posts.getTitle()).isEqualTo(title);
        assertThat(posts.getAuthor()).isEqualTo(content);
    }
}

@After

- Junit에서 단위 테스트가 끝날 때마다 수행되는 메소드를 지정
- 보통은 배포 전 전체 테스트를 수핼할 때 테스트간 데이터 침범을 막기위해 사용된다.
- 여러 테스트가 동시에 수행되면 테스트용 데이터베이스인 H2에 데이터가 그대로 남아 있어 다음 테스트실행시 테스트가 실패할 수 있다. 따라서 위 코드에서는 cleanup()을 수행하도록 작성되었다.

@postRepository.save

- 테이블 posts에 insert/update 쿼리를 실행
- id 값이 있다면 update가, 있다면 insert 쿼리가 실행된다.

@postRepository.findAll

- 테이블 posts에 있는 모든 데이터를 조회해오는 메소드이다.

@SpringBootTest

- 별다른 설정 없이 H2 데이터베이스를 자동으로 실행해 준다.

 

실행된 쿼리 확인하는 법

스프링 부트에서는 application.properties, application.yml 등의 파일로 한 줄의 코드로 설정할 수 있도록 지원하고 이를 권장한다.
1. src/main/resources 하위에 application.properties 파일 생성 및 옵션 추가

spring.jpa.show-sql=true

2. 콘솔에서 쿼리 로그 확인

BOJ_15787 기차가 어둠을 헤치고 은하수를 -Python3

문제분석

1. 관찰
- 명령에 따라 기차 좌석을 조절해준다.
- 패스한 기차를 기록하여 이후 기차를 보낼지 판단한다.

2. 복잡도
- O(N+M) = 20만 >> 가능

3. 자료구조
- 명령 list[][]
- 패스한 기차 : list[]

해결코드

import sys
si = sys.stdin.readline

N, M = map(int, si().split())
m_list = list(list(map(int, si().split())) for _ in range(M))

train_list = [[0]*20 for _ in range(N)] # 처음기차에는 아무도 타지 않는다
pass_train = []

for m in m_list:
    m_num, i = m[0], m[1]-1
    t = train_list[i]

    if m_num ==1:
        x = m[2]-1
        if t[x] == 0:
            t[x] = 1

    elif m_num ==2:
        x = m[2]-1
        if t[x] == 1:
            t[x] = 0

    elif m_num ==3:
        t[:] = [0]+t[:-1]

    elif m_num ==4:
        t[:] = t[1:]+[0]

ans = 0
for i in range(N):
    if train_list[i] not in pass_train:
        pass_train.append(train_list[i])
        ans+=1

print(ans)

'Etc > PS' 카테고리의 다른 글

BOJ_20207 달력 -Python3  (0) 2022.08.03
BOJ_17836 공주님을 구해라! -Python3  (2) 2022.08.03
BOJ_15649 N과 M (1) - Python3  (0) 2022.08.01
BOJ_15686 치킨 배달 - Python3  (2) 2022.08.01
BOJ_16918 봄버맨 - Python3  (0) 2022.08.01

Array (배열)

정적배열 (Static Array)

  • 메모리상에서 연속적이다.
  • 메모리에 선언하는 시점에 각각의 인덱스가 어느 메모리에 할당되는지 정해진다.

동적배열 (Dynamic Array)

  • 원소가 추가, 삭제 됨에 따라 메모리가 늘어났다가 줄어들어야함으로 연속한 메모리에 들어있지 않다.
  • 다만, 내부적으로 O(1)의 시간 복잡도로 원소를 조회할 수 있다.

 

배열의 시간복잡도

삽입

  • [최악의 경우] 맨 앞에 새로운 값을 삽입하는 경우, 다른 값들을 모두 한칸씩 이동해야 하므로 -> O(N)
  • 맨 뒤에 새로운 값을 삽입하는 경우, 다른 값들의 이동이 존재하지 않으므로 -> O(1)

삭제

  • [최악의 경우] 맨 앞의 값을 삭제하는 경우, 다른 값들을 모두 한칸씩 이동해야 하므로. -> O(N)
  • 맨 뒤의 값을 삭제하는 경우, 다른 값들의 이동이 존재하지 않으므로 -> O(1)

탐색

  • 배열은 index 기반으로 이루어져 있기 때문에 다른 위치를 참조하여 바로 원하는 index의 원소를 구할 수 있다. -> O(1)

LinkedList (연결리스트)

  • 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조
  • 노드들로 구성되어 있다.
  • 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있다.
  • 첫 노드인 헤드(Head)로 부터 시작해, 포인터를 사용해 리스트를 순회할 수 있다.

Single Linked List (단일 연결리스트)

  • 포인터가 한 방향(다음 노드)을 가리키면 Single Linked List

Doubly Linked List

  • Single Linked List에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 된다.

Circular Linked List

  • Linked List의 마지막 노드인 테일(Tail)과 헤드(Head)를 이으면 Circular Linked List이다.

 

연결리스트의 시간복잡도

삽입

  • 새로운 노드를 만들어 포인터로 연결 하면 되므로 -> O(1)

삭제

  • 노드를 삭제하고 이전 이후 노드를 포인터로 연결 하면 되므로 -> O(1)

탐색

  • [최악의 경우] 맨 뒤의 원소를 조회하는 경우, 헤드에서부터 순차적으로 탐색을 하므로 -> O(N)
  • 맨 앞의 원소를 조회하는 경우, 바로 탐색가능 하므로 -> O(1)

장단점 비교 및 정리

배열은 인덱스로 O(1)로 조회에 효율적이지만, 연결리스트에 비해 삽입/삭제가 비효율 적인 부분이 있다.

연결리스트는 순차적으로 탐색해야 함으로 배열에 비해 조회에 비효율적이며, 노드를 통해 삽입/삭제 효율성이 좋다.

  배열 연결리스트
조회 O(1) O(N)
맨 앞에서 삽입/삭제 O(N) O(1)
맨 뒤에서 삽입/삭제 O(1) O(1) : 마지막 원소를 아는 경우
O(N) : 마지막 원소를 모르는 경우
중간에서 삽입/삭제 O(N) 탐색시간 + O(1)

 

'CS > DSA' 카테고리의 다른 글

[알고리즘]그래프 탐색 알고리즘 BFS/DFS  (0) 2022.07.04

BOJ_15649 N과 M (1) - Python3

문제 접근

1. 아이디어
- 백트래킹 재귀함수 안에서 for loop를 돌면서 숫자 선택 & 방문여부 확인
- 재귀함수에서 M개를 선택할 경우 print

2. 복잡도
- N! > 가능(8까지 가능)

3. 자료구조
- 결과값 저장 int[]
- 방문여부 체크 bool[]

해결 코드 1

import sys
input = sys.stdin.readline

N,M = map(int, input().split())
result = []
check = [False]*(N+1)

def recur(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N+1):
        if check[i] == False:
            check[i] = True # 방문
            result.append(i)
            recur(num+1)
            check[i] = False
            result.pop()

recur(0)

해결 코드 2

import sys
si = sys.stdin.readline

N, M = map(int, si().split())

s = []
def f():
    if len(s) == M:
        print(' '.join(map(str,s)))
        return

    for i in range(1,N+1):
        if i in s:
            continue
        s.append(i)
        f()
        s.pop()
f()

같은 풀이이지만 방문여부를 코드 2 처럼 판별하면 코드가 간결해진다.

BOJ_15686 치킨 배달 - Python3

문제 분석

1. 관찰
- 전체 치킨 집에서 중복없이 M 개의 치킨집을 선택하여 탐색
- combinations를 통해 m개 선택한 경우에 대하여 최소값의 합을 구한다.

2. 복잡도
- O(N*N) = 50*50 상수배 >> 가능

3. 자료구조
- 집, 치킨집: int[]
- 거리합 : int

해결 코드

import sys
si = sys.stdin.readline
from itertools import combinations

N, M = map(int, si().split())

h = [] # 집의 위치
c = [] # 치킨집의 위치

for i in range(N):
    tmp = list(map(int, si().split()))
    for j in range(N):
        if tmp[j] == 1:
            h.append([i,j])
        if tmp[j] == 2:
            c.append([i,j])


ans = float("inf")

for chicken in combinations(c, M):
    sum = 0
    for hou in h:
        sum += min([abs(hou[0]-chi[0])+abs(hou[1]-chi[1]) for chi in chicken])
    if ans>sum:
        ans = min(ans, sum)
print(ans)

BOJ_16918 봄버맨

문제 분석

1. 관찰
- 첫 번째 폭탄이 터진 형태와 두 번째 폭탄이 터진 형태가 3번째 부터 반복된다.
- 첫 폭탄 폭파 3,7,11...
- 둘째 폭탄 폭파 5,9,14...
... 코드 참고

2. 복잡도
- O(R*C) = 200*200*8 >> 가능

3. 자료 구조
- 폭탄 배열: int[][]

해결 코드

import sys
si = sys.stdin.readline

R, C, N = map(int, si().split())
board = [list(si().strip()) for _ in range(R)]


if N<=1: # 첫 1초동안은 인풋을 출력
    for li in board: print(''.join(li))
elif N%2 == 0: # 짝수번째는 폭탄이 모두 차 있는 형태
    for i in range(R): print('O'*C)
else: # 첫 폭탄이 터진 이후 3번째 부터 형태가 반복된다. 3,7,11 ... 과 5,9,13...

    bom_1 = [["O"]*C for _ in range(R)] # 첫 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if board[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_1[ny][nx] = '.'

    bom_2 = [["O"]*C for _ in range(R)] # 두 번째 폭탄 터짐
    for i in range(R):
        for j in range(C):
            if bom_1[i][j] == "O":
                for y, x in [(0, 0),(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ny, nx = y+i, x+j
                    if 0 <= ny < R and 0 <= nx < C:
                        bom_2[ny][nx] = '.'

    if N%4==3:
        for li in bom_1: print(''.join(li))
    if N%4==1:
        for li in bom_2: print(''.join(li))

'Etc > PS' 카테고리의 다른 글

BOJ_15649 N과 M (1) - Python3  (0) 2022.08.01
BOJ_15686 치킨 배달 - Python3  (2) 2022.08.01
BOJ_20115 에너지 드링크 - Python3  (2) 2022.08.01
BOJ_21314 민겸 수 - Python3  (0) 2022.08.01
BOJ_2667 단지번호붙이기 - Python3  (0) 2022.07.22

BOJ_20115 에너지 드링크

문제 분석

1. 관찰
- 최대로 만들 수 있는 에너지 드링크의 양은
- 직관적으로 가장 큰 값을 a로 선택하고 나머지 음료들의 절반을 다 더한 값과 같음을 알 수 있다.

2. 복잡도
- max() = O(N)
- sum() = O(N)
>> 100000 + 100000 >> 가능

3. 자료구조
- int

해결 코드

import sys
si = sys.stdin.readline

N = int(si())
drinks = list(map(int, si().split()))

M = max(drinks)
S = sum(drinks)

print(M+(S-M)/2)

'Etc > PS' 카테고리의 다른 글

BOJ_15686 치킨 배달 - Python3  (2) 2022.08.01
BOJ_16918 봄버맨 - Python3  (0) 2022.08.01
BOJ_21314 민겸 수 - Python3  (0) 2022.08.01
BOJ_2667 단지번호붙이기 - Python3  (0) 2022.07.22
BOJ_1012 유기농 배추 - Python3  (0) 2022.07.22

BOJ_21314 민겸 수

문제 분석

1. 관찰
- 연속된 M은 M의 개수(cnt) -1이 자리수이다 -> 1E(cnt-1)
- K가 있는 경우 -> 5E(cnt)
- K에서 끊어준다.

- M 묶음으로 끊어주면 최소값이 된다.
- M과 K를 묶음으로 해준 경우 최대값이 된다.
... 코드 참고


2. 복잡도
- O(N) = S의 길이 >> 가능

3. 자료구조
- 최대, 최소 : 문자열

해결 코드

import sys
si = sys.stdin.readline

S = si().strip()
MAX = "" 
MIN = ""
cnt_m = 0  # 연속된 m의 개수 count

for i in range(len(S)):
    if S[i] == 'M':
        cnt_m +=1
    elif S[i] == 'K':
        if cnt_m: # M이 연속된 경우
            MAX += str(5*(10**cnt_m)) # M, K 함께 5의 배수로
            MIN += str(10**cnt_m+5) # M은 1의 배수로, K는 5로 더해서 추가
        else: # K만 단독으로 있는 경우, K는 단독으로 있기 때문에 5로만 끊어서 추가한다.
            MAX += "5"
            MIN += "5"
        cnt_m = 0

if cnt_m: # 끝이 M으로 끝나는 경우
    MIN += str(10**(cnt_m-1))
    while cnt_m: # 최대값을 만들기 위해서는 M의 연속의 경우 1111로 만들어 주어야 함으로 loop
        MAX += "1"
        cnt_m -= 1

print(MAX)
print(MIN)

'Etc > PS' 카테고리의 다른 글

BOJ_16918 봄버맨 - Python3  (0) 2022.08.01
BOJ_20115 에너지 드링크 - Python3  (2) 2022.08.01
BOJ_2667 단지번호붙이기 - Python3  (0) 2022.07.22
BOJ_1012 유기농 배추 - Python3  (0) 2022.07.22
BOJ_1260 DFS와 BFS - Python3  (0) 2022.07.22

BOJ_2667 단지번호붙이기 - Python3

문제 접근

1. 아이디어
- dfs로 단지 방문
- 방문하며 단지 번호 붙이기
- dfs에서 가구수 카운팅

2. 복잡도
- O(V+E) : 5*25*25 >> 가능

3. 자료구조
- 지도: int[][]
- 방문기록: bool[][]

해결 코드

import sys
input = sys.stdin.readline

N = int(input())

map = [input().strip() for _ in range(N)]
visited = [[0]*N for _ in range(N)]

dx =[-1,1,0,0]
dy =[0,0,-1,1]

groupCnt = 0
houseCnt =[]

def dfs(y,x):
    visited[y][x] = 1
    houseCnt[groupCnt]+=1
    for i in range(4):
        ny,nx = y + dy[i], x + dx[i]
        if 0<= ny < N and 0<= nx < N:
            if map[ny][nx] == '1' and visited[ny][nx] == 0:
                dfs(ny,nx)

for j in range(N):
    for i in range(N):
        if map[j][i] == '1' and visited[j][i] == 0:
            houseCnt.append(0)
            dfs(j,i)
            groupCnt +=1

print(groupCnt)
houseCnt.sort()
for e in houseCnt:
    print(e)

'Etc > PS' 카테고리의 다른 글

BOJ_20115 에너지 드링크 - Python3  (2) 2022.08.01
BOJ_21314 민겸 수 - Python3  (0) 2022.08.01
BOJ_1012 유기농 배추 - Python3  (0) 2022.07.22
BOJ_1260 DFS와 BFS - Python3  (0) 2022.07.22
BOJ_2441 별 찍기 - 4 - Python3  (0) 2022.07.20

+ Recent posts