본문 바로가기

전체 글

 (224)
[java/python] 프로그래머스 Lv2. - 하노이 탑 코딩테스트 연습 - 하노이의 탑 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 백준에서 똑같은 문제를 풀었을 때 잘 이해가 가지 않았는데 이번에 다시 풀어보니 이해가 갔던 문제였다. 재귀함수의 기본인 하노이탑 문제를 정리해보았다. 1. 원반 n개를 가장 오른쪽 기둥으로 모두 옮겨야 한다. 2. 한 번에 하나씩만 옮길 수 있다. 3. 크기가 큰 원반 위에 작은 원반을 올려야 한다. 이 사항들을 지키며 주어진 원반을 옮겨야 한다. 문제에서는 최소로 움직이는 경로를 구해야하는데 재귀함수를 이용하여..
패스트캠퍼스 Python 코딩테스트 강의 4주차 이번 강의에서는 백준 10828, 10773, 1874번을 학습하였다. 세 문제 모두 스택 구현 문제로 스택의 기본 원리를 파악할 수 있는 시간이었다. 1.10828 10828번: 스택 (acmicpc.net) 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택 문제로 스택의 기본 메소드들을 구현하는 문제였다. 실버 5단계였는데 어렵지 않게 통과할 수 있었다. 파이썬에서의 스택은 단순 리스트를 사용하여 구현할 수 있으며 append(), pop() 메소드를 사용한다. import sys in..
[Python][Error] ValueError: invalid literal for int() with base 10: '\n' ValueError: invalid literal for int() with base 10: '\n' 형변환 에러이다. 10진수 int()로 변환할 수 없는 문자열이라는 뜻이다. 코딩테스트 문제를 연습할 때 코드 상의 문제가 없는데 위 에러가 계속 떠서 당황했던 기억이 있다. import sys를 했을 때 발생하는데 sys.stdin.readline()은 뒤에 개행문자가 같이 입력되기 때문이다. -> strip()을 사용하여 해결한다.
[TIL] 최소 신장 트리(MST) 2 - 프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) 시작 정점을 선택한 후 정점에 인접한 간선 중 최소 가중치의 간선이 연결된 정점을 선택한다. 선택한 정점에서 위의 과정을 반복하며 최소 신장 트리를 확장해 나간다. 프림 알고리즘 구현 노드의 연결을 확인하기 위한 집합과 연결된 간선들을 관리하기 위한 간선 리스트를 사용한다. 임의의 정점을 선택 후 노드 집합에 삽입한다. 해당 정점에 연결된 간선들을 간선 리스트에 삽입한다. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출한다. -> heapq 사용 만약, 해당 간선에 연결된 정점이 위의 노드 집합에 들어 있다면 다른 간선을 찾는다. (사이클 x) 그렇지 않다면 그 간선을 선택하고 mst를 리스트에 삽입한다. 추출된 간선은 간선 리스트에서 제거한다. 간선 리..
[TIL] 최소 신장 트리(MST) 1 - 크루스칼(kruskal) 알고리즘 최소 신장 트리(MST : Minimum Spanning Tree) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 신장 트리 최소 신장 트리를 찾을 수 있는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있음. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 한다. 신장 트리란? - 그래프의 모든 노드를 포함하면서 모든 노드가 서로 연결 되어 있고 트리의 속성을 만족시키는 트리 (사이클 x) 크루스칼 알고리즘(Kruskal's algorithm) 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 가중치를 기준으로 정렬하고, 가중치가 가장 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점(루트 노드)을 확인하고 서로 다르다면 연결한다. (같을 경우 사이클이 생기므로 x) Un..
[python] 13549 - 숨바꼭질 3 13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 bfs와 다익스트라 두 가지 방법으로 풀이할 수 있다. 전에 bfs 문제를 풀 때 다루었던 문제랑 똑같은게 아닌가? 했는데 이 문제에서는 가중치를 고려해야한다. 그래서 전에 풀었던 bfs 방식에서 가중치를 고려하여 살짝 변형하여 풀고 최근에 학습한 다익스트라로도 코드를 짜 보았다. [BFS] import sys from collections import deque #..
패스트캠퍼스 Python 코딩테스트 강의 3주차 이번 강의에서는 백준 10930, 1920, 4195 번을 학습하였다. 1. 10930 10930번: SHA-256 (acmicpc.net) 10930번: SHA-256 첫째 줄에 문자열 S가 주어진다. S는 알파벳 대문자와 소문자, 그리고 숫자로만 이루어져 있으며, 길이는 최대 50이다. www.acmicpc.net 이 문제는 신기하게도 난이도를 매길 수 없는 문제였다. 문제를 보니 파이썬에서 제공하는 hashlib를 사용하면 바로 풀 수 있는 문제였다. haslib.sha256(문자열 바이트 객체).hexdigest() 이렇게 하면 sha256을 사용하여 암호화 된 해시 결과 문자열을 얻을 수 있다. import hashlib input = input() encoded = input.encode() ..
[java] [Error] no suitable method found for sort(int[],java.util.Comparator<java.lang.Object>) 이전에 포스팅했던 프로그래머스의 '최솟값 만들기'를 해결하며 마주했던 에러 사항이다. 다시 설명하자면, 기존에 알고있던 Arrays.sort()와 Arrays.sort(arr, Collections.reverseOrder())을 사용하여 정렬을 하려고 했는데 계속 에러가 났다. Comparator는 원시 타입의 int 배열에서는 사용할 수 없었던 것이 원인이었다. 하단 블로그를 참고하여 Integer[] Br = Arrays.stream(B).boxed().toArray(Integer[]::new); Arrays.sort(Br, Collections.reverseOder()); integer[]로 변환하였다. boxed - boxed()는 원시 타입에 대한 스트림 지원을 클래스 타입으로 전환해준다. in..
728x90

티스토리툴바