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. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출..
1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출발지를 들렀다고 표시한다. 2. 들르지 않은 노드 가운데 가장 가까운 노드를 선택한다. 3. 선택한 노드를 거쳐서 직접 연결된 다른 노드까지 도달하는 거리가 이미 저장된 거리보다 짧다면 최단 거리를 갱신한다. 4. 2~3을 모든 노드를 방문할때가지 반복한다. 모든 노드를 들르면서 위의 과정을 진행하기 때문에 O(N) 의 연산이 필요하다. 거기에 2번을 완탐으로 탐색하게 되면 매번 O(N)이 걸리므로 총 O(N^2) 이 필요한 알고리즘이다. 2. 최소힙 사용 2. '기장 가까운 노드 찾기'를 더 빠르게 수행하기 위해 최소힙을 사용해..
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)으로 해결해보려고 메모이..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 여러 필드 기준 GROUP BY, 삼중 JOIN, date필드에 조건 걸기 3개의 테이블을 조인해서 해결합니다. 여러 필드 기준으로 ORDER BY 하듯 , 로 연결해서 여러 필드 기준으로 GROUP BY를 할 수 있습니다. YEAR이나 DATE, LIKE 등으로 date 필드 조건을 걸어줍니다. 쿼리문 SELECT a.AUTHOR_ID, a.AUTHOR_NAME, b.CATEGORY, SUM(bs.SALES*b.PRICE) AS TOTAL_SALES FROM BOOK_SALES bs JOIN BOOK b ..
