본문 바로가기

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

(37)
[BOJ] 1697. 숨바꼭질 문제 숨바꼭질 (https://www.acmicpc.net/problem/1697) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 이동 방향이 3가지로 정해져 있다. 목표지점이 정해져있으므로, 해당 목표지점에 도달 시, BFS를 끝내고, 지금까지 간선의 스텝(time) 을 반환한다. 우리는 모든 노드를 최대한 1번 방문하며 BFS를 진행한다. 따라서 시간 복잡도는 O(n) 이다. 맨 처음 생각엔, 한 스텝에서 갈 수 있는 경우의수가 3가지 이므로, n번 스텝까지 진행할 시, O(3^n) 이 아닌가 했다. 이는 매우 큰 수로, k가 좀만 커져도 1억을 넘어 시간초과다. BFS의 시간복잡도는 O(|V|+|E|) 로 알려져있다. 여기..
[BOJ] 9466. 텀 프로젝트 문제 텀 프로젝트 (https://www.acmicpc.net/problem/9466) 풀이 1. 초기접근 문제조건 해석 문제를 잘 읽어보면, 주어진 데이터를 그래프로 보고, 이 중, 싸이클 인 것만 한 팀이 되는 것을 알 수 있다. 즉, 주어진 학생의 수(노드) n개에서 싸이클이 아닌 학생(노드) 만 잡아내면 된다. 알고리즘 모든 노드를 순차적으로 탐색해야 하므로, 기본적으로 DFS 다. 간선을 따라 DFS를 진행하되, 다음 진행 노드가 이전에 방문된 적이 있다면 (visited), 그 노드부터 현재노드까지 싸이클 내에 있음을 알 수 있다. 위 방식으로, 싸이클을 발견했다면, DFS 를 종료하고, 다시 하나씩 반대방향으로 back 하며 cycle 내에 있는 노드는 팀을 이룬다는 체크를 해준다.(team..
[BOJ] 1405. 미친로봇 문제 미친로봇 (https://www.acmicpc.net/problem/1405) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 횟수가 정해져 있다. DFS, BFS 문제. 확률을 구해야 하므로, DFS, BFS 마지막 스텝에서 지금까지 구한 확률을 모두 더해줘야겠다. 마지막 스텝에서 지금까지의 확률을 가지고있어야 하니, 인자로 지금까지의 확률을 넘겨줘야겠다. 알고리즘 BFS가 먼저 떠올라 BFS로 구현. 코드 # 동서남북 순으로 방향 저장. dxs = [0, 0, 1, -1] dys = [1, -1, 0, 0] def bfs(x, y): q = [(x, y, 1)] step = 1 answer = 0 visited = {(x, y)} while q: size = len(q) nex..
[삼성 SW Expert Academy] 1247. 최적 경로 문제 1247 [S/W 문제해결 응용] 3일차 - 최적 경로 풀이 1. 초기접근 문제조건 해석 N 모든 경우를 다 해보는 방법을 고려해보자. 가장 직관적인 방법은, 각 포인트의 거리들을 미리 구하고, 순열로 생성하며 모든 경우의 수를 탐색하는 것이다. 알고리즘 각 포인트들의 좌표를 가지고 만들 수 있는 모든 순열을 탐색해보며, 각 경우에서의 거리를 구해 최소 거리를 갱신. 순열을 만드는 방법은 파이썬 내장 함수인, itertools.permutations() 로 손쉽게 구현 코드 import itertools t = int(input()) for tc in range(1, t+1): n = int(input()) l = list(map(int, input().split())) # 회사, 집, 그리고 각 ..
[BOJ] 14888. 연산자 끼워넣기 문제 연산자 끼워넣기 (https://www.acmicpc.net/problem/14888) 풀이 1. 초기접근 문제조건 해석 N max_value else max_value min_value = res if res < min_value else min_value print(max_value) print(min_value) 2. 유의할 점 python으로 제출할 시, 시간초과가 뜸. pypy 로 제출하면 정답.
파이썬으로 문제 풀 때 주의해야할 점들 요새 코딩 테스트 문제 푸는 것을 파이썬 스타일로 바꾸려 하고있다. 나는 원래 문제풀 때 c++ 유저였는데 (대학생활 내내 c++ 이었다.), 뒤늦게 나마 바꾸려 하니, 사실 적응이 잘 안가는 것도 사실이다. 그렇다보니, 파이썬 코드를 짜더라도, 굉장히 c 스러운 모습이 보이는데, 이 역시 바꾸려고 하나씩 공부 중이기도 하다. 각설하고, 백준 저지 에서 c 로 풀면 정답으로 간주되는 것이, 파이썬으로 풀면 정답으로 간주되지 않는 경우가 간혹 있다. 이 때, 어떻게 해야할지 발견한 몇 가지를 여기에 적어본다. 1. input() 말고 sys.stdin.readline() 를 사용하자. 결론만 말하자면, 입출력 속도가 다음과 같다. sys.stdin.readline() > raw_input() > input..
[BOJ] 적록색맹 문제 적록색약 (https://www.acmicpc.net/problem/10026) 풀이 1. 초기접근 문제 조건 해석 n
[프로그래머스] 거스름돈 문제거스름돈 (https://programmers.co.kr/learn/courses/30/lessons/12907) 풀이1. 초기접근문제 조건 해석n은 100,000 이하의 자연수입니다. 화폐 단위는 100종류 이하입니다. -> O(nm) 안에 풀어야함.문제 조건의 변수로, 다음이 주어짐.거슬러 줘야 하는 금액 n돈의 종류 money거슬러줘야하는 금액 n과 돈의 종류에 따른 경우의 수를 고려해야 하므로, 두 가지를 고려한 2차원 dp를 생각할 수 있음.2차원 dpd[j][i] = (money[0] 부터 money[j] 의 화폐를 가지고 i원을 낼 수 있는 방법의 수) 라고 하면, 목표하는 정답은 d[money.size()-1][n] 가 됨.먼저 어떤 화폐를 쓰던, 0원을 거슬러주는 방법의 수는 1이므로..