여가생활 개발일지

[C++] 백준 2504번 괄호의 값 (정규 표현식)

백준 2504번 괄호의 값 문제 바로가기 ※ 주의사항 이 문제의 대표적인 풀이는 스택입니다. 하지만 필자는 정규표현식 연습을 위해서 다른 방법으로 풀었습니다. 스택 풀이는 다른 블로그에서 보셔야 해요! 이 방법은 이렇게도 풀 수 있구나 하고 넘어가시면 됩니다 사용 알고리즘 정규 표현식 풀이 문제의 5가지 문자를 구분할 정규표현식 만든다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다. (), []와 같이 사이에 아무것도 없이 붙어 있는 괄호를 바로 숫자로 치환해 준다. regex_repl..

[C++] 백준 13549번 숨바꼭질3 (DP, 다익스트라)

백준 13549번 숨바꼭질3 문제 바로가기 알고리즘 분류 DP 다익스트라 풀이 점화식은 위치가 짝수일 때와 홀수일 때로 나뉜다. 짝수일 때 1칸 이전 값 (가중치 1) 절반 위치 (가중치 0) 홀수일 때 1칸 이전 값 (가중치 1) 1칸 앞(짝수)의 절반 위치(가중치 1) 하지만 홀수의 점화식에 의문이 들 수가 있다. 왜 1칸 앞의 절반만 고려할까? 문제에서는 앞이나 뒤로 1칸씩 이동할 수 있다고 했는데? 2로 나눈 값이 올림 또는 내림이 될 수 있는 거 아니야? 왜 "1칸 뒤(짝수)의 절반 위치"는 고려하지 않을까? 결론부터 말하자면 점화식에 1칸 뒤 절반 위치를 넣어도 결과는 동일하다. 하지만 의미 없는 연산이다. 이유는 "1칸 이전 값"과 중복되기 때문이다. 예를 들어 현재 위치가 9라고 가정해 보..

[C++] 백준 2615번 오목 (구현)

백준 2615번 오목 문제 바로가기 알고리즘 분류 구현 풀이 방향 설정하기 8방향 모두 검사할 필요 없이, 우(→), 하(↓), 상우(↗), 하우(↘) 4방향만 검사하면 된다. 중복되는 방향 제거 가로 방향을 예시로 왼쪽으로 훑기(←), 오른쪽으로(→) 훑기 당연히 2가지다. 첫 번째 돌부터 오른쪽으로 훑기 = 마지막 돌부터 왼쪽으로 훑기 방향의 우선순위 문제에서는 우선순위가 왼쪽 다음 위쪽이라고 정해졌다. 상우(↗) 대신에 하좌(↙)를 검사한다면 위쪽을 먼저 우선순위로 두게 된다(화살표 말고 시작점을 보자) 오목 검사를 시작 좌표 고르기 검은 바둑돌 또는 흰 바둑돌 이어야 한다. 인접한 같은 색깔의 돌이 우(→), 하(↓), 상우(↗), 하우(↘) 4방향 중에 있어야 한다. 인접한 같은 색깔의 돌이 좌..