방구석프로의 이야기

www.acmicpc.net/problem/14503

문제 해결을 위한 과정

이 문제의 경우 전형적인 구현 알고리즘입니다. 문제의 조건을 잘 따라가기만 한다면 그다지 큰 어려움 없이 해결할 수 있는 문제입니다. 먼저 문제에서 그래프의 정보와 시작 지점을 입력받습니다. 그 후 방향을 좌측으로 돌린 후 해당 지역이 청소가 필요한 지역이면 청소를 하고 지점을 옮겨줍니다. 벽인 경우는 방향을 다시 좌측으로 돌려줍니다. 이렇게 4번 돌리게 되면 해당 지역 주변에는 청소할 수 있는 지점이 없기 때문에 방향을 유지한 채로 뒤로 후진합니다. 이것은

nx = x - dx[direction], ny = y - dy[direction]으로 구현합니다.

만약 4방향 모두 청소할 수 없는 칸이여서 후진해야 하는데 후진해야 할 칸이 벽이어서 후진할 수 없는 경우 종료하고 청소했던 칸의 숫자를 출력합니다.(소스코드에 주석을 첨부합니다.)

소스코드

www.acmicpc.net/problem/10773

문제 해결을 위한 과정

이 문제의 경우 구현 파트에 속해있지만 문제가 다루는 내용은 사실상 자료구조 중 스택입니다. 스택의 경우 FILO 혹은 LIFO로 설명할 수 있습니다. 단순하게 숫자들을 입력받는데 만약 입력받은 숫자가 0이라면 뒤에서 pop 해주는 식으로 구현을 하면 쉽게 해결할 수 있습니다.

소스코드

www.acmicpc.net/problem/1475

문제 해결을 위한 과정

이 문제의 키 포인트는 9와 6이 서로 뒤집을 수 있다는 것입니다. 그 숫자들을 제외하고는 숫자의 개수만큼 세트의 개수가 증가하기 때문에 고려하기 쉽습니다. 따라서 0부터 9까지 0으로 초기화된 리스트를 선언하고 6, 9는 더 작은 인덱스 번째를 증가시켜주고 그 외의 숫자는 해당 인덱스의 값을 증가시켜주는 방법을 통하면 쉽게 계산할 수 있습니다.

35996가 입력으로 주어진다고 가정하면 3번째 인덱스 5번째 인덱스의 값을 각각 증가시킵니다. 이를 그림으로 표현하면 다음과 같습니다.

초기 상태

3번째와 5번째를 하나씩 증가시킨 후

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 인덱스를 증가시킴 편의상 낮은 인덱스를 증가시킴

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 9번째 인덱스를 증가시킴 

6이 왔으므로 6번째 인덱스와 9번째 인덱스 중 더 작은 값을 가지는 6번째 인덱스를 증가시킴

이렇게 각 인덱스를 증가시키는 과정이 끝난 후 리스트에서 최댓값을 출력하면 필요한 세트의 수가 나오는 것을 알 수 있다.

소스코드

www.acmicpc.net/problem/7568

문제 해결을 위한 과정

문제를 잘 살펴보면 자신보다 몸무게 그리고 키 모두 큰 사람의 수 + 1이 자신의 덩치 등수가 되는 것을 알 수 있습니다.

따라서 입력받은 몸무계와 키를 각각의 사람마다 묶어서 리스트에 저장해준 후 자신보다 몸무게 그리고 키가 모두 큰 사람의 수를 세는 것으로 쉽게 해결할 수 있습니다. 

문제 해결을 위한 팁

문제의 조건에서 데이터의 개수인 N이 50이하인것을 확인할 수 있습니다. 따라서 O(N^2)의 시간 복잡도를 가진 알고리즘을 적용해도 해결할 수 있습니다.

소스코드

www.acmicpc.net/problem/1966

문제 해결을 위한 과정

이 문제의 경우 큐를 이용하여 문제의 조건을 잘 작성해주면 정답을 받을 수 있는 문제였습니다.

파이썬에서 큐를 이용하기 위해서는 from collections import deque 코드의 윗부분에 첨가합니다.

먼저 입력받은 n개의 숫자들을 중요도와 묶어서 큐에 append 해줍니다. 그 후 큐를 조회하면서 뒤쪽에 더 높은 우선순위를 가진 작업이 존재할 경우 큐에서 popleft()를 해준 후 뒤쪽에 append 해줍니다. 반면 뒤쪽에 더 높은 우선순위를 가진 작업이 존재하지 않다면 바로 출력을 해줍니다. 이때 출력을 하기 전 popleft를 해준 후 popleft 된 작업의 번호와 입력받은 원래의 작업들 중에서 m번째 존재하는 값이 값다면 count를 출력해주고 값이 같지 않다면 count를 하나 증가시키는 것으로 해결합니다. 

소스코드

www.acmicpc.net/problem/1316

문제 해결을 위한 과정

이 문제의 경우 문제를 잘 보면 알 수 있는 점이 있습니다. abcd와 같이 뒤에 나오는 문자들이 전부 다 처음 나오는 문자이면 이는 그룹 단어로 인정하지만 abca같이 이미 나왔던 a가 뒤에 한번 더 나오는 경우는 그룹 단어로 인정하지 않는다는 것입니다. 따라서 먼저 알파벳의 개수인 26만큼의 0으로 초기화된 일차원 배열을 생성합니다. 그 후 단어들을 한 글자씩 조회를 합니다. 이 한 글자씩 조회된 문자를 아스키코드로 바꿔주어서 해당하는 배열의 인덱스 값이 0이면 1로 바꾸어 주고 이미 1로 되어있다면 즉 이미 앞에서 나왔던 단어인 경우 바로 break를 해줍니다. 

또한 abbbbbc와 같이 b가 여러개 있는 경우도 그룹 단어 이므로 위에서 말한 조건은 앞의 글자와 뒤의 글자가 다를 때만 적용해주는 걸로 쉽게 해결할 수 있습니다.

소스코드

www.acmicpc.net/problem/1152

문제 해결을 위한 과정

이 문제의 경우 단어와 단어 사이에 공백이 있다는 점을 이용하여 해결을 합니다. 문제의 예시를 보면

The Curious Case of Benjamin Button 공백이 5개가 있습니다. 공백은 단어 사이에 존재하기 때문에 단어는 6개입니다.

그러나 예시 중 시작이 공백으로 시작하는 것이 있습니다. 이를 염두에 두면 단어 뒤에 공백이 존재하는 경우 단어의 개수를 하나 증가시키는 방향으로 해결할 수 있다는 것을 알 수 있습니다.

문제 해결을 위한 팁

문제 해결을 위한 과정을 보면 단어 다음에 공백이 있다면 단어의 개수를 하나 증가시키는 것으로 해결할 수 있다는 것을 알 수 있습니다. 그러나 이렇게 하면 문자열의 가장 마지막 단어의 개수를 셀 수 없게 됩니다. 따라서 단어를 입력받은 후 그 뒤에 공백 문자를 붙여주면 이 문제점을 해결할 수 있습니다.

소스코드

www.acmicpc.net/problem/2739

문제 해결을 위한 과정

쉽게 해결할 수 있는 구구단 문제입니다. n을 입력받고 단순한 for문으로 해결할 수 있습니다.

소스코드