본문 바로가기

Study/알고리즘

[BOJ]2178 미로 탐색 - python https://www.acmicpc.net/problem/2178 BFS를 사용하여 풀었습니다. 큐의 길이를 재면서 BFS를 돌리는 방식으로 최소 블록 갯수를 구했고,한번 방문한 부분은 숫자를 바꿔주는 것으로 다시 접근하지 않도록 처리했습니다. 123456789101112131415161718192021222324252627282930313233import sysimport collections dy = [-1, 0, 1, 0]dx = [0, 1, 0, -1] fastinput = lambda: sys.stdin.readline().rstrip() N, M = map(int,fastinput().split()) maze = [[int(x) for x in fastinput()] for _ in range..
[2019 카카오 신입 공채 1차 코딩 테스트] 2. 실패율 - python 처음에 접근한 방법은 stages를 정렬한 뒤에 visit라는 배열에 해당 스테이지에 방문한 사람의 수를 저장하고 passCnt에는 해당 스테이지를 통과한 사람의 수를 저장했다. visit는 stage를 역순으로 정렬한 뒤에 아래 코드이 반복문을 사용하여 초기화를 해주었고, passCnt도 초기화 해준 뒤 실패율이 아닌 스테이지 성공률을 buffer 리스트에 튜플형태로 저장하였다. 그리고 이를 정렬하여 answer에 저장하는 방법을 사용했는데, 채점결과 70점대로 통과하였다. 이를 개선하여 passCnt 없이 성공률을 계산하였는데 이는 visit를 모두 채워넣었을때 i번 스테이지 성공률 = visit[i+1] / visit[i] 이기 때문이다. 하지만 이를 적용해도 채점결과가 변하지 않았다. 아래는 해당..
[2019 카카오 신입 공채 1차 코딩 테스트] 1. 오픈채팅방 - python 파이썬의 딕셔너러를 이용하여 해결했다. 구현만 하면 되는 문제인데 딕셔너리를 효율적으로 사용하지 않으면 시간초과가 나올수도 있다. 12345678910111213141516171819202122232425def solution(record): answer = [] buffer = [] chatroom = dict() for i in record: tmp = i.split() op = tmp[0] uid = tmp[1] if op == "Enter": nic = tmp[2] chatroom[uid] = nic buffer.append([uid, "님이 들어왔습니다."]) elif op == "Leave": buffer.append([uid, "님이 나갔습니다."]) else: nic = tmp[2] cha..
[BOJ]15954 인형들 - python https://www.acmicpc.net/problem/15954 단순한 완전탐색으로 해결했습니다. 처음에 제출할때는 문제의 조건을 하나 놓쳐서 틀렸는데 주어진 조건이 K이상의 연속된 위치에 인형들을 선택하는것인데 K이상 이라는 조건을 놓쳐서 코드를 수정했다. 처음에 백준 사이트에 제출할때 python3로 제출했을때는 시간 초과가 났었는데 pypy3로 제출하니 시간초과가 발생하지 않고 통과되었다. 해당 문제의 FAQ를 정리한 글이 있어서 이를 참고하여서 문제를 해결했다. https://www.acmicpc.net/board/view/29582 코드는 다음과 같다 12345678910111213141516171819202122232425262728293031import sysimport mathfrom ..
[BOJ]15953 상금 헌터 - python https://www.acmicpc.net/problem/15953 단순한 구현 문제이다. a, b가 0일때 예외처리를 해주지 않아서 한번 틀린게 아쉽다. 1234567891011121314151617181920212223242526272829303132import sys fest2017Prize = ((500, 1), (300, 2), (200, 3), (50, 4), (30, 5), (10, 6))fest2018Prize = ((512, 1), (256, 2), (128, 4), (64, 8), (32, 16)) fastinput = lambda: sys.stdin.readline().rstrip() T = int(fastinput()) for _ in range(T): a, b = map(int, ..
[BOJ]7576 토마토 - python https://www.acmicpc.net/problem/7576 큐를 이용한 BFS를 통해 풀수있는 문제입니다. 파이썬에서 collection 내장 모듈의 deque를 큐처럼 사용하여 BFS를 하였습니다. 코드를 보면 dy, dx를 이용하여 ny, nx를 구하는데, dy,dx는 방향을 나타내는 리스트로 각 인덱스 별로 짝을 이루어서 북,동,남,서 를 현재 좌표값에 더함으로써 현재위치에서 북, 동, 남, 서의 좌표값을 구하는것에 사용했습니다. 그리고 ny, nx는 인접한 배열의 좌표값이며, ny, nx가 익지 않은 토마토가 있는곳인지 체크하고 큐에 넣어주는 형식으로 BFS를 구현하였습니다. 1234567891011121314151617181920212223242526272829303132333435363..
[BOJ]1003 피보나치 함수 - python https://www.acmicpc.net/problem/1003 dp를 이용한 기초적인 문제입니다. 피보나치 함수 f(0), f(1) 의 호출횟수가 서로 영향을 주지 않는다는 규칙을 이용하면 쉽게 풀수있습니다. 각각의 함수 호출횟수를 따로 관리하여 저장하면 됩니다. 1234567891011121314151617181920212223import sys dp0 = list()dp0.append(1)dp0.append(0) dp1 = list()dp1.append(0)dp1.append(1) for i in range(40): dp0.append(dp0[i] + dp0[i+1]) dp1.append(dp1[i] + dp1[i + 1]) T = int(sys.stdin.readline().rstrip()) f..
[BOJ]2504 괄호의 값 - python https://www.acmicpc.net/problem/2504 이 문제는 stack을 활용하여 풀수있는 문제이다. 지난번 글 처럼 스택을 사용하므로 list를 스택으로 이용한다. 알고리즘을 설명해보면 스택에 괄호를 여는 "(","[" 기호와 연산결과를 저장하는 방법으로 구현했다. 우선 이해를 쉽게하기 위해 연산결과를 저장하는 부분은 무시한 채로 코드를 보면 0. 입력받은 문자열을 순서대로 검사하면서1. 괄호를 여는 기호의 경우에는 바로 스택에 push(append)연산을 해준다.2. 그리고 괄호를 닫는 기호( ")" , "]" )를 만나면 자신에게 알맞는 괄호를 여는 기호를 만날때 까지 스택을 pop 해준다.3. 이때 자신에게 맞지 않는 닫는기호를 만날경우 ex) "]"일때 "("를 만난 경우 잘못된..

티스토리툴바