본문 바로가기

취업과 기본기 튼튼

 (76)
[BOJ] 2644. 촌수 계산 문제 촌수계산 (https://www.acmicpc.net/problem/2644) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 가장 기초적인 BFS 문제라고 생각된다. 파이썬에서 그래프 탐색이 필요한 문제들은, 일단 dict {} 로 그래프를 먼저 만들고, (부모노드가 key, 자식노드들이 해당 key의 values가 된다.) set {} 으로 방문체크용 스트럭처를 만들면 된다. 이러면 노드접근에 모두 상수시간 O(1) 밖에 안걸린다. 코드 import sys from collections import defaultdict n = int(input()) a, b = map(int, input().split()) t = int..
[BOJ] 16397. 탈출 문제 숨바꼭질 (https://www.acmicpc.net/problem/1697) 풀이 1. 초기 접근 문제조건 해석 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다. BFS 문제다. 알고리즘 전체적으로 1697.숨바꼭질 과 동일한 문제다. 다만, 여기서 신경써야할 부분은, 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 이 부분이다. 언어에 따라 다르게 처리할 수 있겠지만, 파이썬은 그래도 str() 이나 int() , .join() 을 통해 쉽게 처리할 수 있다. 아래 코드를 보면 된다. 코드 import sys n, t, g = list(map(int, sys.stdin.readline().split())) def bfs(n, t, g): ..
[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..

티스토리툴바