본문 바로가기

Python9

(python) 부동 소수점 오류 및 연산 정리 파이썬 공식 문서에 보면 부동 소수점 산술 오류에 관한 글이 있다. 알고리즘 문제를 풀 때 가끔 부동 소수점 오류 때문에 발생하는 문제를 해결하는 법과 파이썬에서의 나누기를 항상 헷갈리는 나를 위한 정리이다. 부동 소수점 산술이란? 부동 소수점 방식은 컴퓨터 상에서는 실수를 근사하여 표현하는 수이다. 쉽게 말해 이진법을 사용하여 실수를 나타내기 때문에 정확한 값을 나타낼 수 없다. 컴퓨터에서는 십진수 0.1을 0.1000000000000000055511151231257827021181583404541015625 컴퓨터로 표현할 수 있는 0.1과 가장 가까운 값을 내놓는다. 1 / 10을 출력해 보면 0.1이 나오지만 실제 저장된 값은 위에 수가 저장되기에 오류가 생긴다. 0.1 + 0.1 == 0.2는 .. 2023. 2. 18.
(python) 7562 나이트의 이동, 7569 토마토 7562 나이트의 이동 https://www.acmicpc.net/problem/7562 문제 체스판의 길이와 시작위치, 도착위치를 주고 체스에서의 나이트로 최소 몇 번만에 도착할 수 있을지 묻는 문제이다. 입력 테스트 케이스 개수를 주고 그다음 체스판의 한 변의 길이 (체스판은 주어진 변수 * 변수가 크기가 된다.) 시작위치 x, y 도착위치 x, y 기본적인 그래프에서의 BFS를 사용하고 이동 좌표만 나이트에 맞추어 설정해 주면 된다. from collections import deque def bfs(): while queue: x, y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0 2023. 1. 19.
백준 25501번 문제 함수 호출 횟수 계산 -python 백준 문제 단계별로 풀기 중 재귀 단계에 있는 문제이다. 문제 자체는 재귀 함수를 주어주고 푸는 문제라 쉬운데 여기서 함수가 몇 번 호출됐는지 구하는 것이 나와 풀이도 기억할 겸해서 들고 왔다. 백준 25501번 https://www.acmicpc.net/problem/25501 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의.. 2022. 11. 17.
백준 1003번 문제 (다이나믹 프로그래밍) python 이중 배열 요즘 다이나믹 프로그래밍 완벽 숙지를 위해 매일 하나씩 풀고 있습니다. 백준 1003번 문제는 이중 배열을 이용하여 풀었는데요. 이중 배열을 대입 연산자를 이용하여 변경할 때 꼭 알아야 하는 내용이 있어 같이 들고 왔습니다. 문제 1003번 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치수열의 응용문제인데 당연히 다이나믹 프로그래밍으로 해결이 가능하다. 문제를 보면 fibonacci(1), fibonacci(0) 일 때 각각 1과 0을 리턴한다. 그렇다면 fibonacci(2) 일 때는 fibonacci(1) + fibonacci(.. 2022. 11. 2.
파이썬 스택 자료구조 스택이란? 후입선출 특성의 자료구조 마지막으로 들어온 것이 처음 나가는 형태 예로 8 5 3 순으로 입력하면 3 5 8 순으로 나가게 된다. 파이썬에서는 리스트를 사용하여 스택 자료 구조를 표현할 수 있다. 리스트를 먼저 초기화시키고 stack = [] 스택에 원소를 추가할 때는 append 매서드를 사용하여 추가 stack.append(8) stack.append(5) stack.append(3) stack ---> [8, 5, 3] 스택에서 원소를 제거할때는 pop 매서드 이용 stack.pop() stack ---> [8, 5] 최상단부터 출력할때는 stack[::-1] 2021. 2. 10.
구현 유형 알고리즘 정리 구현 유형 알고리즘은 풀이를 생각해내기는 쉽지만 코드로 작성할 시 어려움을 겪는 알고리즘입니다. 시뮬레이션 문제, 완전 탐색 등이 포함됩니다. 알고리즘 대회를 볼 때 2차원 공간에서의 이동 관련 문제를 많이 접했습니다. 시뮬레이션 문제의 N * N 공간에서의 이동을 할 떄 코드입니다. n = int(input()) ## N*N 을 위한 값 n 입력 받음 x, y = 1, 1 ## 처음 위치를 정하기 plans = input().split() ## 입력 값 공백 기준 나누기 dx = [0, 0, -1, 1] ## x, y 위치 이동을 위한 리스트 작성 dy = [-1, 1, 0, 0] ## (0, 1) 면 (1, 2) 이동 y축으로 이동 move_type = ['L', 'R', 'UP', 'DOWN'] #.. 2021. 1. 23.

티스토리툴바