전체 글 (64) 썸네일형 리스트형 유노윤호 명언 모음 명언시작 세상에서 가장 해로운 벌레는 대충 우리 인생은 수도꼭지와 같다. 녹물부터 나온다고 두려워 하지 말고, 곧 깨끗한 물이 나오니까 받아들이고 잠그지말자. 넌 세계로 뻗어나갈 아이야 오늘 하루 특별하게 만들어야지 저는 그 한계에 지고 싶지 않아요. 네 꿈을 펼쳐 봐 내가 무대 한번 찢어야겠다!! 유노윤호의 명언은 그의 말이 아니라, 그의 삶이었기 때문이다. 미래는 예측할 수 없지만, 창조할 수 있습니다! 시작을 주저하지 않았으면 좋겠다. 흙을 밟으면 흔적이 되고 길이 되지 않냐. 흙을 밟는게 두려울 수 있지만 한번 밟으면 곧 자신의 길이 되어 있을 것이다. 어떠한 선택을 했을 때, 그 선택이 실패라도 경험이 될 거고, 그 실패로 인해서 성공이 올거라는걸 믿고 있어요. '하다보면 답이 나올거다' 그러.. Codeforces Round #694(Div. 2) 리뷰 1. 최종 결과 Rank : 4976/22818 Performance : 1283 A : WA on Test 4 B : AC C : AC D : Unsolved E : Unsolved F : Unsolved 2. 문제풀이 A Strange Partition tags : greedy, math, number theory 문제 : x와 배열의 길이 n이 주어질 때, beauty of array는 $\sum_{i=1}^k \lceil \frac{b_i}{x} \rceil$으로 결정된다. 해당 리스트에 인접한 두 원소를 더해서 배열의 길이를 줄여줄 수 있다. 모든 경우에서의 beauty of array의 최댓값과 최솟값을 구해라. 풀이 : $\lceil \frac{a+b}{x} \rceil \le \lceil .. 시간 복잡도 1. 문제 : 백준 - 주사위 윷놀이 www.acmicpc.net/problem/17825 2. 틀린 이유 : 주어진 이동횟수 또한 바뀔 것이라 생각해서 10! * 4^10의 시간복잡도를 계산하고도 완전 탐색으로 풀려고 했다. 실제로는 4^10만 계산해서 완전탐색으로 풀 수 있는 문제이지만 풀이를 구상하기 전에 시간복잡도를 먼저 계산하고 맞는 풀이인지 검토하려는 노력이 필요하다. 3. key idea : 4^10(1,048,576), 10!(3,628,800) -> 대충 계산할 수 있는 능력 다 백만 안쪽으로 계산된다. 4. 알아두면 좋을 것 : (1) 실제로 10! * 4^10으로 해당 문제가 나왔다면 어떻게 계산해야될까? -> dp를 이용하면 될듯한데,,,조금 더 생각해보기 (2020.12.30. 추.. 시뮬레이션에서 문제 조건을 잘못 읽은 문제 1. 문제 : 백준 - 이상한 게임 2 www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 2. 틀린 이유 : 빨간색 격자에서의 조건을 잘못 봤다. 밑의 말부터 위의 말 순서대로 적어 놓은 것을 캐치하지 못하고 다른 조건으로 2시간 동안 붙잡고 풀었음. 3. key idea : 문제를 꼼꼼히 읽는 것 말고는 답이 없는 듯. 더군다나 규칙이 복잡한 문제는 코딩에 들어가기 전 조건들 모두 적고 이후에 잘못됐을 때 비교할 수 있는 표를 만들 것 시뮬레이션 재귀 때 map 원래 상태로 복귀 1. 문제 : 백준 - 2048(Easy) www.acmicpc.net/problem/12100 2. 틀린 이유 : 재귀에서 이전 상태를 저장하는 tmp array를 전역 변수로 선언. DFS가 진행됨에 따라서 tmp 상태도 함께 바뀌게 되어 이전 값을 올바르게 저장할 수 없다. 3. key idea : tmp array를 DFS 함수 안에서 선언한다. 함수가 끝날 때 자동으로 없어지기 때문에 서로 영향을 받지 않음. 4. 알아두면 좋을 것 : (1) array를 지역 변수로 선언했을 때 다른 함수에서 인자로 받는 방법 int (* tmp)[21] 이렇게 선언해주면 된다. array 하나가 pointer를 의미하므로 2차원의 경우에는 [21]을 뒤에 붙여주면 된다. 3차원의 경우에는 int (* tmp).. Graphs 1. Definition and terms Graph (V, E)는 set of vertices V와 set of edges E로 이루어져 있다. vertex는 하나의 node 점을 의미하고, edge는 vertex끼리 이어진 선을 의미한다. # of Vertices는 |V| # of Edges는 |E| 이다. Path : Vertices의 sequence와 n-1개의 edge로 이뤄진 집합을 의미한다. simple path : Path를 이루는 모든 vertices가 distinct한 것을 뜻한다. Cycle : $v_1$에서 시작하여 자기 자신으로 돌아오는 길이가 3 이상인 path를 뜻한다. Simple Cycle : 처음과 끝을 제외하고 모든 vertices가 distinct한 것을 뜻한다. Co.. Searching 1. Searching Ordered Arrays 만약 element가 정렬되어 있지 않다면, linear search($\Theta(n)$)가 가장 최선의 선택지이다. 정렬이 되어 있다면 Binary Search($\Theta(log n)$)이 linear search보다 낫다. 하지만 우리가 사전에 데이터의 분포와 사용 패턴을 알고 있다면 Binary Search보다도 더 좋은 Search Algorithm을 찾을 수 있다. 1-1. Jump Search k의 범위를 두고, L[0], L[k-1], L[2k-1]...을 순차적으로 방문하며 해당 값이 찾고자 하는 값 K보다 큰지 작은지를 검사한다. 해당 값이 K보다 크다면 계속해서 jump search를 진행하고 아니라면 이전의 값으로 돌아가 Line.. Internal Sorting 각각의 sorting algorithm을 비교하기 위해 # of comparison, # of swap을 기준으로 삼는다. 1. $\Theta(n^2)$ Sorting Algorithms 1-1. Insertion Sort (1) 초기에 output은 비어있다. (2) 각각의 item을 알맞은 장소에 삽입한다. static 이전 1 2 3 4 ··· 8 다음
