7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net 불가능한 상황들을 나열하고 if문으로 하나씩 제거하기 특별히 다른 방법은 없는 것 같습니다. 꼼꼼하게 처리해주면 통과가 가능합니다. 이번엔 짜잘짜잘한 오타들이 많이 생기면서 디버깅에 시간이 좀 걸렸네요. 테스트 케이스를 여러가지 만들어서 시도해봐야했습니다. 코드 ''' Title : 틱택토 Link : https://www.acmicpc.net/problem/7682 Level : G5 Problem : 주어진 판이 가능한 틱택토 최종 상태인지 구..
2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 스위치를 누르는 순서는 상관 없다 고로 처음부터 끝까지 한번 탐색하면 된다. 모든 스위치는 누르거나 누르지 않거나 둘 중 하나 두번 누르면 안누른것과 같다. 두번 이상 누르는 경우를 고려할 필요가 없다. 누를지 말지 어떻게 결정할까 n번 전구는 n-1, n, n+1번 스위치에만 영향을 받는다. 즉 앞에서 뒤로 순차적으로 탐색할때, n+1번 스위치가 n번 전구에 마지막으로 영향을 줄 수 있는 스위치이다. 스위치의 바로 앞 전구의 상태를..
5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 이 문제는 노드와 간선 수가 많아서 1. 그래프는 인접 행렬로 표현하면 메모리 초과가 발생한다. 인접 리스트로 표현하도록 한다. 2. 최소힙을 사용해야지만 시간초과가 발생하지 않는다. 코드와 알고리즘은 따로 정리했다. Dijkstra 다익스트라 : 고정된 출발지에서 다른 노드들까지의 최단거리찾기 1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 다양한 풀이 방법 (행단위, 열단위, 스택) 매우 다양한 풀이로 해결할 수 있는 문제인 것 같습니다. 전 두가지 방법을 시도해봤고 접근법은 코드에 주석으로 달아놨습니다. 1. 행단위로 해결하기 2. 열단위로 해결하기 2번이 가장 많이 알려진 풀이인 것 같습니다. 2번의 경우 max(slicing)으로 해결할 수 있고 그게 코드상 훨씬 간결하긴한데 모든 칸에 대해서 왼쪽, 오른쪽의 max 값을 구하면 O(N*N)이라 O(N)으로 해결해보려고 메모이..
2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 유의미한 탑만 남기자 유의미한 탑은 신호가 도달할 가능성이 있는 탑이다. 자기자신보다 큰 탑에 신호가 완전히 막힌 탑은 앞으로 무의미한 탑이된다. 그런 탑들을 제외하면서 정보를 가져가면 빠르게 탐색할 수 있다. 스택을 이용해서 관리할 수 있다. 앞에서부터 탐색을 진행하면서 스택의 가장 위에 있는 탑보다 현재 탑이 더 높은 경우 스택에 있는 탑은 무의미한 탑이 되므로 pop해서 모두 제거한 뒤 현재 탑을 스택에 추가한다. 시간복잡도 시간복잡도는 O(N)으로 대..
2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. O(N*N*logN) : 2개 조합 완탐+바이너리서치 3개의 용액을 고르는 방법을 찾아야한다. 2개의 용액을 완전 탐색으로 고르고, 세 용액의 합이 0에 가장 가까워지도록 하는 마지막 용액을 찾는 방식을 채택했다. 2개의 용액을 완탐으로 찾는데 O(N*N), 마지막 용액을 binary search으로 찾는데 O(logN)이 걸린다. (이진 탐색의 경우 재귀로 푼 경우 시간초과, 반복문으로 푼 경우 성공이었다. 반복문으로 쉽게 짤 수 ..
