[백준 #2565 파이썬] 전깃줄
2023. 1. 4. 12:03
Algorithm
생각은 맞았지만 생각을 전개하는 방식에 문제가 있었다. 이 문제를 다시 푸는 경우에는 증가하는 수열에 대한 개념을 먼저 알고 푸는 것이 도움이 될 듯하다. 생각 1. 교차하는 방법을 정리한다. 2. 순서대로 정렬하여 교차가 발생하는 지점을 센다. 일단은 생각대로는 풀었지만, 그 생각이 결국 수정이 필요한 생각이었다. 구현 (수정이 필요했음) 1. 최대 번호에 맞는 배열 크기를 초기화 한다. 2. 전깃줄을 정렬한다. 3. 시작과 끝 지점을 저장해 정렬한다. 이때 시작지점이 기존 값보다 크면서(작으면서) 도착 지점이 기존 도착 값보다 작으면(크면) 교차가 발생한다. 이때, 기존 값에 count 1을 더해준다. 그렇게 나온 제거가 필요한 위치를 세어준다. 여러 반레도 맞추고 예제도 맞출 수 있었지만 9%만 달..
[백준 #2580 파이썬] 스도쿠
2023. 1. 3. 13:00
Algorithm
으음 반은 풀고 반은 몰랐던 문제 보자마자 이건 백트래킹이다! 라고 생각할만한 요소가 많았다. 한 칸에 여러 경우의 수가 올 수 있었고 그 수가 완성이 되어야 최적의 값을 탐색할 수 있다는 점은 당연히 백트래킹을 연상할 수 밖에 없었다. 그런데 어떻게 푸냐가 항상 문제지 ㅎㅎ 생각 그래서 그냥 스도쿠를 푸는 방식을 먼저 생각해봤다. 1. 가로 2. 세로 3. 3 * 3 사각형 내 가장 기본적으로 생각해볼 수 있는 방법이었다. 이제 구현하는 과정에서 bfs를 줄기차게 풀던 시절을 떠올리며 문제를 풀어보았다. 우선 0인 값을 모두 찾아 저장해준다. 그리고 그 값들마다 저 세개의 검증 과정을 거치자 그런데 함수를 구현하는 방법에서 스도쿠 숫자 1~9까지 탐색하는 방법에 고민이 많았다. 첫째는 각 함수마다 없는..
[백준 #12865 파이썬] 평범한 배낭
2023. 1. 2. 13:37
Algorithm
냅색 알고리즘의 가장 기본이 되는 문제다! 어렵게 느껴지는 유형 중 하나다. 이러한 문제를 푸는 방법에 있어 가장 중요하게 생각해야 하는 부분이 있다. 1. 변화를 감지하는 방법 2. 변화를 기록하는 방법 어찌보면 dp 와 맥락을 같이 하고 있다고 생각하면 된다. 생각 1. 순서에 상관 없이 최적의 값을 도출할 수 있어야 한다.(정렬을 사용하지 않는다.) 2. 제한 무게 내에서, 이전 결과의 최적 값과 현재 결과값 + 더할 무게의 가치 를 비교한다. (이해가 안된다면 아래에서 설명!) 사실 이전에 풀어봤던 내용이라 지금은 쉽게 방법을 떠올릴 수 있다. 하지만, 처음 봤을 때는 생소하고 전혀 방향을 잡지 못했기 때문에 기억해 두는 것이 좋을 듯 하다. 구현 1. DP테이블을 구체적으로 만든다. 일반적으로 ..
[백준 #2589 파이썬] 보물섬
2022. 12. 26. 11:20
Algorithm
bfs를 연습해보기 가장 적절한 문제라고 생각한다! 아마 실버에서 골드정도로 올라갈 때 가장 적합한 문제? 기초 예제문제정도로 생각된다! 생각 1. 어떤 지점이 시작지점인지 모른다. 2. 어떤 지점이 끝지점인지 모른다. 구현 전체 탐색을 해야만한다. 방문 여부 처리를 해야 한다. 값 갱신 처리를 해야 한다. 모든 bfs결과값을 저장하고 그중 최대값을 뽑기만 하면 된다. from collections import deque n,m = map(int,input().split()) field = [list(map(str,input()))for _ in range(n)] ans = [] dx = [1,0,-1,0] dy = [0,-1,0,1] def bfs(a,b): q = deque() q.append((a,..
bfs & dfs 문제를 풀 때 유의해야 할 점들 (생각해보며 업데이트!)
2022. 12. 26. 11:18
Algorithm
리스트가 범위 밖을 나가는 경우 진짜 나가게 설정했거나 배열이 제대로 선언이 잘 된건지 확인해봐라 방문여부 처리 방문여부 처리가 반복적으로 초기화되어야 하지 않는지 살펴보기 dfs 와 bfs 연계 둘을 연계해야 하는 문제일 수도 있다. 값 갱신 값이 갱신되어야 하는 방식에 어떤 문제가 있는 지 살펴보기
[백준 #2206 파이썬] 벽 부수고 이동하기
2022. 12. 23. 17:05
Algorithm
이건 사실 내가 풀었다고 할 수 없는 문제였다! 결정적인 풀이는 참고를 했기 때문에 ㅎ 다만 기록과 반성을 위해서, 그리고 새로운 bfs 풀이에 대한 개념을 위해서 작성하는 오답노트 생각한 문제 1. 어떤 벽에 1을 써야 하는가, (아예 막혀 무조건 뚫어야 하는 경우, 무조건 뚫지 않아도 되는 경우로 구분해서 생각을 시작했다) 2. 두개이상의 방향으로 나아갈 수 있다면 어떤 방법으로 가는 것이 좋은가? 구현 사실 2번은 어느정도 경험해 본 문제였다! 풀던 방법은 1. 이동하는 케이스의 경우 cnt 변수를 만들어서 하나씩 더해주는 방식 2. max나 min을 값을 비교하며 갱신하는 방법 3. 현재 위치의 값에서 1을 더해서 이동하는 값에 대입해주는 방식이었다. 그래서 이러한 방식으로 어느정도 해결법을 찾아..
[백준 #2573 파이썬] 빙산
2022. 12. 22. 12:45
Algorithm
빙산 문제도 연구소와 어느정도 비슷한 점이 많다고 생각했다. 생각해야 하는 부분들 1. 얼음이 모두 녹는 경우 음수가 되어서는 안된다. 2. 녹아서 물이 된 경우,그 결과는 바로 반영되는 것이 아닌 내년에 반영된다. 3. 두동강이 나면 끝난다. 4. 아예 녹으면 끝난다. 예전에 구름 알고리즘 챌린지에서 비슷한 문제를 풀어본 경험이 있다 (단풍나무 문제 링크가 있으면 추가해드릴게요!) 여기에서 1, 2번 문제를 해결했던 경험이 있어 이를 활용하고자 했다 구현 1 해결 : max 활용 어쩌면 dp를 하면서 가장 많이 봤을 키워드였다. 하나의 빙산의 숫자가 2이고 3면이 바다인 상황을 가정해보자. 그러면 bfs를 돌리면 -1이라는 값이 된다. 하지만 max(0,현재 빙산 숫자 - 접하는 면의 바다)라는 로직을..
HTTP 버전
2022. 12. 21. 15:34
CS
HTTP 1.0 한 연결당 하나의 요청을 처리한다. RTT(Round Tip Time, 패킷이 목적지에 도착하고 나서부터 출발지로 돌아오기 전 까지 걸리는 시간 = 패킷 왕복시간)의 증가 TCP - 3 way handshake를 서버로부터 파일을 가져올 때마다 하기 때문에 RTT시간이 증가한다. RTT 증가를 해결하기 위한 방법 이를 이미지 스플리팅, 코드 압축, 이미지 BASE 64인코딩을 활용해 해결한다. 이미지 스플리팅 많은 이미지를 다운로드받으면 과부하가 걸려 이미지가 합쳐진 하나의 이미지를 다운받고 이를 기반으로 Background 이미지의 Position을 이용해 이미지를 표기한다. 코드 압축 코드를 압축해 개행 문자, 빈칸을 없애 크기를 최소화한다. 이미지 BASE 64 인코딩 이미지 파일을..