PS 기록 18

AtCoder ABC #309 UpSolving + 첫 앳코더 후기

더보기 1. 앳코더를 신청한 계기 BOJ 문제를 100일 넘게 꾸준히 풀면서 점점 문제 푸는데에 긴장감이 없어지는 것 같았다. 시간 제한이 있는 것도 아니고, 내가 풀고 싶은 시간 아무때나, 난이도를 자유롭게 골라서 풀면 되는 점이 오히려 역효과로 작용했다. 이 역효과에 대해 좀 더 자세히 설명하자면, 내 컨디션에 맞춰서 문제 풀이가 느슨해진다는 점이다. 매일 어려운 문제, challenging 한 문제, 새로운 알고리즘에 도전해야 실력이 빨리 늘텐데 앞으로 나아가기 보다 쉬운 문제를 풀면서 제자리에 안주하는 느낌이 들기 시작했다. 별로 배운 것도 없는 수준이고, 다른 사람들이 웰노운이라고 말하는 것조차 다 소화하지 못했는데도 내가 피곤하다는 이유, 시간이 모자라다는 이유 등으로 새로운 것을 배우는데에 ..

PS 기록/CP 2023.07.09

23년 1학기 PS 회고록

종강 기념으로 23년 1학기 (학기 병행) PS 회고록을 쓴다. 23.02.28 기준 165 문제를 solved, 현재 23.06.29 기준 347 문제를 해결했다 한 학기 (3월-6월) 동안 347-165=182 문제를 풀었다! 다행이도 개강 전에 세웠던 소소한 목표는 모두 달성했다. 1. 종강 전에 G2 달성 -- completed! 2. 스트릭 Day 100+ 달성, 유지 -- completed! 솔직하게 말해서, 1학기를 돌아보니 아쉬운 점이 너무 많다. 학교 생활에서 아쉬운 점도 물론 있지만, PS 중심으로 내 성취를 다시 돌아보았을 때 너무 많이 아쉬운 게 있어서 이를 차근차근 정리해보려고 한다. 아쉬운 점 1. 새로운 알고리즘을 많이 소화하지 못한 것 - 알고리즘 수업에서 Backtracki..

PS 기록 2023.06.29

최단거리 : 다익스트라 Dijkstra (Python)

다익스트라(또는 데이크스트라) 알고리즘은 특정한 시작점에서 다른 모든 점들로 가는 최단거리를 구하는 알고리즘이다. 그래프 내에서 시작점과 연결되지 않은 노드가 있을 수도 있다. (최단 거리를 구할 수 없는 노드) 이렇게 연결되지 않은 경우를 나타내기 위해 거리를 나타내는 배열 dist = [ ] 의 초기 값을 INF (매우 큰 수)로 설정해주는 것이 일반적이다. 물론, 여러 간선의 가중치 합이 아무리 커도 INF 보다는 작을 것이라는 제한 조건이 붙어야 한다. 이렇게 구현하면, if dist[node] == INF 일 때, 시작점과 해당 노드가 서로 연결되지 않아서 최단 거리를 구할 수 없다는 뜻이 된다. 본격적으로 다익스트라 코드를 구현해보자. 제대로 공부하기 전에 구현된 코드를 복사해서 쓰지 말고, ..

PS 기록/Algorithm 2023.03.30

이진 탐색 Binary Search (Python)

이진 탐색은 이미 순서대로 정렬된 arr에서, 특정 값을 보다 빠르게 찾기 위해서 사용되는 방법이다. 처음부터 차례대로 탐색하는 순차탐색 O(N) 과 다르게, 중앙값 mid 를 기준으로 나눈 arr에서 target이 앞/뒤 중 어디에 위치하는지를 찾는다. 이진 탐색의 시간 복잡도는 O(log N) 으로, 보다 빠른 탐색이 필요한 PS에서 유용한 라이브러리로 사용할 수 있다. 이진 탐색 함수를 짤 때 두 가지 방법으로 짤 수 있다. 하나는 재귀적으로, 남은 하나는 반복적으로 짜는 방법이다. 간단하게 PS 용으로 쓰기 위해서는 반복적인 방법을 주로 사용한다. 코드 짜기 쉽고, Python의 재귀 깊이를 고려하지 않기 위함이다. 또한, 이진 탐색 코드를 짤 때 주의할 점이 있다. (1) 탐색을 진행할 arr가..

PS 기록/Algorithm 2023.03.26

겨울 방학 사이의 꾸준함을 기록하다

오늘은 2월 마지막 날이고, 내일 3월이 되면 이제 개강이다!! 본격적으로 학기를 시작하기 전에 겨울 방학 동안 스스로 세운 목표를 잘 이뤄서 뿌듯했고, 전체적인 회고록을 작성하게 되었다. 백준 (Solved.ac) 기준 티어 골드 달성하기 PS 시작하고 하루도 빠짐 없이 문제 풀기 코딩 테스트 기본기 실력 쌓기 자료 구조 / 알고리즘의 기본적인 내용 1회독 하기 => 23-1학기를 위한 예,복습 CS 지식 쌓기 => CS 책 구매해서 읽기, 기술 블로그 읽어보기 그리고 1, 2, 3, 4, 5 번을 모두 달성했다!! 내가 엄청난 천재는 아니지만, 꾸준히 하면 이룰 수 있을 것 같다고 생각해서 이렇게 정했다. 처음 PS를 시작하는 거라서 혹시 높게 목표를 잡은 건 아닐지 걱정도 했..

PS 기록 2023.02.28

Heap, Priority Queue (우선순위 큐)

1. Heap Heap : 무더기, 더미를 의미함 컴퓨터 기억 장소에서 일부분이 프로그램에 할당 되었다가 회수되는 작용이 되풀이되는 영역 Heap의 기억장소는 대부분 Pointer 변수를 통해 동적으로 할당받고 돌려줌 아래 메모리 구조 그림을 참고 2. 자료구조 Heap 자료구조로 쓰이는 Heap: 데이터에서 최댓값, 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리: 자식노드가 왼쪽부터 꽉 채워지는 트리 부모 노드 index = 자식 노드 index // 2 Left 자식 노드 index = 부모 노드 index * 2 Right 자식 노드 index = (부모 노드 index * 2) + 1 배열로 구현할 때 index 1부터 시작하는게 편함 3. Heap 사용 이유 배열에서 max,..

PS 기록/Algorithm 2023.02.17

한 달 동안 백준 골드 달기

백준 골드 찍은 것이 큰 자랑거리는 아니지만, 그래도 그동안 열심히 했다는 뿌듯함이 느껴졌고 이 감정을 글로 남겨보고 싶어서 적게 되었다. 이번 겨울 방학엔 정말 작은 무언가라도 제대로 해봐야겠다고 생각했다. 이제 슬슬 사회로 나갈 준비도 해야하니 코딩 테스트 연습을 하자고 다짐했다. 처음에는 무작정 백준 문제 박치기로 시작했다. 쉬운 문제부터 할 수 있는 것들 위주로 풀었던 것 같다. 그러다가 실버 티어 문제에서 한계가 왔다. 내가 알고 있는(자력솔로 소화할 수 있는) 자료 구조/알고리즘 내용은 실버까지였다. 좀 더 공부해야겠다는 생각이 들어 자료 구조, 알고리즘 심화 내용 병행을 시작했다. 이번에 골드를 달성하면서 느낀 점은 "적절한 방법으로 꾸준히 시간을 투자하면 무조건 실력이 는다."라는 것이다...

PS 기록 2023.02.13

Codeforces Round #851 (Div. 2) 코드포스 첫 도전 후기 + C번 자력솔 [23.02.09]

1. 첫 도전 후기 코드포스에 도전해봐야 겠다고 마음먹은 이유는 바로 백준 사이트에 있다. 백준 랭킹을 보면 닉네임이 Bold + 화려한 색으로 꾸며진 사람들이 있다. 보고 너무 신기하고 멋있어서... 무엇을 하면 저런 닉네임을 받을 수 있지? 궁금증이 생겼다. 그렇게 구글링을 하면서 알아본 결과 외부 사이트의 랭킹, 레이팅을 끌어온 것이라는 걸 알게 됐다. 처음에 코드포스만 서치에 걸려서 코드포스를 준비해야겠다고 마음 먹었다. (처음 마음먹은 건 1월 중순?) n일에 한 번씩 코드포스 사이트에 들어가서 일정을 확인했다. 사실 쫄보+뉴비+자신감 부족 등등.. 여러 요인으로 인해서 첫 시험으로 div. 3이나 div. 4를 치고 싶었는데 OMG(엄마엄마갓) 내가 코포 도전 결심을 너무 늦게 하는 바람에 쉬..

PS 기록/CP 2023.02.11