본문 바로가기

알고리즘

[백준,Java] 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이전에 파이썬으로 풀었던 문제이지만 Java의 문법 공부와 함께.. 새롭게 풀어 본 문제입니다. bfs로 풀었으며 Scanner는 속도 이슈가 생겨서 안쓰고.. BufferedReader, StringTokenizer를 사용하였습니다. (이 개념은 다시 정리해보겠습니다.) 문법적인 문제로.. 컴파일 에러, 런타임 에러.. 많이 발생하였습니다.. 반성하고 자바로 앞으로 계속 연습할 생각입니다.. import java.util.*;.. 더보기
파이썬 딕셔너리 lambda TypeError: bad operand type for unary -: 'str' 에러 관련 파이썬 딕셔너리(Dictionary)를 정렬할 때 보통 문자열에 정렬을 시도하는 경우가 있습니다. 오름차순은 위 사진과 같이 정상 작동하나 내림차순으로 정렬을 시도 시( -x[0]) 위 사진과 같이 TypeError: bad operand type for unary -: 'str' 에러가 발생합니다. 이 오류는 문자열로 된 값에 마이너스부호를 붙일 수 없다는 데에서 오는 오류이다. 물론 reverse=True 를 사용하여 반대로 정렬할 수 있습니다. 하지만, 이렇게 하나의 정렬 조건만 쓰는 경우가 아닌 x : (x[0], -x[1]) 와 같이 여러 정렬 조건을 쓰게 된다면 조건이 엉킬 수 있습니다. ----------------------- 파이썬에서는 이런 상황을 위해 안정적인(stable) 정렬 알고.. 더보기
해시 테이블 (Hash Table) with 파이썬 C언어로 해시 테이블을 먼저 구현해 본 나에게는 파이썬에서 이렇게 간단하게 불러서 쓸 수 있다니.. 놀랍기만 합니다. 파이썬에서의 해시 테이블은 딕셔너리라는 이름으로 구현되어 있습니다. 딕셔너리가 없는 언어에서는 1. 배열로 hash Table 생성 2-1. 키값을 입력 시 해시값을 변환해주는 함수 생성 2-2. 해시으로 해시테이블에 저장하는 함수 이렇게.. 보통 해시 테이블은 연속되지 않은 값들 혹은 문자가 들어간 값들을 한번에 찾을 때 사용하면 시간이 많이 단축됩니다. 해시 테이블의 장점 단점 장점 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.) 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움 단점 일반적으로 저장공간이 좀더 많이 필요하다. 여러 키에 해당하는 주소가 동일할 경우 충돌.. 더보기
[백준] 1927번: 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net from heapq import heappush,heappop import sys n = int(input()) q = [] # put, get for i in range(0, n): x = int(sys.stdin.readline()) if x == 0: # pop if(len(q) == 0): print(0) else: print(heappop(q)) else : # pus.. 더보기
[백준] 11399번: ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net n = int(input()) arr = list(map(int, input().split())) arr.sort() sum = 0 result = 0 for i in range(0,n): result += sum+arr[i] sum += arr[i] print(result) 그리디 문제로.. skill 언어만 사용하던 나에게 오랜만에 문법 공부..? 정도로 풀었습니다.. 더보기
[Python] 다양한 문자열 입력 방법 저는 코딩테스트를 주로 파이썬으로 진행합니다. 예전에 고등학생 때는.. C언어를 사용하였지만 이제는 파이썬이 손에 익어버렸습니다. 그만큼 문법도 쉽고 구현도 쉬운 파이썬의 다양한 문자열 입력 방법과 변수, 배열에 저장하는 방법을 알려드리겠습니다. * map (자료형, 매핑할 값) * split() : 괄호 안의 값을 기준으로 값을 나눠줌, 빈칸은 한칸 띄어쓰기(' ')와 동일 - 변수 여러개 한줄에 입력 받기 map함수를 사용하면 for문을 쓰지 않고 한줄에 여러 개의 정수를 입력받을 수 있습니다. line단위로 입력이 나뉘기 때문에 엔터에 주의해야합니다. split()을 사용하여 띄어쓰기를 기준으로 변수를 나눕니다. * 참고 : int로 자료형을 바꿔주지 않으면 문자로 취급됩니다. x, y, k, t .. 더보기
[백준] 14499번: 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 이번 문제 역시 구현이.. 중요한 문제였습니다. 사실상 다이스가 어떻게 굴러가는지를 종이에다가 다 풀어서 동,서,남,북의 경우를 찾으니 나머지 구현은 쉬웠던 문제입니다. n,m, x,y,k = map(int,input().split()) arr = [] for i in range(n): arr.append(list(map(int,i.. 더보기
[백준] 3190번: 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 이번 문제는 간단한 로직 구현 정도였습니다. 로직이 다른 문제에 비해서는 조금은 난이도 있었다고 생각합니다. 삼성 A형 문제들이 기본 알고리즘도 중요하지만 구현에 초점을 두고 있다는 생각이 듭니다. (3시간 2문제여서 그런가 싶네요) from collections import deque n = int(input()) arr = [[0 for i in range(n)]for j in range(n)] ap.. 더보기

티스토리툴바