87건의 항목
송재준 저자의 Programming Bitcoin을 정리합니다.
골드5 : 구현 문제이다.
실버2 : 동적계획법 문제이다.
실버2 : 동적계획법 문제이다. 풀이 그냥 합을 구하는 문제이다.
실버1 : DFS 문제이다. 풀이 DFS와 동적계획법이 섞인 문제이다. 일단, 특정 위치까지 갈 수 있는 모든 경우의 수를 구해야 하는데, 그냥 방문할 때마다 count를 늘려준다면, 중복해서 방문하는 곳이 너무 많아 비효율 적이다.
실버1 : 최단거리 문제이다. 생각 모든 경로에 대한 최단 거리를 구해야 한다. 가중치는 양수이자 동일 정점 개수 100개 모든 경로에 대해 최단 거리를 구해야 한다는 점에서 플루이드를 사용할 것이고, O(V^3) 알고리즘에도 통과한 노드 개수이므로 진행한다.
실버2 : BFS 문제이다.
골드4 : dp & DFS 문제이다. 풀이 이게. 접근 방식을 약간 반대로해서 오래걸렸다. 바텀 업 방식으로 사고를 하여, 마지막 지점까지 가는데 있어 4방향의 경로를 더해주어야 한다고 생각했다. 그런데 그렇게 생각을 하니 쉽게 점화식이 떠오르지 않았다.
실버5 : 브루트포스 문제이다.
실버2 : 조합 문제이다. 풀이1 기본적인 조합 문제이다.
실버4 : 그리디 문제이다. 풀이 단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 문자열만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.
실버1 : 그리디 문제이다. 풀이 처음에 부르트 포스로 접근했다가, 시간초과가 났다. 그래서 그리디로 방향을 전향했다. >가 나왔을 때, 가장 큰 숫자를 설정해두고, 이하 부터 순서대로 이숫자를 채우는 것으로 해당 조건을 만족시킬 수 있다.
브론즈2 : 브루트포스 문제이다.
골드4 : union find 문제이다. 풀이 기본적인 union find 문제. 코드를 기억하자.
실버2 : 동적계획법 문제이다. 풀이 기본적인 동적계획법 문제이다.
실버2 : DFS 문제이다. 풀이 그냥 구현하라는 대로 탐색해서 answer를 늘려주면 된다.
실버2 : two pointer 문제이다. 풀이 투포인터는 i이상 j미만으로 짠다. 같을 경우는 i를 늘려서 파악한다.
풀이1 실버1 : BFS 문제이다.
골드5 : BFS 문제이다.
골드5 : BFS 문제이다. 풀이 cost에 따라 탐색하지 않을 노드를 분명히 정해야 한다.
골드4 : BFS 문제이다. 풀이 아니 풀이방법을 아는데 왜 코드가 안돌아가는지 모르겠다. 계속해서 메모리 초과가 뜨는데 어떤 부분이 문제인지 아직도 못찾았다.
풀이1 실버4 : 이분 탐색 문제이다. 생각 특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.
실버1 : BFS 문제이다. 풀이 물의 높이를 존재하는 min값에서 max로 잡아줬었는데, 이렇게 하지않고 0부터 하니 통과했다. 국어문제인듯한데. 아무래도 비가 안오는 것부터 체크해주는게 보다 맞는 것 같긴하다.
골드4 : 완전 탐색 문제이다. 풀이 이게 전날에 급하게 짜다가 조건을 놓친 문제인데, 오늘의 첫문제로 도전해보았다. 난 BFS로 문제 풀이방향을 정했는데, 문제가 방문이 중복으로 일어난다는 것이다.
실버2 : 완전 탐색 문제이다. 풀이 기존 것에 비해 연산자 개수가 늘어난 문제. 단순한 순열로 풀면 44P10의 연산 결과라 못푼다. 그냥 완전탐색으로 풀면되긴한데, 백준에서 pypy로 제출했더니 틀렸다고 해서 당황했다.
실버1 : DFS 문제이다. 풀이 기본적인 DFS 문제이다. DFS를 사용할 때는 dp적 사고를 기반으로 코드를 짜는 것이 좋다. 즉, 현재 상태는 다음 상태들의 연산으로 구해진다는 것.
골드3 : dp? 문제이다. 풀이 음..풀이를 이상하게 했는지는 모르겠지만 일단 맞았다. 다른 사람들을 보니, 각각의 시작 위치에서 dfs를 돌려서 최대 거리를 구한뒤 max 를 취하는 방법을 사용한 것 같았다. 이렇게 풀었어도 될 걸 이상하게 풀었다.
골드3 : 최단 경로 문제이다. 풀이 이전에 풀었던 문제와 매우 비슷한데 음,.., 아 분명히 풀었다. 아마 프로그래머스 문제였던 것 같다. 연결되어 있는지 모두 파악하는 문제였다.
골드5 : 구현 문제이다. 풀이 문제 똑바로 읽자. 조건하나 안봐서 틀렸네.
실버2 : 순열 문제이다.
실버2 : 유니온파인드 문제이다. 풀이 유니온 파인드로 같은 집합인지 아닌지를 검증하고, 같은 집합이라면 촌수를 계산한다! 이 때 pypy로 하지말고 python3로 할 것.
골드5 : 구현 문제이다. 풀이 컨디션이 안좋아서 그냥 풀었다.
골드2 : union find 문제이다. 풀이 으으 너무 아쉽다. 잘해놓고 같은 친구가 들어올 경우에 계산이 중복된다는 것을 체크하지 못했다. 그리고 지나고 보니 코드가 더러워서 다시짰다.
골드5 : 스택 문제이다. 풀이 비슷한 문제를 한 3번 봤다. 근데 그 때는 heap을 사용해서 뒤에서 가장 큰 문자를 계속해서 뽑는 것으로 문제를 해결했다. 풍선 터트리기 그런 방식으로 해당 문제를 다시 풀려했으나, 밑에 알고리즘 분류를 봤는데 stack…이더라.
실버1 : 완전 탐색 문제이다. 풀이 매우 막 푼 풀이. 좋지 않다.
골드5 : 동적계획법 문제이다. 풀이 잘 접근했다고 생각했는데, 점화식을 잘 못 구했다.
실버5 : 해쉬 문제이다.
실버? : stack 문제이다. 풀이 처음에 op과 ()를 담는걸 별도로 생각했다가 낭패를 보았다. 생각하다보니 이 두개가 엮인다는 것을 알았고, 쉽게 규칙을 파악해서 풀 수 있었다.
풀이 실패했다. 뭔가 감은 오는데 기존의 dp처럼 풀려고 하니 문제가 안잡히는 기분. 일단 접근 방법은 맞으니, 엑셀처럼 나열하면서 규칙을 찾는 것이 좋다.
풀이 문자열 정렬의 아이디어는 항상 갖고 있는게 좋을 것 같다. 약간 스킬 적인 측면으로 작용하는데(~~~이거 버그아닌데 스끼린데~~~) 음 일단 보자. 이 문제는 보면 특징이 있다. 일단 다 만드는 것은 잘못된 방법이다.
풀이 아. 시도를 총 세번했다. 해시맵으로 발생할 수 있는 모든 구간에서 시청하고 있는 사람을 저장 아이디어는 좋았으나, 실제 계산할 때 n^2을 피할 수 없음.
풀이 구현 문제라 풀만하긴 한데, 코드가 깔끔히 짠다그래도 아직 부족하다. 다시한번 꼭 짜보자. 리팩토링 연습이다.
풀이 트리 구현을 한번도 안해보다가 처음으로 했다. 첫 시도에서는 바로 구현을 못하고 다른 코드를 참고 했다. 반복적으로 연습하면서 체득을 해야 겠다.
풀이 정말 미쳐버리겠다. 왜 구현을 못하지. 왜 while문으로 구현을 못하는 걸까. 푸는 방법 다 알아놓고. 미쳐버리겠다.
풀이 시뮬레이션 문제이다. 시뮬레이션 문제는 순서를 명확하게 이해하고 이를 지켜주는 것이 매우 중요하다.
풀이 가장 최소인 녀석을 계속해서 뽑아야 하기 때문에 heap 구조를 사용했다. 이 때 python으로 코딩을 하려한다면 무조건적으로 heapq를 사용할 것. priorityQueue는 속도가 너무 느려서 효율성 통과를 하지 못한다.
풀이 deque, heap을 통해서 구할 생각을 했다. 그런데 구현을 하는 점에 있어서 어떠한 요소가 필요하겠다고 생각하는 능력이 좀 떨어진다. 몇개의 변수를 사용하면 쉽게 구할 수 있다와 같은 판단을 하는 것이 모자라다.
풀이 좀 어려울 수 있지만, 시간 초과가 나면 무언가 규칙이 있다는 생각을 해보자. 일단 찾을 수 있는 규칙은 다음과 같다. 최소공배수로 나눈 작은 모양이 반복되어 발생한다.
풀이 아니, 갑자기 딕셔너리 소트 안되는게 말이냐구. 왜 다 풀줄 아는데 꼭 저런거 때매 문제일까. 더 많이 풀어서 오류를 판단하는 눈을 길러야 한다. Code def solution(genres, plays): # 속한 노래가 많이 재생된 장르를 먼저 수록.
풀이 순열로 해결했다. n이 작아서 가능했다. 순열로 가능한 순서의 모든 banned를 나열하고, 각각에 대해 가능한지 확인하여 문제를 해결했다.
풀이 그냥 풀었다.
풀이 어떻게 해야 이런 문제를 풀 수 있을까. 일단 조합과 같은 생각은 n이 작을 때 한다. 완전 탐색 방법을 먼저 생각한다.
풀이 일단, 200,000이라서 n^2은 안된다. 그러면 한번에 가야하는데, 이 때, 잘 살펴보면, 해당 스테이지에서의 실패율은 stage잔존 수/stage 통과수로 정의된다.
풀이 BFS로 풀었는데, 배열이 reference로 전달되어 애먹었다.
풀이 아무 생각 없이 재귀로 풀었다. 그냥 어느 위치에 있는지에 따라 값이 변하길래. 아마 최근에 정렬문제를 많이 푼 탓인가보다. 그래서 풀고나서 다른 분 코드를 보고 규칙을 나도 파악해 보기로 했다. 일단 사실 문제를 안읽었다.
풀이 쉬워서 패스. 해시사용 문제이다.
풀이 일단 input보고 항상 판단하는 것이 중요하다. 방향만 잘 잡으면 어느정도 풀 수 있다. 이제. 이분 탐색의 핵심은 결국 값을 제안하고, 그 값이 맞는지 틀린지를 검증하는 로직을 찾을 수 있냐는 것이다.
풀이1 이게 보면, 전화번호 개수가 백만개라 단순히 비교로 풀면 n^2이라 박살난다. 그렇기 떄문에 다른 방법을 고민해야한다. 이 문제의 핵심은 결국 특정 단어가 접두어로 있는지에 대한 문제이다. 그렇기 때문에 startswith를 생각하는 것이 편하다.
풀이 prices의 길이가 100,000이라 n^2으로 짜면 터질 것 같아 stack으로 구현했다. 그런데 이때, 특정 원소가 조사해야 하는 부분은 i+1부터 끝까지의 요소이다. 그 과정에서 중복이 발생하기 때문에 반대로 정렬한뒤 값을 구해주었다.
풀이 그냥 막 풀었다. 컨디션이 좋지 않다.
풀이 다익스트라로 한번에 성공했다. 그래도 발전이 있나보네. 스위프트로 플루이드 워셜로 다시 풀었다. Code # AB가 함께 모든 노드까지 가는데 걸리는 최단 거리를 구한다. # 그리고 그 거리 각각에서 출발하여 # 1.
문자열 처리는 파이썬으로 find() isalpha() isalnum() for ~ in list, string으로 하나씩 꺼낼 수 있다. ~ in list, string으로만 하면 t/f 반환한다.
What is pointer 포인터는 먼저 자료형으로 선언할 수 있다. 각각의 자료형에 대해 * 를 달게 되면 선언할 수 있으며.
기본 정보 발표년도 : 1991 설계자 : Guido van Rossum, 네덜란드 패러다임 : 절차적 프로그래밍, 함수형 프로그래밍, 객체 지향 프로그래밍 초보자부터 전문가까지 사용자층이 넓다. 다양한 플랫폼에서 쓸 수 있다. 라이브러리(모듈)이 풍부하다.
String 문자열 나누기 Pithon -> Python 으로 바꾸는 작업을 진행해보자. # 잘못된 예 a = "Pithon" a[1] = 'y' 불가능하다. 문자열의 요소값은 바꿀 수 있는 값이 아니다.
지금까지, 정수, 실수 문자열을 다루는 법을 배웠다. 그런데 하나의 값 말고, 여러개를 다룰 필요가 있다면 어떡해야할까? 이런 용도를 위해 python은 리스트를 제공하고 있다.
튜플(tuple)은 몇 가지 점을 제외하곤 리스트와 거의 비슷하다. 리스트와 다른 점은 다음과 같다. 리스트는 []으로 둘러싸지만 튜플은 ()으로 둘러싼다. 리스트는 그 값의 생성, 삭제, 수정이 가능하지만 튜플은 그 값을 바꿀 수 없다.
Dictionary 사람은 누구든지 “이름” = “홍길동”, “생일” = “몇 월 몇 일” 등으로 구분 할 수 있다. 파이썬은 영리하게도 이러한 대응 관계를 나타낼 수 있는 자료형을 가지고 있다.
모든 변수는 객체이다. 파이썬에서 사용하는 변수는 객체를 가리킨다. 여기서 객체란 파이썬에서 사용되는 모든 것 을 의미하는 말이다. 이게 무슨말일까? 이 개념에 대한 직관적인 설명을 잘해둔 페이지가 있어 여기 소개한다.
Function Design Recipe (FDR) 우리는 파이썬에서 제공하는 다양한 내장 함수들에 대한 설명을 보고싶을때, help() 함수를 통해 정보를 확인할 수 있었다.
C++과 약간의 차이를 기억해야 하는데, 가장 핵심적인 것은 OR, AND 를 그대로 갖다 쓴다는 것이다. C++에서는 각각 && , || 로 사용했는데, 이것을 AND, OR 로 사용하면 된다.
Python은 언어이기에 내장하는 기능들이 대부분의 프로그래머에게 필요한 필수적인 것들을 제공하고 있다. 따라서 특정 분야에서 필수적으로 필요로 하는 기능은, 분야에 제한적이기에 Python 언어에서 기본 내장하기가 어렵다.
format() print('{0} ate {1} apples {2}'.format('I', '3', 'yesterday')) print('{0} ate {1} apples {2}'.format('You', '5', 'at 2 pm')) print('{1} ate {0} apples {2}'.format('5', 'You', 'a...
컴퓨터를 통하여 문제를 해결하는 가장 중요한 이유 중에는 계속적으로 반복하는 작업을 컴퓨터가 대신 처리하여 주는 것이다. 이런 기능을 반복문이라고 하며, 대부분의 프로그래밍 언어는 다양한 반복문을 제공한다.
컴퓨터를 통한 문제 해결을 위해서 우리는 정수, 실수, 문자열 등을 프로그램 실행중에 만들어서 사용하였다.
Set set은 정렬되지 않은 수학의 집합과 동일한 개념의 데이터 타입으로서, 중복된 값을 가질 수 없다. 아래의 예제에서 exSet1은 set의 규칙에 제대로 부합하는 경우 이지만, exSet2는 중복된 아이템(‘p’)이 섞여 있는 것을 볼 수 있다.
클래스는 c++에서 자세히 다뤘으므로, 해당 내용에 대해 파이썬 문법만 알아보도록 하자.
정규 표현식은 다양한 언어에서 사용이 가능하다. 이 글에서는 파이썬을 기반으로 정규 표현식을 확인해 보도록 하자. import re p = re.compile('ab*') re.compile을 사용하여 정규 표현식(위 예에서는 ab*)을 컴파일한다.
개요 앞의 글에서 우리는 컴파일 된 pattern 객체의 메서드를 공부했다. 이 메서드에는 match, search, findall, finditer가 있었다. 해당 메서드들은 검색이 된 경우 match 객체를 리턴했다.
개요 지금까지는 간단한 정규식을 살펴 보았지만, 실제로 존재하는 다양한 문자열에서 정보를 뽑아내기 위해서는 추가적인 옵션이 필요하다. 예를 들어 쇼핑몰의 상품 리뷰를 사용자가 작성했다고 한다. 우리는 여기서 핵심적인 단어를 뽑아내야 한다.
앞에서 정규식을 표현할 때 우리는 \ 문자를 사용했다. 하지만 내가 정규식을 작성하는 데 있어서 \문자 자체를 찾고 싶다면 어떻게 해야할까? \section 이렇게 정규식을 작성하게 되면 문제가 발생한다.
특정 문자열이 반복되는지에 대해서 알기 위해서는 어떠한 정규식을 작성해야 할까? 우리가 앞에서 배운 내용으로는 할 수 없다. 이렇게 특정 문자열이 단위로 구성되어 검색을 진행하고 싶을 때 사용하는 것이 그루핑이다.
개요 Lookahead Assertions는 이해하기가 어렵다. 하지만 예시와 함께라면 어떤 경우에 이를 사용해야 하는지 알 수 있을 것이다.
개요 sub 메서드를 사용하면 정규식과 매치되는 부분을 다른 문자로 쉽게 바꿀 수 있다.
Greedy는 알고리즘 문제를 풀 때 보았던 용어이다. 이 용어는 어떤 의미로 사용이 될까? 무언가 탐욕적으로 한다는 의미일 것이다. 다음과 같은 문자열에서 처음 나오는 tag를 검색하고 싶다 해보자.
원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자 문자 클래스 [] [ ] 사이에 있는 각각의 문자들에 대해 적어도 하나가 매치가 되는가? 즉, 정규 표현식이 [abc]라면 이 표현식의 의미는 “a, b, c 중 한 개의 문자와 매치”를 뜻한다.
잘 사용하고 있던 Alfred workflow가 동작하지 않는다. Mac OS 12.3으로 업데이트하고나서 바로 이런 이슈가 터지다니. 속도가 안나 답답하다. Issue 원인 Apple에서 12.3부터 공식적으로 python 2을 지원하지 않는다고 한다.