Hyun's_Devlog

https://www.acmicpc.net/problem/1652

간단한 문자열 탐색 문제다. 문제를 이해하는 시간이 더 길었던 문제다.

풀이

문제에 대한 설명이 부실하다고 생각되지만, 내 문해력이 부족한 것이라고 생각해야겠다. 예제를 그림으로 설명하면 다음과 같다.

즉 두 칸 이상의 공간이 생기면 해당공간을 하나의 누울 자리로 취급하겠다는 이야기. 

주의해야 할 사항으로 자리는 벽과 짐으로 구분한다는 것을 잊지 말아야 한다.

입력되는 문자열을 기준으로 가로배열과 세로배열을 생성. 두 배열을 "X"문자열을 기준으로 split() 함수를 통해 빈 공간을 탐색하였다.

정답 코드

https://www.acmicpc.net/problem/15565

기본적인 투포인터 문제다.

풀이

head, tail 두 개의 인덱스를 담는 변수와 인형의 개수를 담는 변수를 통해 조건을 판별한다. 개수가 k이상이라면, head를 증가 k보다 작다면 tail을 증가한다. 각 조건마다 head와 tail인덱스에 1이 담겨있는지 확인하여 개수를 갱신한다. 

개수가 k보다 적고, tail이 이미 n이라면, 더 이상 k개의 인형이 없다는 뜻이므로 반복문을 종료한다.

전체를 탐색했는데도 k개의 인형이 없다면 -1을 출력해야 한다는 조건도 까먹지 말자.

정답 코드

https://www.acmicpc.net/problem/1337

투 포인터로 접근한 문제다.

풀이

기준이 될 인덱스 i는 1부터 n까지, 비교할 인덱스 k는 i+1부터 i+4까지 반복문을 수행. 둘의 차이가 5보다 작다면 올바른 배열로 판정한다.

기준 인덱스 i가 바뀔 때마다 최댓값을 갱신한 뒤, 반복문이 끝나고 나면 값을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/10025

투 포인터, 슬라이딩 윈도우로 접근한 문제다.

풀이

투 포인터를 사용하여 곰이 얼음에 닿을 수 있는 최대거리 (2*k+1) 범위의 얼음합을 좌표값 0부터 1000,000까지 탐색을 하면 된다. 단 k의 크기가 500,000을 넘는다면 모든 좌표에 있는 얼음을 가져올 수 있으므로, 입력을 받으면서 얼음의 최댓값을 미리 계산하여 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14246

투포인터 문제다. 간단한 문제라고 생각하고서 접근했지만, 약간의 시간이 걸린 문제다.

풀이

head와 tail 두 개의 변수에 구간 합의 시작 인덱스와 끝 인덱스를 할당. 처음에는 둘 다 0으로 시작한다. 주어지는 수는 무조건 자연수다. 그 이야기는 해당 구간의 합이 k보다 크다면, 그 이후의 구간은 모두 조건을 만족한다는 뜻이다. 조건이 맞는다면 tail에 해당하는 인덱스부터 n까지의 개수를 모두 더해준 뒤, head 인덱스를 증가하여 다시 조건을 탐색. 이런 방법으로 구간을 탐색한다.

만일 sum이 k보다 작고, tail이 더 이상 증가할 수 없는 상황이라면, 반복문을 종료하면 된다.  

정답 코드

https://www.acmicpc.net/problem/2018

기초적인 투포인터 문제다.

풀이

1부터 N까지의 수를 오름차순으로 담은 배열을 생성한 뒤, 인덱스를 활용한 구간탐색을 통해 답을 구하면 된다. 시작 인덱스와 끝인덱스는 동일하게 0으로 시작한 뒤, 아래와 같은 조건으로 반복을 수행한다.

• 누적합이 목표 숫자보다 크다면 시작 인덱스가 가리키는 숫자를 뺀 뒤 시작 인덱스 증가
• 누적합이 목표 숫자보다 작거나 같다면 끝 인덱스가 가리키는 숫자를 더 해준 뒤 끝 인덱스 증가
• 누적합이 목표숫자와 같다면 카운트 증가
• 끝 인덱스가 증가할 부분이 없다면 종료

정답코드

https://www.acmicpc.net/problem/1504

다익스트라 알고리즘 문제. 마찬가지로 Rhyno님이 작성한 힙을 사용했다.

풀이

1번에서 n번 정점까지의 최단경로, 하지만 반드시 두지점을 거쳐야 한다는 조건이 붙었다.

[1 -> v1 -> v2 -> n ] 또는 [1 -> v2 -> v1 -> n] 두 가지 최단 경로중 가중치가 더 적은 경로를 반환하면 된다. 1번 정점에서 각 정점으로 향하는 최단경로, v1 정점에서 각 정점으로 향하는 최단경로, v2 정점에서 각 정점으로 향하는 최단경로 총 다익스트라 3번을 돌린 뒤 각 가중치를 적절히 조합해서 반환하면 된다.

하지만 여기서 경로가 없는 조건에 대해 처리해주어야 하므로 이 부분만 신경 써준다면 정답을 받을 수 있다. 본인의 경우 최단경로를 담은 배열을 -1로 초기화한뒤 다익스트라를 통해 갱신하였는데, 아무리 조건을 신경 써서 제출해도 오답판정을 받아 결국 계산 가능한 가중치의 최댓값인 2억으로 초기화하며 예외처리하였다.

정답 코드

https://www.acmicpc.net/problem/1238

다익스트라 알고리즘으로 접근한 문제다. 힙 구현이 필요하다. 직접 구현할 역량이 안되기에, Rhyno님이 작성한 힙을 사용하였다.

풀이

간선과 가중치를 입력받은 map 배열을 통해, 다익스트라 알고리즘을 사용한다. 양방향 간선이 아닌 단방향 간선이기에 우선 파티 장소 x에서 각 마을로 되돌아가는 배열을 생성, 다익스트라 알고리즘을 통해 각 인덱스에 저장. 이후 1 ~ n번 마을에서 x로 향하는 최단거리를 한 번 더 다익스트라 알고리즘을 통해 방금 저장한 배열에 추가시켜 준다. 마지막으로 배열에 담긴 최댓값을 출력한다.

정답 코드