[백준/python]2623번 음악프로그램 - topology sort
문제 출처 - https://www.acmicpc.net/problem/2623
Posts by Category
algorithm
[백준/python]21757번 나누기 - prefix sum, dp
누적합과 dp를 활용하여 풀어야 했는데 dp 점화식을 세우는 것이 생각보다 쉽게 떠오르지 않아서 당황했다. 현재 풀이보다 dp부분을 좀 더 깔끔한 코드로 작성할 수 있을 것 같다.
[백준/python]3020 개똥벌레 - prefix sum
석순과 종유석의 길이가 주어지면 석순과 종유석이 가장 적게 등장하는 구간을 찾는다.
[백준/python]2629번 양팔저울 - knapsack
백준 2629번 양팔저울 파이썬
[백준/python]2473번 세 용액 - two pointer
다양한 방법으로 풀 수 있다. 2470번 두 용액 문제의 풀이를 활용했다. 다른 테크닉 없이 모든 용액을 하나씩 고정해두고 해당 용액 다음으로 등장하는 용액들만 사용하여 투 포인터를 사용해서 풀면 된다.
[백준/python]1092번 배 - greedy
그리디 알고리즘은 간단하다고 생각하고 최근에 많이 풀지 않았는데 까다로운 문제가 많았다. 처음에는 배와 크레인의 무게를 오름차순으로 정렬하여 그리디하게 할당했는데 반례가 있었다.
[백준/python]10775번 공항 - union find, greedy
문제 링크 - https://www.acmicpc.net/problem/10775
[백준/python]1765번 닭싸움 팀 정하기 - union find
문제 링크 - https://www.acmicpc.net/problem/1765
[백준/python] 14003번 가장 긴 증가하는 부분 수열 5 - dp
가장 긴 증가하는 부분 수열 문제 중 가장 마지막 문제다. 주어진 수열의 길이가 작다면 dp를 이용하여 O(n^2)의 시간 복잡도로 해결하는 것이 일반적인 방법이다.
[백준/python]냅색 문제 2차원 배열 및 1차원 배열 정리, 1106번 호텔 - knapsack
냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다.
[백준/python]4358번 생태학 - string
python 포맷팅 - 소수점 자릿수 표현
[백준/python]1254번 팰린드롬 만들기 - string
python 문자열
[백준/python]5525번 IOI - string
stack에 I가 등장하면 인덱스를 push하고 stack의 원소의 차이가 2이상이면 답을 늘려가는 방식으로 풀 수 있다. 그러나 문자열 문제이기 때문에 split을 사용하는 방식으로 풀어보았다.
[백준/python]7579번 앱 - knapsack, dp
냅색 알고리즘에 해당 되는 문제이다. 냅색 알고리즘에는 가방에 보석을 담을 때 보석을 자를 수 없다고 가정하는 0-1 냅색 알고리즘과 자를 수 있다고 가정하는 Fractional 냅색 알고리즘이 있다.
[백준/python]2662번 기업투자 - knapsack, dp
0-1 냅색 문제다. 냅색 알고리즘 유형을 분석하고 풀었더니 생각보다 쉽게 풀 수 있었다.
[백준/python/오답]1493번 박스 채우기 - divide and conquer
```python box=[] l,w,h = map(int, input().split()) N = int(input()) for i in range(N): box.append(list( map(int, input().split()) )) sol = 0 def dividin...
[백준/python]16236번 아기상어 - bfs, implementation
BFS를 사용하는 구현 문제이다. 조건이 다양하기 때문에 주의해서 풀어야 한다.
[백준/python]7569번 토마토 - bfs
3차원 그래프 문제다. 이미 익은 토마토를 기준으로 BFS를 실행하면서 총 소요되는 시간을 더해준다.
[백준/python]9663번 N-queen - backtracking
백트래킹의 대표적인 예제다. 넴모넴모 문제를 풀고 풀어서 모든 격자를 방문하며 가로방향, 세로방향, 대각선 방향을 체크하는 방식의 풀이를 생각했었다. 상당히 복잡하고 시간도 오래 걸렸다. 많은 시행착오 후에 각각의 행과 열에는 오직 1개의 퀸이 올 수 있다는 것을 생각해낼 수 있었...
[백준/python]2580번 스도쿠 - backtracking
스도쿠 문제다. 스도쿠 문제를 풀어봤다면 백트래킹으로 풀어야 된다는 생각이 자연스럽게 떠오를 것 같다.
[백준/python]1987번 알파벳 - backtracking
보드를 방문하며 해당 보드를 방문한 적이 있는지, 해당 알파벳을 이미 마주친 적 있는 지만 확인해주면 된다. DFS를 이용한 백트래킹으로 간단하게 구현했다.
[백준/python]14712번 넴모넴모(Easy) - backtracking
```python #넴모넴모(easy) , backtraking
[백준/python]15649번 N과 M (1), 15650번 N과 M(2) - backtracking
N과 M 문제를 통해 백트래킹을 익혀보자.
[백준/python]1182번 부분수열의 합 - backtracking
N과 M 문제보다 먼저 풀었다. 백트래킹에 대한 개념을 몰라서 백트래킹 문제 중에서도 상대적으로 쉬운 문제였지만 시간이 꽤 걸렸다. 첫 풀이도 백트래킹이지만 다른 사람들의 코드를 참고하여 더 간단하게 풀 수 있음을 알게 되었다. 코드
[백준/python]15732번 도토리 숨기기 - binary search
1300번 문제 K번째 수와 유사한 문제이다. 어떤 것을 기준으로 이분 탐색을 할 지 찾는 것이 중요하다.
[백준/python]15686번 치킨 배달 - implementation
문제를 풀다보면 조합이 필요한데 이 때 가장 많은 의문이 들었다. 하지만 구현 문제라는 것을 알고 풀었기 때문에 차근차근 코드를 작성했다. https://gudals113.github.io/algorithm/acmicpc-21608/ 21608번 상어 초등학교 문제 풀 때도 그랬지...
[백준/python]21608번 상어 초등학교 - implementation
구현 문제는 코드를 작성하면서도 너무 복잡한 것 아닌가 하는 의문이 든다. 그러나 의문을 뒤로 하고 일단 끝까지 풀 수 있다.
[백준/python]2001번 보석줍기 - bfs, bitmasking
이제 비트마스킹은 그만 풀어야겠다. 2001번 보석줍기 문제는 주어진 테스트 케이스가 많이 없었고 오류를 찾지 못해서 5시간은 걸린 것 같다.
[백준/python]10816번 숫자 카드2 - binary search
10815번의 변형 문제이다. 해당 문제를 푸는 여러 풀이가 있지만 어떤 풀이를 선택하든 딕셔너리(해쉬맵)을 사용해야 시간 내에 풀 수 있다.
[백준/python]1194번 달이 차오른다, 가자 - bfs, bitmasking
처음에 비트마스킹을 잘못 이해했다. 보유할 수 있는 열쇠의 경우의 수를 비트마스킹으로 표현했다. (7bit)
[백준/python]2133번 타일 채우기 - bitmasking
매 열마다 3개의 타일이 있다.채워진 타일을 1, 채워지지 않은 타일을 0으로 표시한다.
[백준/python]2098번 외판원 순회 - bitmasking
알고리즘분석 시간에 배웠던 NP 중 하나인 TSP 문제다. N이 작은 경우 DP와 비트마스킹을 통해 풀 수 있다.
[백준/python]2178번 미로탐색 - bfs
prev에 경로를 저장하고 BFS를 돌렸다. BFS가 끝나면 prev를 거꾸로 돌아가며 지나온 개수를 구한다. 돌아가는 과정이 비효율적이다.
dev
비트코인 트레이딩 봇 만들기(1)- pyupbit, 잔고 조회 및 백테스트
지난 글에서는 Upbit API 공식 문서에서 잔고와 마켓에 대한 정보를 불러오는 법을 알아봤다. 이번 글에서 부터는 python 라이브러리인 pyupbit를 통해 더욱 쉽고 간편하게 다양한 정보와 자동 매매를 위한 코드를 작성해보자. pyupbit 라이브러리 사용하기
비트코인 트레이딩 봇 만들기(0)- python, Upbit API
얼마전 유튜브를 보는데 홍준표 국민의힘 대선 경선 후보가 SNL에 나와서 인기를 얻었다. 조회수 200만이 넘었다. SNL에서도 냄새를 맡았는지 정치인들이 계속해서 출연하고 있다. 이번에는 이준석 국민의힘 당대표가 나왔다. 비트코인 얘기를 하는데 자동투자로 선거 세네 번 치를 비용...
cs
[네트워크/CS]프로토콜 계층화란?
0. 시작하기에 앞서 데이터그램은 어떤 레이어의 PDU인가?
[운영체제/OS]Operating System Concepts - 공룡책 개념 정리(2)
Chapter2. 운영체제 구조
[운영체제/OS]Operating System Concepts - 공룡책 개념 정리(1)
Chapter1. 서론
life
안녕하세요 개구리입니다.
개발 블로그 시작했습니다.