https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 나도 맥주마시면서 펜타포트 페스티벌 가고 싶다 ! 88%에서 걸린 코드 from collections import deque t = int(input()) # 맨하튼 거리 계산 def distance(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) def route(sx, sy, ex, ey): queue = deque([]) x, y = sx, ..
Algorithm (PS)
https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net i ) 선형적으로 문제를 풀어야 하니까 정렬 , 투포인터 , .. 등등을 떠올리게 되었다. ii ) 문제를 그려서 이해해보았다. 한 선분을 기준으로, start와 end 가 선분의 양 끝점이라고 한다. 이 경우 새로운 두 개의 점이 주어졌을 때 위의 그림과 같이 두가지 경우로 나뉘게 된다. 합쳐지거나, 합쳐지지 못하거나 두가지이다. 주어지는 (x, y) 에 대해 오..
https://school.programmers.co.kr/learn/courses/30/lessons/77485 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시뮬레이션 문제 값을 한칸씩 이동시키는 방법은 위의 그림처럼 했다. 왼쪽 ->하단 -> 우측 -> 상단 순서로 한칸씩 값을 이동시켰다. 이동시키면서 min_num 값과 비교해서 최솟값을 갱신해준다. 직사각형이므로, 문제에서 주어지는 좌표값 (x1, y1), (x2, y2) 를 이용해서 직사각형의 테두리를 순회할 수 있다. def solution(rows, columns, queries): answ..
https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 구현 + 브루트포스 + 그래프 탐색 문제였다. N 값이 3 ~ 6 으로 작아서 브루트포스로 장애물을 설치할 3군데를 정해서 풀어도 되는 문제였다. 선생님이 움직이지 않아서 상하좌우 방향으로 세로줄 전체와 가로줄 전체만 확인해주면 되었다. from itertools import combinations import sys input = sys.stdin.readline n = int(inpu..
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net pypy 로 제출해서 맞은 코드 플로이드워셜이라는 힌트를 가지고 풀었다. 처음에는 Union-find 로 사이클을 찾아야 하는가? 라고 생각했으나, 결국 문제에서는 최소 경로 비용을 구하는 것이 핵심이므로 플로이드 워셜로 푸는것이 더 적절하다고 판단했다. 우선,graph 구성했다. 예제를 기준으로 아래의 graph를 만들어 보았다. graph 에는 a-> b 가는..
https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제보고 DFS/BFS를 떠올렸다 2. 처음에는 DFS이고 최단 경로로 탐색하려면 아래방향이나 오른쪽 방향을 먼저 탐색하는 greedy 방식인가? 라고 생각했다 3. 그리고 모든 경로를 탐색해야 하므로 백트래킹으로 풀었다. 4. 테스트케이스에서 시간초과가 났다 해결방법 - DFS 모든 경로 탐색에서 안되는 경로를 빨리 쳐내야 한다 !! - DP 테이블을 이용한다. 탐색하지 않을 경로의 재귀함..
https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오랜만에 자료구조형에 대해 생각해 볼 수 있는 문제를 풀었당 문제상황 (시간 초과) 맨 첨에는 list 만들고 삭제하면 0 , 데이터 있는 값은 1 이렇게 테이블을 만들어주었다. 그러나 list 로 테이블을 관리하게 되면.. Z 복구 연산의 경우 0 -> 1로 바꿔주는거니 O(1) 이지만, 행들을 순차적으로 탐색해야 하는 U, D, C 연산의 경우 시간복잡도에서 걸린다. 최대 cmd 가 20000..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 시간초과 풀이 단순하게 구현했더니 시간초과 난다 ㅎㅎ import sys input = sys.stdin.readline r, c = map(int, input().split()) board = [] for i in range(r): data = input() temp = [] for j in range(c): temp.append(data[j]) board.append(temp) dx =..
