반응형

https://www.acmicpc.net/problem/1325

 

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한

www.acmicpc.net

1. 문제설명

입력으로 노드간의 단방향 연결관계가 주어진다.

입력으로 들어오는 노드는 최대 만개 이하, 간선 관계는 10만개 이하다.

 

처음 문제를 봤을 때 시간제한이 5초이고 노드가 최대 만개이므로

단순히 모든 노드에 대해 BFS를 돌릴 때 계산량을 생각해보면

10000*10000 = 1억 정도 되므로 2초정도 있으면 충분히 시간제한에 들어올 거라 생각했다.

 

그런데 정답률이 좀 낮은 걸 보고 이렇게 하면 틀릴까 곰곰히 생각을 해보다가

시간을 줄일수 있는 방법으로 DP를 생각했는데

DP를 사용하면 안된다! 이 문제는 DP를 적용할 수 없는 문제이다.

 

 

 

 


 

 

2. DP를 사용하면 안되는 이유

처음에 계산을 줄이는 방법으로

탐색한 노드에서 연결된 노드(신뢰관계에 놓여진 노드)의 수를 저장하는 방식으로

DP를 이용할 수 있지 않을까 생각했다.

 

이는 만약 그래프가 단방향 그래프라면 이용할 수 있다.

그림을 보면 쉽게 이해할 수 있다.

 

백준 1325 설명

위 그림과 같이 단방향 그래프인 경우 노드3번을 통해 노드 1번과 2번의 값을 구할 수 있는

DP 알고리즘을 이용하면 된다.

 

백주 1325 설명

 

하지만 이 문제에서는 단방향그래프라는 말이 없었기 때문에

빨간색 같은 간선이 존재할 수 있다.

 

이럴 경우 사이클이 생기기 때문에 DP를 이용한다면

3번 노드에서 값은  3이 나오는데 이때 3에는 1번 노드가 포함되어 있고,

또 1번 노드를 3번 노드 기반해서 값을 구하면 자기 자신을 포함한 채

실제정답은 3인데 4가 되버리는 현상이 나타난다.

 

그렇기 때문에 DP를 이용할 수 있는지 없는지

그래프의 특성을 잘 생각해봐야 올바르게 풀 수 있는 문제였다.

 

이렇게 그냥 무지성으로 DP를 푸는게 아니라

어떻게 풀어야할지 사고과정을 배울 수 있는 좋은 문제인 것 같다.

 

 


 

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
int mem[10001];
vector<int> adj[10001];

int BFS(int x){
    int ret = 0;
    bool vis[n+1];
    memset(vis,0, sizeof(vis));

    queue<int> Q;
    Q.push(x); vis[x] = 1;

    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        for(auto nx : adj[cur]){
            if(!vis[nx]){
                ret++;
                vis[nx]=1;
                Q.push(nx);
            }
        }
    }

    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;

        adj[b].push_back(a);
    }


    int ans = 0;
    for(int i=1; i<=n; i++){
        mem[i] = BFS(i);
        ans = max(ans, mem[i]);
    }

    for(int i=1; i<=n; i++){
        if(mem[i] == ans){
            cout << i << ' ';
        }
    }


    return 0;
}

백준 1325

 

반응형
반응형

JpaMemberRepository.class

package hello.hellospring.repository;

import hello.hellospring.domain.Member;

import javax.persistence.EntityManager;
import java.util.List;
import java.util.Optional;

public class JpaMemberRepository implements MemberRepository{

    private final EntityManager em;

    public JpaMemberRepository(EntityManager em){
        this.em = em;
    }

    @Override
    public Member save(Member member) {
        em.persist(member);
        return member;
    }

    @Override
    public Optional<Member> findById(Long id) {
        Member member = em.find(Member.class, id);
        return Optional.ofNullable(member);
    }

    @Override
    public Optional<Member> findByName(String name) {
        List<Member> result = em.createQuery("select m from Member m where m.name = :name", Member.class)
                .setParameter("name", name)
                .getResultList();

        return result.stream().findAny();
    }

    @Override
    public List<Member> findAll() {
        return em.createQuery("select m from Member m", Member.class).getResultList();
    }
}
반응형
반응형

우분투에 내장 마이크 외 블루투스 마이크 연결

https://atish3604.medium.com/solved-bluetooth-headset-mic-not-working-detected-in-ubuntu-20-04-86a5236444d0

 

[Solved] Bluetooth headset mic not working/detected in Ubuntu 20.04

This is the headset i used but the following article can help you solve the similar issue for other headsets too. Also, the solution should…

atish3604.medium.com

출처는 윗글과 같습니다.

 

저도 원리는 잘 모르는데

 

윈도우에서는 블루투스 이어폰으로 마이크도 잘 연결이 되었는데

우분투로 바꾸니까 이어폰으로 마이크 연결이 안되어서 불편해서 찾아보고

따라하니까 되었습니다.

 

위 링크 글에서 1번부터 11번 명령어를

터미널 창에 다 따라치면 마이크 input에 블루투스로 연결한 이어폰도 나타납니다.

 

근데 위에 명령어중에 --를 쳐야되는데 복사붙여넣기하면 --가 아니라 ㅡ 이렇게 들어가서 올바르게 되지않아서

간편하게 복붙 할 수 있도록 명령어를 써두겠습니다.

 

 

우분투 이어폰 마이크 INPUT 추가 명령어

1.
sudo add-apt-repository ppa:pipewire-debian/pipewire-upstream
2.
sudo apt update
3.
sudo apt install pipewire
4.
sudo apt install libspa-0.2-bluetooth
5.
sudo apt install pipewire-audio-client-libraries
6.
systemctl --user daemon-reload
7.
systemctl --user --now disable pulseaudio.service pulseaudio.socket
8.
systemctl --user --now enable pipewire pipewire-pulse
9.
systemctl --user mask pulseaudio
10.
systemctl --user --now enable pipewire-media-session.service
11.
pactl info
sudo add-apt-repository ppa:pipewire-debian/pipewire-upstream
sudo apt update
sudo apt install pipewire
sudo apt install libspa-0.2-bluetooth
sudo apt install pipewire-audio-client-libraries
systemctl --user daemon-reload
systemctl --user --now disable pulseaudio.service pulseaudio.socket
systemctl --user --now enable pipewire pipewire-pulse
systemctl --user mask pulseaudio
systemctl --user --now enable pipewire-media-session.service
pactl info

 

 

 

위에 명령어 다 쳤는데 안된다면 저도 잘 모르겠습니다..

 

반응형

'etc' 카테고리의 다른 글

PLSQL 커서, 프로시저  (0) 2022.12.28
git 로컬 브랜치 생성후 원격 브랜치 push하고 연동하기  (0) 2022.08.08
반응형

MemberController.class

package hello.hellospring.controller;

import hello.hellospring.domain.Member;
import hello.hellospring.service.MemberService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PostMapping;

@Controller
public class MemberController {

//    @Autowired private MemberService memberService;

    private MemberService memberService;

    @Autowired
    public MemberController(MemberService memberService) {
        this.memberService = memberService;
    }


    @GetMapping("members/new")
    public String createForm(){
        return "members/createMemberForm";
    }

    @PostMapping("/members/new")
    public String create(MemberForm form){
        Member member = new Member();
        member.setName(form.getName());

        System.out.println("member =" + member.getName());

        memberService.join(member);
        return "redirect:/";
    }
}

 

 

MemberForm.class

package hello.hellospring.controller;

public class MemberForm {
    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

 

반응형
반응형

MemberController.java

package hello.hellospring.controller;

import hello.hellospring.service.MemberService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;

@Controller
public class MemberController {

//    @Autowired private MemberService memberService;

    private MemberService memberService;

//    @Autowired
//    public void setMemberService(MemberService memberService){
//        this.memberService = memberService;
//    }
//



    @Autowired
    public MemberController(MemberService memberService) {
        this.memberService = memberService;
    }
}

memberController에서는 @Autowired를 이용하여 의존관계를 설정해주어야 한다.

 

SpringConfig

package hello.hellospring;

import hello.hellospring.repository.MemberRepository;
import hello.hellospring.repository.MemoryMemberRepository;
import hello.hellospring.service.MemberService;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class SpringConfig {

    @Bean
    public MemberService memberService(){
        return new MemberService(memberRepository());
    }

    @Bean
    public MemberRepository memberRepository(){
        return new MemoryMemberRepository();
    }
}
반응형

'Spring' 카테고리의 다른 글

[Spring] JPA  (0) 2022.07.02
[Spring] 회원 웹 기능 등록  (0) 2022.07.01
[Spring] Component Scan을 통한 의존관계 설정  (0) 2022.07.01
[Spring] 회원 서비스 테스트  (0) 2022.06.30
[Spring] 테스트 케이스 작성  (0) 2022.06.30
반응형

HelloSpringApplication.class

package hello.hellospring;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class HelloSpringApplication {

	public static void main(String[] args) {
		SpringApplication.run(HelloSpringApplication.class, args);
	}

}

 

controller.MemberController.class

package hello.hellospring.controller;

import hello.hellospring.service.MemberService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;

@Controller
public class MemberController {

    private final MemberService memberService;

    @Autowired
    public MemberController(MemberService memberService) {
        this.memberService = memberService;
    }
}

 

 

 

MemberService.class

 

package hello.hellospring.service;

import hello.hellospring.domain.Member;
import hello.hellospring.repository.MemberRepository;
import hello.hellospring.repository.MemoryMemberRepository;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

import java.util.List;
import java.util.Optional;

@Service
public class MemberService {

    private final MemberRepository  memberRepository;

    //MemberService입장에서 외부repository를 넣어줌 - > Dependency Injection!
    @Autowired
    public MemberService(MemberRepository memberRepository){
        this.memberRepository = memberRepository;
    }

    //회원가입

    public Long join(Member member){
        //같은 있는 중복 회원X
        validateDuplicateMember(member);

        memberRepository.save(member);
        return member.getId();
    }

    private void validateDuplicateMember(Member member) {
        memberRepository.findByName(member.getName())
                        .ifPresent(m -> {
                            throw new IllegalStateException("이미 존재하는 회원입니다.");
                        });
    }

    public List<Member> findMembers(){
        return memberRepository.findAll();
    }

    public Optional<Member> findOne(Long memberId){
        return memberRepository.findById(memberId);
    }


}

 

 

 

 

MemoryMemberRepository.class

package hello.hellospring.repository;
import hello.hellospring.domain.Member;
import org.springframework.stereotype.Repository;

import java.util.*;



@Repository
public class MemoryMemberRepository implements MemberRepository{
    private static Map<Long, Member> store = new HashMap<>();
    private static long sequence = 0L;

    @Override
    public Member save(Member member) {
        member.setId(++sequence);
        store.put(member.getId(), member);
        return member;
    }

    @Override
    public Optional<Member> findById(Long id) {
        return Optional.ofNullable(store.get(id));
    }

    @Override
    public Optional<Member> findByName(String name) {
        return store.values().stream()
                .filter(member-> member.getName().equals(name))
                .findAny();
    }

    @Override
    public List<Member> findAll() {
        return new ArrayList<>(store.values());
    }



    public void clearStore(){
        store.clear();
    }
}

 

 

@Component annotation을 통해

MemberController -> MemberService -> MemoryMemberRepository 순으로

의존관계를 주입하고 있다.

 

 

 

cf.

/*
 * Copyright 2002-2022 the original author or authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.springframework.stereotype;

import java.lang.annotation.Documented;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

import org.springframework.core.annotation.AliasFor;

/**
 * Indicates that an annotated class is a "Repository", originally defined by
 * Domain-Driven Design (Evans, 2003) as "a mechanism for encapsulating storage,
 * retrieval, and search behavior which emulates a collection of objects".
 *
 * <p>Teams implementing traditional Java EE patterns such as "Data Access Object"
 * may also apply this stereotype to DAO classes, though care should be taken to
 * understand the distinction between Data Access Object and DDD-style repositories
 * before doing so. This annotation is a general-purpose stereotype and individual teams
 * may narrow their semantics and use as appropriate.
 *
 * <p>A class thus annotated is eligible for Spring
 * {@link org.springframework.dao.DataAccessException DataAccessException} translation
 * when used in conjunction with a {@link
 * org.springframework.dao.annotation.PersistenceExceptionTranslationPostProcessor
 * PersistenceExceptionTranslationPostProcessor}. The annotated class is also clarified as
 * to its role in the overall application architecture for the purpose of tooling,
 * aspects, etc.
 *
 * <p>As of Spring 2.5, this annotation also serves as a specialization of
 * {@link Component @Component}, allowing for implementation classes to be autodetected
 * through classpath scanning.
 *
 * @author Rod Johnson
 * @author Juergen Hoeller
 * @since 2.0
 * @see Component
 * @see Service
 * @see org.springframework.dao.DataAccessException
 * @see org.springframework.dao.annotation.PersistenceExceptionTranslationPostProcessor
 */
@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Component
public @interface Repository {

	/**
	 * The value may indicate a suggestion for a logical component name,
	 * to be turned into a Spring bean in case of an autodetected component.
	 * @return the suggested component name, if any (or empty String otherwise)
	 */
	@AliasFor(annotation = Component.class)
	String value() default "";

}

 

@Controller, @Service, @Repository 내부에

@Component가 포함되어 있다.

반응형

'Spring' 카테고리의 다른 글

[Spring] JPA  (0) 2022.07.02
[Spring] 회원 웹 기능 등록  (0) 2022.07.01
[Spring] 자바코드로 직접 스프링 빈 등록하기  (0) 2022.07.01
[Spring] 회원 서비스 테스트  (0) 2022.06.30
[Spring] 테스트 케이스 작성  (0) 2022.06.30
반응형

MemberService.class

package hello.hellospring.service;

import hello.hellospring.domain.Member;
import hello.hellospring.repository.MemberRepository;
import hello.hellospring.repository.MemoryMemberRepository;

import java.util.List;
import java.util.Optional;

public class MemberService {

    private final MemberRepository  memberRepository;

    //MemberService입장에서 외부repository를 넣어줌 - > Dependency Injection!
    public MemberService(MemberRepository memberRepository){
        this.memberRepository = memberRepository;
    }

    //회원가입

    public Long join(Member member){
        //같은 있는 중복 회원X
        validateDuplicateMember(member);

        memberRepository.save(member);
        return member.getId();
    }

    private void validateDuplicateMember(Member member) {
        memberRepository.findByName(member.getName())
                        .ifPresent(m -> {
                            throw new IllegalStateException("이미 존재하는 회원입니다.");
                        });
    }

    public List<Member> findMembers(){
        return memberRepository.findAll();
    }

    public Optional<Member> findOne(Long memberId){
        return memberRepository.findById(memberId);
    }


}

 

Test

MemberServiceTest.class

매 테스트 마다

repository를 만들어주고 memberService에

넣어줘서 한 테스트에 각기 다른 객체를 이용할 수 있다.

 

그리고 AfterEach를 통해 각 테스트 후에 clear을 해주므로

static한 hashMap이 클리어되어 이후 새로운 MemeryMemberRepository를 생성해도

static한 hasjMap은 비어 있게 된다.

package hello.hellospring.service;

import hello.hellospring.domain.Member;
import hello.hellospring.repository.MemoryMemberRepository;
import hello.hellospring.repository.MemoryMemberRepositoryTest;
import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.junit.jupiter.api.Assertions.*;

class MemberServiceTest {

    MemberService memberService;
    MemoryMemberRepository memberRepository;

    @BeforeEach
    public void beforeEach(){
        memberRepository = new MemoryMemberRepository();
        memberService = new MemberService(memberRepository);
    }



    @AfterEach
    public void afterEach(){
        memberRepository.clearStore();
    }

    @Test
    void 회원가입() {
        //given
        Member member = new Member();
        member.setName("spring");

        //when
        Long saveId = memberService.join(member);

        //then
        Member findMember = memberService.findOne(saveId).get();
        assertThat(member.getName()).isEqualTo(findMember.getName());

    }

    @Test
    public void 중복_회원_예외(){
        //given
        Member member1 = new Member();
        member1.setName("spring");

        Member member2 = new Member();
        member2.setName("spring");

        //when
        memberService.join(member1);
        IllegalStateException e = assertThrows(IllegalStateException.class, () -> memberService.join(member2));

        assertThat(e.getMessage()).isEqualTo("이미 존재하는 회원입니다.");
//
//        try{
//            memberService.join(member2);
//            fail("예외가 발생해야 합니다");
//        } catch (IllegalStateException e){
//            assertThat(e.getMessage()).isEqualTo("이미 존재하는 회원입니다.");
//        }

        //then
    }


    @Test
    void findMembers() {
    }

    @Test
    void findOne() {
    }
}
반응형
반응형

MemberReposiotry.interface

package hello.hellospring.repository;

import hello.hellospring.domain.Member;

import java.util.List;
import java.util.Optional;

public interface MemberRepository {
    Member save(Member member);
    Optional<Member> findById(Long id);
    Optional<Member> findByName(String name);
    List<Member> findAll();
}

 

 

MemoryMemberRepository.class

package hello.hellospring.repository;
import hello.hellospring.domain.Member;
import java.util.*;

public class MemoryMemberRepository implements MemberRepository{
    private static Map<Long, Member> store = new HashMap<>();
    private static long sequence = 0L;

    @Override
    public Member save(Member member) {
        member.setId(++sequence);
        store.put(member.getId(), member);
        return member;
    }

    @Override
    public Optional<Member> findById(Long id) {
        return Optional.ofNullable(store.get(id));
    }

    @Override
    public Optional<Member> findByName(String name) {
        return store.values().stream()
                .filter(member-> member.getName().equals(name))
                .findAny();
    }

    @Override
    public List<Member> findAll() {
        return new ArrayList<>(store.values());
    }



    public void clearStore(){
        store.clear();
    }
}

 

 

 

/test/java/hello.hellospring/repository/MemoryMemberRepositoryTest.class

package hello.hellospring.repository;

import hello.hellospring.domain.Member;
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.Test;

import java.util.List;

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

public class MemoryMemberRepositoryTest {
    MemoryMemberRepository repository = new MemoryMemberRepository();


    //테스트는 의존 관계 없이 설계해야한다!
    @AfterEach
    public void afterEach(){
        repository.clearStore();
    }


    @Test
    public void save(){
        Member member = new Member();
        member.setName("spring");

        repository.save(member);

        Member result = repository.findById(member.getId()).get();
//        System.out.println("result = " + (result ==member));
        assertThat(member).isEqualTo(result);

    }

    @Test
    public void findByName(){
        Member member1 = new Member();
        member1.setName("spring1");
        repository.save(member1);

        Member member2 = new Member();
        member2.setName("spring2");
        repository.save(member2);

        Member result = repository.findByName("spring2").get();

        assertThat(result).isEqualTo(member2);


    }
    @Test
    public void findAll(){
        Member member1 = new Member();
        member1.setName("spring1");
        repository.save(member1);

        Member member2 = new Member();
        member2.setName("spring2");
        repository.save(member2);

        List<Member> result = repository.findAll();

        assertThat(result.size()).isEqualTo(2);

    }


}

 

 

반응형

+ Recent posts