본문 바로가기

취업과 기본기 튼튼/코딩 테스트 노트

 (37)
[프로그래머스] 방문 길이 문제 방문 길이 (https://programmers.co.kr/learn/courses/30/lessons/49994) 풀이 1. 문제 조건 해석 문제도 직관적이고, 변수 조건도 무난, 아주 심플하다. 2. 알고리즘 U, L, D, R 을 하나씩 입력받으며, 그냥 순차적으로 트래킹하면 된다. visited 를 set 자료구조로 두어, 이미 지나간 길인지 아닌지 체크하면 된다. 주의해야할 점은, 트래킹에는 '단방향성' 이 존재하지만, 길 자체는 '양방향' 이라는 점이다. 3. 코드 def solution(dirs): dxs, dys = [-1, 0, 1, 0], [0, -1, 0, 1] d = {"U": 0, "L":1, "D":2, "R": 3} visited = set()..
[프로그래머스] 가장 먼 노드 문제 가장 먼 노드 (https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3) 풀이 1. 문제조건 해석 먼저, 현재 노드로부터 가장 멀리 떨어진 노드와의 최단거리를 찾는다. 이 최단거리들 중, 가장 큰 값을 가지는 거리의 개수를 찾는 문제다. 2. 알고리즘 전형적인 BFS 문제다. 그냥 다 탐색하면서 거리를 잰 뒤, 마지막에 거리 중 가장 큰 거 개수 세면된다. 진짜 그냥 주어진대로 하면 됨. 3. 코드 from collections import defaultdict, deque def solution(n, edge): dists = {i:0 for i in range(1, n+1)} # 노드 1과 다른 노드들 사이의 거리를 담..
[프로그래머스] 야근 지수 문제 야근지수 (https://programmers.co.kr/learn/courses/30/lessons/12927) 풀이 1. 초기 접근 문제 조건 해석 n은 1,000,000 이하인 자연수입니다. -> 뭔가를 해도, O(n log n) 안으로 끝내야 한다. (for 효율성 테스트) 사실 문제자체는 엄청 간단하다. 직관적으로, 누가 봐도 정렬 후 가장 큰 값만 계속 1씩 빼야될 것 같은데, 문제는, 리스트 내 가장 큰 값을 n 번 루프동안 어떻게 계속해서 찾아낼 것인가다. 리스트로는 택도없다. 왜냐하면 반복문 돌 때마다 정렬할 것인가? 시간복잡도 루프 O(n) 내, 정렬에 O(n log n) 이 나온다. 따라서 불가능. 주목 해야할 것에만 주목하자. 리스트 내 '최대값' 만 필요하다는 ..
[프로그래머스] 가장 큰 수 문제 가장 큰 수 (https://programmers.co.kr/learn/courses/30/lessons/42746) 풀이 1. 초기 접근 조합을 이용하여 완전 탐색. 가장 먼저 떠오르는 직관적인 방법은, numbers 에 있는 모든 변수들을 조합하여 만든 수들 중, 가장 큰 값을 반환하는 것이다. 이럴 경우, 조합하는 시간은 약 O(len(numbers)!) 이다. 그런데, 조건에 보면, 1 < numbers < 100,000 이란다. O(100000!) 은 절대 1초 내로 안들어오므로, 이 알고리즘은 사용할 수 없다. number 를 정렬한다거나, 탐색할 때, O(n log n) 안으로 해결 해야 한다는걸 늘 생각해야 한다. 보통, 이렇게 루프로 시간문제가 걸리는 경우, 배열 내 아이템을 &#3..
[BOJ] 5430. AC 문제 AC (https://www.acmicpc.net/problem/5430) 풀이 1. 초기 접근 문제조건 해석 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000) n
[BOJ] 2493. 탑 문제 탑 (https://www.acmicpc.net/problem/2493) 풀이 1. 초기 접근 문제조건 해석 N 이 500,000만 이하로 주어진다고 한다. 즉 O(N) 또는 O(N log N) 안으로 풀어야 한다. 선형 탐색 한 번만 가능한 것이다. 알고리즘 주어진 예제 6 9 5 7 4 에서 앞의 인덱스부터 하나씩 탐색해나간다 했을 때, 현재 인덱스의 값의 올바른 정답이 무엇인지 차근차근 생각해보자. 맨 왼쪽 6은 수신하는 곳이 없으니 항상 0일 것이다. 9 도 마찬가지로, &#39;지금까지&#39; 9 보다 큰 값이 없었으므로, 값은 0이 된다. 5 에서는, 지금까지5 보다 큰 값인 9가 있었다. 따라서 값은 배열에서 9의 인덱스값인 1이 된다. 7도 마찬가지다. 지금까지 7보다 큰 값은 9였..
[BOJ] 17135. 캐슬 디펜스 문제 캐슬 디펜스 (https://www.acmicpc.net/problem/17135) 풀이 1. 초기접근 문제조건 해석 판이 주어지고, 각 턴에 따라 판의 형태가 달라진다. 문제에서 이야기 했 듯, 궁수의 위치가 중요하다. 궁수의 위치에 따라, 진행되는 판의 모양이 달라진다. N, M BFS다. 가장 왼쪽에 있는 -> 방향 순서를 고려해줘야 한다. 같은 적이 여러 궁수에게 공격당할 수 있다는 말은, 각 궁수가 없애고자하는 좌표가 겹칠 수 있다는 말이다. 없앨 좌표를 일괄적을 처리해야 한다. 알고리즘 먼저, 각 궁수가 위치할 수 있는 모든 경우를 구한다음, 각 경우를 탐색한다. itertools.combination 을 이용하면 된다. 각 경우에서, 3명의 궁수가 이번 스텝에 없앨 적의 좌표(targe..
[BOJ] 14891. 톱니바퀴 문제 톱니바퀴 (https://www.acmicpc.net/problem/14891) 풀이 1. 초기 접근 문제조건 해석 각 스텝에 따라, 기존 자료구조의 값이 바뀌는데, 바뀌는게 연쇄적이다. 시뮬레이션 + DFS 문제다. 알고리즘 문제 조건에서, 많은걸 알려주는데, 일단 톱니바퀴를 리스트로 표현할 수 있음을 알 수 있다. 그리고 톱니바퀴의 회전은 리스트 요소들을 왼쪽 혹은 오른쪽으로 시프트하는 것임을 알 수 있다. deque 의 .rotate() 가 있다! 회전 조건은, 정해진 인덱스를 비교하면 된다. 코드 from collections import deque from sys import setrecursionlimit setrecursionlimit(10**8) def dfs(no, di, visit..

티스토리툴바