BOJ 문제 링크: https://www.acmicpc.net/problem/17829

 

17829번: 222-풀링

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22

www.acmicpc.net

222-풀링은 다음과 같은 작업을 말한다.

1. 행렬을 2*2 정사각형으로 나눈다.

2. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a a≤ a a1 라 했을 때, 원소 a2를 뜻한다.

3. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

222-풀링을 반복해서 크기를 1*1로 만들었을때 남아있는 값을 구하는 문제이다.

 

초기 배열을 기저사례(2*2크기)가 될때까지 4조각으로 쪼갠 뒤 4개의 조각중 3번째로 작은 값을 반환하는 식으로 문제를 해결할 수 있다.

 

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

연구소가 N*M크기 행렬로 주어진다. 연구소 각 칸의상태는 빈칸(0), 벽(1), 바이러스(2) 세가지 중 하나이다.

바이러스가 아직 퍼지지 않은 상태지만, 바이러스가 벽에 막히지 않는다면 상하좌우로 인접한 빈 칸에 퍼져 나갈 예정이다.

벽을 꼭 3개 세워서 바이러스가 퍼져나가는것을 막는다 했을때, 빈칸으로 남을 수 있는 안전영역 크기의 최댓값을 구하는 문제이다.

 

3개의 벽을 세우는 모든 경우를 구하고, 각 경우마다 바이러스가 퍼졌을때 0으로 남아있는 칸의 갯수를 구하는 식으로 문제를 풀 수있다.

벽을 세울때는 N*M개의 각 칸들을 일차원으로 풀어서 here로 표현한다.

현재영역(here)이 0이면 here에 벽을 설치하거나, 설치안하거나 두가지 경우를 계산하고 here이 0이 아니면 바로 다음칸(here+1)로 넘어간다.

안전영역의 넓이를 구할때는 bfs를 이용하는데 연구소상태(lab)를 훼손시키면 안되므로

visited라는 이차원 배열을 따로 두어서 바이러스가 이미 퍼진곳인지, 아직 퍼지지 않은 곳인지 표현한다.

 

 

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314502.cpp

 

GitHub - sbl133/BOJ

Contribute to sbl133/BOJ development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

jpa를 이해하는데 있어서 가장 중요한것 중 하나가 바로 영속성 컨텍스트이다.

영속성 컨텍스트에 대해 먼저 간단히 설명하자면 '엔티티를 영구 저장하는 환경' 이라는 뜻인데,

엔티티 메니저가 아래 코드와 같이 엔티티를 저장하거나 조회하면 영속성 컨텍스트는 엔티티를 보관/저장하여 관리하게 된다.

EntityManager.persist(entity);

영속성 컨텍스트에 대해 본격적으로 얘기하기 앞서 먼저 알아야 할것은 엔티티의 생명 주기이다. 

엔티티의 생명주기를 코드와 함께 보면 다음과 같다.

비영속 (new/transient) : 영속성 컨텍스트와 전혀 관계가 없는 새로운 상태

Member member = new Member();
member.setId("member1");
member.setUsername("회원1");

 

영속 (managed) : 영속성 컨텍스트에 관리되는 상태

Member member = new Member(); 
member.setId("member1"); 
member.setUsername(“회원1”);

EntityManager em = emf.createEntityManager();
em.getTransaction().begin();

//객체를 저장한 상태(영속)
em.persist(member);

 

준영속 (detached) : 영속성 컨텍스트에 저장되었다가 분리된 상태

// 객체를 저장(영속상태)
em.persist(member);

...

// 엔티티를 영속성 켄텍스트에서 분리(준영속 상태)
em.detach(member);

 

삭제 (removed) : 삭제된 상태

// 객체를 삭제한 상태
em.remove(member);

이제 엔티티의 생명주기가 어떤식으로 운영되는지, 또한 영속성 컨텍스트는 어떤식으로 동작하는지 얘기해보자.

맨 앞에서 영속성 컨텍스트란 엔티티객체를 관리해주는거라 간단히 말했는데 이렇게 영속성 컨텍스트를 이용하므로써 얻을 수 있는 이점은 다음과 같다.

  • 1차 캐시
  • 동일성(identity) 보장
  • 트랜잭션을 지원하는 쓰기 지연 (transactional write-behind)
  • 변경 감지(Dirty Checking)
  • 지연 로딩(Lazy Loading)

 

 

먼저 1차 캐시를 가짐으로써 db와의 통신을 줄일 수 있다.

처음 엔티티 객체를 생성하게 되면 비영속 상태이고, 엔티티 객체와 영속 컨텍스트는 아래 그림처럼 아무런 관계가 없다.

 

비영속 상태의 엔티티 객체를 엔티티매니저를 통해 저장(em.persist)하면 아래 그림처럼 영속 켄텍스트가 1차 캐시를 통해 엔티티객체를 저장/관리 한다.

이렇게 영속 컨텍스트에 의해 관리되는 영속상태의 엔티티객체를 조회(em.find)할 경우 아래 그림처럼 db를 통하지 않고 영속 켄텍스트의 1차캐시를 통해 객체 정보를 받아온다.

영속 컨텍스트로 관리되고 있지 않는 비영속 상태 엔티티객체를 조회할 경우에는 아래 그림과 같이 작동한다.

 

 

다음 이점인 동일성 보장이란 1차 캐시에 있는 엔티티를 참조함으로써 == 연산을 가능하게 해준다는 뜻이다.

Member a = em.find(Member.class, "member1"); 
Member b = em.find(Member.class, "member1");
System.out.println(a == b); // 동일성 비교 true

만약 1차캐시가 있는 영속 컨텍스트를 이용하지 않는다면 db에 직접 정보를 받아와 각각의 객체에 할당해야하기 때문에 동일한 정보라도 ==연산을 하면 false가 나올것이다.

 

다음 이점으로 트랜잭션을 지원하는 쓰기 지연이 있다.

영속 컨텍스트에는 1차 캐시 말고도 '쓰기 지연 SQL 저장소'라는게 있다. 트랜잭셕이 시작하고 나서 에티티 매니저가 요청하는 INSERT 쿼리들은 바로바로 db로 넘어가는 것이 아니라 쓰기 지연 SQL 저장소에 저장 된다.

EntityManager em = emf.createEntityManager();
EntityTransaction transaction = em.getTransaction();
//엔티티 매니저는 데이터 변경시 트랜잭션을 시작해야 한다.
transaction.begin(); // [트랜잭션] 시작
em.persist(memberA);
em.persist(memberB);
//여기까지 INSERT SQL을 데이터베이스에 보내지 않는다.
//커밋하는 순간 데이터베이스에 INSERT SQL을 보낸다.
transaction.commit(); // [트랜잭션] 커밋

저장된 INSERT SQL 들은 트랜잭셕이 커밋되는 시점에 flush되서 db로 한꺼번에 넘어가게 된다.

 

다음 이점은 엔티티 수정 변경 감지(Dirty Checking)가 있다.

영속 컨텍스트는 1차캐시에 스냅샷이란것을 유지해서 flush되는 시점에 현재 엔티티객체의 상태와 1차캐시의 스냅샷에 저장된 엔티티객체의 상태를 비교하고 다르다면 UPDATE SQL을 생성하여 쓰기 지연 SQL 저장소에 등록 했다가 기존에 쓰기 지연 SQL 저장소에 등록돼 있었던 쿼리들과 함께 한꺼번에 db에 전송한다.

 

영속성 컨텍스트로 얻을 수 있는 이점으로 지연로딩이 남았는데, 이는 프록시와 관련되 있어서 프록시를 주제로 다룰때 따로 설명할 예정이다.


참고로 영속성 컨텍스트를 플러시 하는 방법으로는 아래와 같은 경우들이 있다.

  • em.flush() - 직접 호출
  • 트랜잭션 커밋 - 플러시 자동 호출
  • JPQL 쿼리 실행 - 플러시 자동 호출

여기서 주의할 점은 플러시는 쓰기 지연 SQL 저장소에 있는 쿼리들을 db에 전송하는 것이지 영속성 컨텍스트를 비우는 것이 아니다.

영속성 컨텍스트를 완전히 초기화하기 위해서는 em.clear()라는 명령어가 쓰이고, 영속성 컨텍스트를 종료하기 위해서는 em.close()가 쓰인다.

 

참고: 자바 ORM 표준 JPA 프로그래밍 (https://www.inflearn.com/course/ORM-JPA-Basic#)

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/WORDCHAIN

 

algospot.com :: WORDCHAIN

단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이

www.algospot.com

입력된 단어들을 한번씩만 사용하여 끝말잇기를 한다.

모든 단어를 사용하여 게임이 끝날 수 있는 경우 어떤 순서로 단어를 사용해야 하는지 출력하는 문제이다.

만약 모든 단어를 사용하고 게임이 끝나느 경우가 없다면 IMPOSSIBLE를 출력한다.

 

알파벳 26개를 정점으로 하는 그래프에서 각 단어의 시작 알파벳을 나오는 방향, 끝나는 알파벳을 들어가는 방향으로 하는 간선을 추가한다.

그래프를 생성한 후에 오일러 서킷/트레일을 이용하여 각 간선의 방문순서를 기록한다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/WORDCHAIN.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/DICTIONARY

 

algospot.com :: DICTIONARY

고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된

www.algospot.com

새롭게 정의된 사전순으로 입력된 단어들을 통해 새로운 사전순의 알파벳 순서를 알아내는 문제이다.

 

dfs를 이용한 위상 정렬을 사용하면 문제를 풀 수 있다.

dfs를 사용하면 어차피 우선순위가 낮은 알파벳 먼저 order에 push되므로 들어오는 간선이 하나도 없는 정점들을 굳이 먼저 탐색하지 않아도 된다.

 

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

BOJ 문제 링크: https://www.acmicpc.net/problem/17830

 

17830번: 이진수씨의 하루 일과

이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은

www.acmicpc.net

길이가 N인 이진수 A, B가 있다. A는 모든 자리의 수가 1로만 채워져 있고, B는 각 자리에 0, 1, ? 셋중 하나가 올 수 있다. 

B의 ?를 0 또는 1로 적절히 변환시켜서 A와 B를 곱했을때 자릿수가 최대가 되는 경우의 자릿수, 자릿수가 최소가 되는 경우의 자릿수를 구하는 문제이다.

 

A와 B의 곱이 최대자릿수를 가지려면 가장 큰 값이 되어야 하고, 그러려면 B의 ?는 모두 1로 변환시켜야 한다.

마찬가지로 A와 B의 곱이 최소자릿수를 가지려면 가장 작은 값이 되어야 하고, 그러려면 B의 ?는 모두 0으로 변환시켜야  한다.

곱의 자릿수가 몇인지는 값이 범위가 너무커서 직접적인 계산으로는 알기 어렵다.

계산할 수 있는 방법으로는 A가 모두 1이므로 B의 최고자리수 미만의 자리에 1인 자리가 있으면 N+B의 자리수,

B의 최고자리수 미만의 자리에 1인 자리가 없으면 N + B의 자리수 - 1 임을 몇개의 예를 통하면 금방 알아차릴 수 있다.

예를 들어 N이 10인 경우 1111111111*0010000001 와 1111111111*0011111111의 자리수는 10 + 8 = 18이다.

하지만 1111111111*0010000000의 자리수는 17이다.

 

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2317830.cpp

 

GitHub - sbl133/BOJ

Contribute to sbl133/BOJ development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

알고스팟 문제 링크: https://algospot.com/judge/problem/read/EDITORWARS

 

algospot.com :: EDITORWARS

에디터 전쟁 문제 정보 문제 에디터 전쟁은 가장 유명한 자유 소프트웨어 텍스트 편집기인 vi와 Emacs 중 어느 쪽이 더 우월한가를 놓고 인터넷에서 자주 벌어지는 논쟁을 말합니다. 이 논쟁에 참

algospot.com

n개의 노드에 관한 m개의 관계가 주어진다.

만약 ack a b 라고 하면 a, b 가 같은 집합에 속해야 하고 만약 dis a b 라고 하면 a, b 가 서로 다른 집합에 속해야 한다.

이때 어떤 집합에 속할 수 있는 노드의 최대 갯수를 구하는 문제이다.

 

상호배타적집합을 사용하면 문제를 풀 수 있다.

한가지 주의할 점은 enemy라는 vector를 이용하여 적대관계(서로 다른 집하에 속해야만 하는)에 있는 집합의 루트 정보를 유지해야한다.

동지의 적은 적이므로 ack일때 merge할 상대와 적대관계에 있는 집합끼리 merge를 해야한다.

적의 적은 동지이므로 dis일때 dis인 상대의 적과 merge를 해야한다. 

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/25.%20disjointSet/EDITORWARS.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEASURETIME

 

algospot.com :: MEASURETIME

삽입 정렬 시간 재기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는

algospot.com

길이 N인 수열 A[]가 주어지고, A[]를 삽입정렬했을때 정렬 과정에서 숫자들을 총 몇 번이난 옮기는지 계산하는 문제이다.

 

일단 모든 노드의 값이 0인 팬윅트리를 생성한다. A[]의 요소를 왼쪽부터 탐색해서 각 값에 해당하는 팬윅트리 노드들의 값을 1씩 증가시킨다. 또한 자신보다 큰 값이 나왔던 횟수를 구하기 위해 전체 횟수 합에서 자신이하의 값이 나온 횟수합을 뺀다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MEASURETIME.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

+ Recent posts