[2023 알고리즘 스터디] 5조 #1주차 - 구현, 브루트포스, 스트링

FOSCAR 알고리즘 스터디 1주차 5조 블로깅

 

괄호 추가하기 - 코드 리뷰 박병규

• 문제 링크

16637번: 괄호 추가하기

• 풀이

괄호로 만들 수 있는 모든 경우의 수를 따짐

dfs탐색을 재귀로 호출함

묶고 넘기기, 안 묶고 넘기기 2개에 대해 dfs를 호출함

 

• 안묶는 경우

1+2+3+4

• 묶는 경우

1+(2+3)+4 → 이 경우 idx가 4를 가리킬 때 묶을 수 없음

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <bitset>
#include <set>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

// 변수 선언
int n;
string s;
int ans = -987654321;

//계산하는 함수
int cal(char oper, int a, int b){
    //cout << oper << endl;
	  int ret = 0;
    if(oper == '+')
        ret = a+b;
    else if(oper == '*')
        ret = a*b;
    else if(oper == '-')
        ret = a-b;
    return ret;
}

// dfs
void solve(int idx, int val){
    //cout << idx << " " << val << endl;
    // 탈출조건
    if(idx >= n){
        ans = max(ans, val);
        return;
    }
    char oper;
    if(idx == 0) oper = '+';
    else {
        oper = s[idx-1];
    }
	  // 괄호를 묶을 수 있는 조건
    if(idx + 2 < n){
        int k = cal(s[idx+1], s[idx]-'0', s[idx+2]-'0'); // 괄호 묶은거 연산
        solve(idx+4, cal(oper, val, k));
    }
    // 괄호를 안 묶는 조건
    solve(idx+2, cal(oper, val, s[idx]-'0'));
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    cin >> s;
    
    solve(0,0);
    
    cout << ans;
    
    return 0;
}

 

잠수함 식별 - 코드 리뷰 이승찬

• 문제링크

2671번: 잠수함식별

• plan

연산 기호들과 같이 사용할 수 있는 조합 여러개 제시 → 특정 조건에 부합하는 지 확인’ 이러한 과정을 통해 각각의 연산을 정의하고 여러개의 조합법을 통해 검토하는 문제인 줄 알았지만 너무 노가다라 알고리즘 분류를 확인해 봄. 정규표현식을 ****처음 접해보아 정리하여 풀어봄.

 

메타 문자

"[ ] 사이의 문자들과 매치"

• [a-zA-Z] : 알파벳 모두
• [0-9] : 숫자

문자 클래스 안에 ^ 메타 문자를 사용할 경우에는 반대(not)라는 의미를 갖는다

 

자주 사용하는 문자 클래스

[0-9] 또는 [a-zA-Z] 등은 무척 자주 사용하는 정규 표현식이다. 이렇게 자주 사용하는 정규식은 별도의 표기법으로 표현할 수 있다. 다음을 기억해 두자.

• \\d - 숫자와 매치, [0-9]와 동일한 표현식이다.

• \\D - 숫자가 아닌 것과 매치, [^0-9]와 동일한 표현식이다.

• \\s - whitespace 문자와 매치, [ \\t\\n\\r\\f\\v]와 동일한 표현식이다. 맨 앞의 빈 칸은 공백문자(space)를 의미한다.

• \\S - whitespace 문자가 아닌 것과 매치, [^ \\t\\n\\r\\f\\v]와 동일한 표현식이다.

• \\w - 문자+숫자(alphanumeric)와 매치, [a-zA-Z0-9_]와 동일한 표현식이다.

• \\W - 문자+숫자(alphanumeric)가 아닌 문자와 매치, [^a-zA-Z0-9_]와 동일한 표현식이다. 대문자로 사용된 것은 소문자의 반대임을 추측할 수 있다.

 

Dot

줄바꿈 문자인 \\n 을 제외한 모든 문자와 매치됨

‘a.b’ == ‘a + 모든문자 + b’

즉 a와 b라는 문자 사이에 어떤 문자가 들어가도 모두 매치된다는 의미

 

‘a[.]b’ == ‘a + Dot(.)문자 + b’ 따라서 정규식 a[.]b는 "a.b" 문자열과 매치되고, "a0b" 문자열과는 매치되지 않는다. 만약 앞에서 살펴본 문자 클래스([]) 내에 Dot(.) 메타 문자가 사용된다면 이것은 "모든 문자"라는 의미가 아닌 문자 . 그대로를 의미한다. 혼동하지 않도록 주의하자.

 

반복 ()*

*은 * 바로 앞에 있는 문자 a가 0부터 무한대로 반복될 수 있다는 의미이다.

반복 (+)

+ 는 최소 1번 이상 반복될 때 사용한다. 즉 * 가 반복 횟수 0부터라면 +는 반복 횟수 1부터인 것이다.

반복 ({m,n}, ?)

{ } 메타 문자를 사용하면 반복 횟수를 고정할 수 있다. {m, n} 정규식을 사용하면 반복 횟수가 m부터 n까지 매치할 수 있다. 또한 m 또는 n을 생략할 수도 있다. 만약 {3,}처럼 사용하면 반복 횟수가 3 이상인 경우이고 {,3}처럼 사용하면 반복 횟수가 3 이하를 의미한다. 생략된 m은 0과 동일하며, 생략된 n은 무한대(2억 개 미만)의 의미를 갖는다.

? 메타문자가 의미하는 것은 {0, 1} 이다.

정규식을 이용한 문자열 검색

match()

문자열의 처음부터 정규식과 매치되는지 조사한다.

>>> import re
>>> p = re.compile('[a-z]+')

>>> m = p.match("python")
>>> print(m)
<re.Match object; span=(0, 6), match='python'>

>>> m = p.match("3 python")
>>> print(m)
None

search()

문자열 전체를 검색하여 정규식과 매치되는지 조사한다.

search 메서드를 수행하면 match 메서드를 수행했을 때와 동일하게 매치된다.

>>> m = p.search("3 python")
>>> print(m)
<re.Match object; span=(2, 8), match='python'>

"3 python" 문자열의 첫 번째 문자는 "3"이지만 search는 문자열의 처음부터 검색하는 것이 아니라 문자열 전체를 검색하기 때문에 "3 " 이후의 "python" 문자열과 매치된다.

Solve

(100~1~|01)~ → (100+1+|01)+

match VS fullmatch

match는 target이 해당 패턴으로 시작하는지를 검사 → 그렇다면 Match object 반환

패턴과 일치하는 접두사가 있는지를 판단하려면 match를, 문자열 전체가 패턴과 일치하느냐를 검사하려면 fullmatch를 사용

import re

target = input() #정규표현식은 int가 아니라 str으로 대체시키므로 인풋 형태 조심
stand = re.compile('(100+1+|01)+') #기준(100~1~|01)~
answer = stand.fullmatch(target) #match fullmatch 차이 확인

if answer:
    print("SUBMARINE")
else:
    print("NOISE")

 

치킨 배달 - 코드 리뷰 이진호

• 문제 링크

15686번: 치킨 배달

• 풀이
  1. 입력을 받고 치킨집과 집에 대한 정보를 각각의 list에 넣어준다.
  2. python의 itertools의 combinations를 사용하여 치킨집을 선택할 수 있는 모든 조합의 수에 대해 거리의 합을 구하고 이때 가장 거리가 짧은 것을 구한다.

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

n, m = map(int, input().rstrip().split())
graph = list(list(map(int, input().rstrip().split())) for _ in range(n))
house_coords = []
chicken_coords = []

def parseCoord():
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                house_coords.append( [i, j] )
            elif graph[i][j] == 2:
                chicken_coords.append( [i, j] )

def calcDist(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)

def solve():
    answer = 10 ** 9
    for comb in combinations(chicken_coords, m):
        comb_total_dist = 0
        for house_coord in house_coords:
            dist = 999
            r1, c1 = house_coord[0], house_coord[1]
            for chicken_coord in comb:
                r2, c2 = chicken_coord[0], chicken_coord[1]
                calc_dist = calcDist(r1, c1, r2, c2)
                if calc_dist < dist:
                    dist = calc_dist
            comb_total_dist += dist
            if comb_total_dist > answer:
                break
        if comb_total_dist < answer:
            answer = comb_total_dist
    print(answer)

if __name__ == '__main__':
    parseCoord()
    solve()

 

로봇 청소기 - 코드 리뷰 박준석

• 문제 링크

14503번: 로봇 청소기

• 풀이

1. 현재 위치를 청소한다
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2.  왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3.  네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

// 세로크기: N, 가로 크기 M
// 로봇청소기가 있는 칸의 좌표 (r, c)
// 바라보는 방향 d
int N, M, r, c, d;
int visited_cnt = 0;
int map[51][51]; // 지도
int visited[51][51]; // 청소기 경로, 방문했으면 1

// 북, 동, 남, 서
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

//모든 노드를 방문하고자 하는 경우이기에 dfs알고리즘 사용
void Dfs(int r, int c, int d, int visted_cnt) {
	// 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. - d = 0(위), 1(오른쪽), 2(아래), 3(왼쪽)
	for (int i = 0; i < 4; i++) { 
		int next_d = (d + 3 - i) % 4;
		int next_r = r + dx[next_d];
		int next_c = c + dy[next_d];

		//b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
		if (next_r < 0 || next_r >= N || next_c < 0 || next_c >= M || map[next_r][next_c] == 1) {
			continue;
		}

		//a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
		if (visited[next_r][next_c] == 0 && map[next_r][next_c] == 0) {
			visited[next_r][next_c] = 1; //현재 위치 청소
			r = next_r;
			c = next_c;
			d = next_d;
			visited_cnt++;
			Dfs(next_r, next_c, d, visited_cnt);
		}
	}
	int back_dir = (d+2) % 4; //후진방향 0 -> 2, 1 ->3, 2 -> 0, 3 -> 0 
	int back_r = r + dx[back_dir];
	int back_c = c + dy[back_dir];
	//c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
	if (0 <= back_r && back_r <= N && 0 <= back_c && back_c <= M) {
		if (map[back_r][back_c] == 0) {   //뒤쪽 방햑 벽 아니어서 후진할 수 있을 때
			Dfs(back_r, back_c, d, visited_cnt);  //한칸 후진
		}
		//d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
		else {   //뒤쪽 방향 벽이라 후진 못할 때
			cout << visited_cnt << endl;
			exit(0);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//입력 부분
	cin >> N >> M;
	cin >> r >> c >> d;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	// 1. 현재 위치를 청소한다.
	visited[r][c] = 1;
	visited_cnt++;
	Dfs(r, c, d, visited_cnt);

	return 0;
}