오뚝이개발자

문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 생각의 흐름 수빈이가 X에 있을 때 이동가능한 경우의 수는 X-1, X+1, 2X의 세가지이다. 가능한 경우는 이 세가지이므로 수빈이의 위치를 q에 넣고 이들을 pop하면서 BFS로 탐색을 해주면 된다. 이 때, pop을 했을 때 원소가 K와 같은 값이면 탐색을 종료한다. 방문을 체크하기 위해서는 visit이라는 1차원 리스트를 사용하였다. 리스트에는 ..

이전에 포스팅한 AWS S3 객체 리스트 불러오기 1 와 유사한 내용이다. 마찬가지로 아래의 코드도 S3의 버킷내의 객체를 읽어들이는 것이다. 차이점은 아래의 코드는 key값을 그대로 불러오는 파이썬 스크립트 코드라는 것이다. 이전 포스팅의 경우 버킷내 최상단의 객체들에 대해서만 읽어들이지만 아래 코드의 경우 말그대로 '모든' 객체에 대한 key값을 읽는 것이다. import boto3 def get_all_s3_objects(s3, **base_kwargs): continuation_token = None while True: list_kwargs = dict(MaxKeys=1000, **base_kwargs) if continuation_token: list_kwargs['ContinuationTok..

AWS S3 버킷내의 객체 리스트를 불러와야 할 때가 있다. 이를 redirection시켜 txt 파일로 저장해둔다거나 하면 객체명에 대한 정보를 얻을 수 있기 때문이다. 객체의 경로를 포함한 객체명은 해당 파일의 key가 되기 때문에 중요하다. aws s3 ls 이럴 땐 위와 같은 aws cli를 사용하면 된다. aws s3 ls > key.txt 위와 같이 작성하면 key라는 텍스트 파일안에 객체 리스트들이 저장되도록 redirection 시킬 수 있다. 해당 개념과 연관하여 s3가 파일을 어떠한 식으로 저장하는지에 대해 간략히 설명을 하자면, 기본적으로 s3 버킷에는 '폴더'라는 개념이 없다는 것을 인지해야 한다. 예컨대, School이라는 버킷내에 Student라는 폴더 안에 Amy.txt라는 파..

파이썬 dictionary 구조의 key값을 이용해 value를 참조하는 방법은 두 가지이다. fruit = ["apple":1200, "banana":1300] print(fruit["apple"])# 1200 print(fruit.get("apple"))#1200 print(fruit["orange"])# KeyError print(fruit.get("orange"])#None 위에서 보다시피 fruit[key]와 get(key)메소드를 이용하는 것이다. 차이점은 직접 접근하려는 경우 해당 키가 딕셔너리에 없으면 키에러를 일으키지만 get메소드의 경우 None을 반환한다는 것이다. 용도에 따라 맞게 사용하면 된다.

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 생각의 흐름 메모리 제한이 심한 문제이다. 따라서 2차원 리스트 그대로를 이용해 문제를 풀기에는 무리가 있다. 메모리 제한을 해결하기 위해선 저장하는 방식을 바꾸어야 하는데 주어진 예시에서 0을 9로 바꿔주고 이를 int형으로 저장한다. 예를 들어 예제1의 경우 193425786이 된다. 위와 같이 저장하면 특정한 "상태"를 나타낼 수 있는데 이 상태에 대한 value 값으로 이동 횟수를 매칭시켜 저장해야 한다. 이를 위해 dictionary 구조를 사용한다. 즉, k..

문제 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 생각의 흐름 편의상 물통을 각각 x,y,z라고 하자. 물이 담겨 있는 것을 "특정한 상태"라고 바라보자. 그러면 이 특정상태는 x,y에 ..

https://git-scm.com/book/ko/v2 Git - Book git-scm.com 위의 링크는 깃 사전과 같이 다양한 기능 및 활용법들을 모아둔 링크이다. 참고하면서 깃에 대해서 배워가며 필요한 내용들을 포스팅할 계획이다.

백트래킹 알고리즘을 우리말로 하면 '퇴각검색'이라고 할 수 있다. 그렇다면 뭐가 퇴각이라는 걸까? 이에 대한 설명은 좀 더 미뤄두도록 하자. 위키피디아의 정의를 찾아보면 아래와 같다. “Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems…” 중요한 것은 마지막 부분인데 CSP(Constraint Satisfaction Problems)에 적용한다는 것이다. 그럼 CSP가 뭘까? 말그대로 특정 조건을 만족하도록 하는 문제를 말한다. 이러한 CSP의 정의를 백트래킹과 연관지어 생각해보면 백트래킹이란 "조..