컴퓨터공부하기

C++ STL의 stirng을 이용하면 쉽게 구현할 수 있다.

입력으로 주어진 문자열에서 몇번째에 하이픈을 넣을지도 주어진다.

몇번째에 몇개의 하이픈을 넣을지 개수를 계산한 다음

string의 뒤에서부터 하이픈을 넣으면, 앞쪽의 인덱스 위치는 그대로 이기때문에 원하는 위치에 하이픈을 넣을 수 있다.

탐색해야하는 경우가 많지않기때문에 완전탐색을 이용했다.

각 스위치를 누를때마다 시간이 3씩 증가한다. 즉, 스위치를 4번 누르면 해당 시계들이 다시 원래의 시간을 가지게 된다. 그러므로 각각의 스위치를 0, 1, 2, 3 번 누를때에 대하여 재귀적으로 호출했다.

dfs함수가 호출될 때 마다, 모든 시계가 12시를 가르키는지 체크한 후, 모든 시계가 12시를 가르키면 min값 갱신 후에 반환,

아닌 경우에는 그다음 스위치를 눌러본다. 

불가능할 때 -1을 처리하지 않아 처음에 틀렸는데, 문제를 꼼꼼하게 읽어야 하는 중요성을 다시 깨닿게 된다.

coverType는 책에 나와있는 부분을 이용하였다. 옛날 같으면 직접 하드코딩했지만, 확실히 좌표값을 움직일 때에는 미리 정의해놓고 사용하는 것이 반복문을 이용하기에 편리한 것 같다.

이 문제를 해결하기위해 DFS를 이용한 완전탐색을 이용하였으며, 중복을 최대한 줄이기 위해 전체 보드판에서 가장 위, 가장 왼쪽에 있는 빈 부분'.'의 좌표부터 탐색하기 시작한다.

빈 좌표에 대하여 4가지 블록을 놓을 수 있는지 확인한 후에, 다음 빈칸을 찾아 재귀적으로 호출하며, 다음 빈칸이 없는 경우에는 모든 블록이 덮어진 것이므로 카운트를 1 증가시킨다. 또, 이런 경우, 다른 모양의 블록은 해당 x,y 좌표에 넣을 수 없으므로 바로 리턴해준다.

이문제 또한 완전탐색으로 해결했다.

서로 친구인지 여부를 저장하는 friends배열이 있으며,

find배열은 짝을 결정지었는지를 저장하는 배열이다.

재귀함수의 기저 조건으로는 마지막 한쌍만 더 연결하면 될 때, 이 마지막 한쌍이 서로 친구를 만족하면 sum+1을 해주고 리턴, 친구사이가 아니면 그냥 리턴하게된다.

재귀 탐색을계속 해야하는 경우 ptr번째 친구는 자신보다 뒷번호 사람 중에서, 아직 짝을 찾지 않았고(find=0), ptr과 친구인 관계가 성립하면 서로 짝을 맺는다.

그 후, 아직 짝을 찾지 않은 멤버를 찾아 재귀적으로 호출하여 짝을 찾아준다.

알고리즘 문제해결 전략 06챕터 무식하게 풀기에 있는 문제이다.

앞쪽에 DFS 로 완전탐색에 대해 설명이 나와있고, 예제 문제로 나와있어서 처음엔 DFS로 완전탐색하도록 구현했다.

당연히! 시간초과가 나왔다. 결과를 보고 문제를 다시보니  문제에 6장에 나온대로 해결하면 너무 느리다고 설명되어있다. 역시 문제를 제대로 읽고 풀어야 했다.

특히 다음과 같이

AAAAA

AAAAA

AAAAA

AAAAA

AAAAH

이런 예제에서 AAAAAAAAAH 이런 문자열을 찾으려면 한참 걸릴 것이다.

그래서 처음 시간초과 났던 코드에 방문 여부를 확인하는 배열을 하나 추가하였다.

dp[6][6][11]로 각각의 차원을 i,j,k로 본다면 (i,j) 좌표를 k번째 문자와 비교하기위해 방문을 했었는지 기록한다.

이전에 방문한 기록이 있다면, 이미 불가능한 길이므로 바로 반환한다.

방문하지 않았었다면, 다음 문자를 비교해본다.

이런 방식으로 불필요한 탐색을 줄였더니 0ms 가 나왔으며, 가장 빠른 답안의 1페이지에 내 아이디가 뜬다! 

Bitset

레퍼런스

비트를 다루는 STL

#include <bitset> 을 이용

bitset<비트개수> 변수명

bitset<비트개수> 변수명(초기값) 으로 bitset 선언. 초기값으로는 int, float, double, string 가능하다.

ex)

비트셋은 배열처럼 인덱스로 접근 가능 (위 비트셋 100에서  b[0] = 0, b[1] = 0, b[2] = 1)

멤버함수

test(인덱스): 인덱스의 비트가 1이면 true, 0이면 false 반환

set(): 전체 비트를 1로 설정

set(인덱스): 해당 인덱스의 비트를 1로 설정

set(인덱스, 비트): 해당 인덱스의 비트를 지정한 비트로 설정

reset(): 전체 비트를 0으로 설정

reset(인덱스): 해당 인덱스의 비트를 0으로 설정

flip(): 전체 비트를 반전( 0은 1로, 1은 0으로)

flip(인덱스): 해당 인덱스의 비트를 반전

all(): 모든 비트가 1인지 검사

any(): 비트 중 1이 1개 이상 있는지 검사

none(): 모든 비트가 0인지 검사

count(): 비트 중 1의 개수 

size(): 비트셋의 크기 반환

(size() - count() : 비트 중 0의 개수)

to_string(): 전체 비트를 string으로 변환

to_ulong(): 전체 비트를 unsigned long으로 변환

to_ullong(): 전체 비트를 unsigned long long으로 변환

선언 예제 코드

처음엔 DP로 해결 가능할거 같기도 했는데, 너무 오랬동안 DP를 안했더니 점화식이 잘 떠오르지 않아 DFS로 문제를 해결했다.

배열의 0~n-1번째 인덱스들을 이용한다.

color[i][j] 배열은 i번째 줄을 j색으로 바꾸는데 필요한 비용이다. j의 값으로 0=W, 1=B, 2=R 를 의미한다.

map에 현재 색 상태를 입력받으면 color 배열에 해당 i번째 줄을 다른색으로 바꾸는데 필요한 비용을 채워 놓는다.

그다음 dfs를 호출하여, 현재 색으로 색칠하거나 다음색으로 색칠할 때, 두가지 경우를 재귀적으로 호출한다.

dfs 종료 조건으로, 3가지 색이 모두 사용되어야 하며, 사용되지 않으면 바로 반환,

3가지 색이 모두 사용되었으면, 최솟값을 비교 후 반환한다.

이번주에 올라온 재미있는 오셀로 게임을 끝으로 SWEA에 올라온 유저 문제, 대회문제를 제외하고 D1~D3 문제는 다 풀었다.

물론 코드 배틀이 1주에 한번정도 꾸준히 있어서 계속 추가 되겠지만 어쨋든 다풀었다.

이제 D4를 정복할 차례다.

D1~D2는 주로 단순히 계산하면 해결할 수 있는 문제 들이었다.

D3는 왠만하면 풀리지만 간혹 시간을 절약해야 하는 경우가 있었다.

삼성 SW TEST의 B형을 통과하기 위해서는 최소 D4부터가 맞는 것 같다.

원래 나는 방향을 탐색해야하는 코딩할 때, 조건문에 직접 좌표값에 변화를 주었었다.

하지만 알고리즘 공부를 하며, 다른사람 코드를 보면 방향을 저장해 놓은 배열을 이용하는 것이 훨신 깔끔하고 좋아 보여서 여기서 연습했다.

오셀로 게임 규칙에 따라, 돌을 놓으면 색을 바꿔야하는지 8방향으로 탐색한다.