버러범의 개발이야기

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

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

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

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

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

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

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

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

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

연구소가 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

길이가 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

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

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

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

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

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

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

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

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

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

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

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

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

0번 노드는 루트이고 1번부터 n-1번까지 각 노드의 parent의 번호가 주어진다.

정수로 노드의 번호 a, b가 주어질때 a와 b사이의 촌수(거리)를 구하는 문제이다.

문제에 제시된 트리를 전위탐색하면서 노드를 방문할때마다 trip이라는 vector안에 넣는다. 이때 depth와 현재 노드의 최초 방문 순서를 저장한다.

trip을 활용하여 RMQ를 생성하고 a, b의 공통조상을 찾는데 활용한다.

a, b의 거리는 ( a의 depth - 공통조상의 depth ) + ( b의 depth - 공통조상의 depth) 이다.

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

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

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