링크 https://www.acmicpc.net/problem/1647 난이도(solved.ac 참고) 골드4 풀이 최소 스패닝 트리와 크루스칼 알고리즘을 공부한 뒤에 가볍게 풀어본 문제인데, 재밌었다. 최소 스패닝 트리는 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이며 가중치의 합이 최소인 그래프이다. 그리고 이 최소 스패닝 트리에 관한 알고리즘으로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 그래프에서 A와 B를 선택했을 때 A에서 B로 가는 경로가 반드시 존재하도록 최소 비용으로 간선을 배치하는 경우의 수에 관한 알고리즘이다. 이 알고리즘의 지향점은 당연히 최소 스패닝 트리를 만족하면서 가중치의 합이 최소가 되게끔 하는 것이다. 일반적인 크루스칼 알고리즘의 기본 ..

링크 https://www.acmicpc.net/problem/22846 난이도(solved.ac 참고) 골드3 풀이 처음에는 링고와 칼리가 보는 모니터가 각각 따로 있는 줄 알았다. 그랬는데, 다시 보니까 두명이 같은 모니터를 보고 있었고, 그 상황에서 약수를 더해주는 것이었다. 문제가 감이 안와서 유형을 봤는데 게임 이론이었다. 내가 경제시간에 배운 게임이론은 매 상황마다 자신에게 최대한으로 유리한 결정을 내리는 것에 대한 이론으로 기억했다. 일단 트리를 그려봤다. 첫 시작은 칼리이므로 칼리는 무조건 1을 더해 2가 될 것이다. 이제 그 다음부터가 시작이다. 각자는 K가 무엇인지 알고있다고 가정했다. 그래야 그에 맞는 최선의 전략을 선택한다는 말이 맞기 때문이다. K가 2일 경우부터 생각해보자. 그러..

링크 https://www.acmicpc.net/problem/1238 난이도(solved.ac 참고) 골드3 풀이 다익스트라 이론을 접하고 백준에서 기본 문제들(1753 최단경로, 1916 최소비용구하기, 18352 특정거리의도시찾기)을 풀었는데, 이론만 알면 그냥 풀 수 있는 문제였어서 재미가 없었다. 그래서 더 난이도가 높은 문제들 중 제출 횟수가 많은 이 문제를 선택했다. 다익스트라 함수의 기본 틀은 거의 같다. 다익스트라 함수를 어떻게 활용하는지가 중요한 문제였다고 생각한다. 물론 이 문제도 다익스트라의 기본 개념만 알면 어렵진 않다. N개의 숫자로 구분된 각각의 마을에 한 명씩 살고 있다고 했다. 그러므로 1부터 n의 범위를 갖는 for문을 돌면서 다익스트라 함수를 실행한다. 여기서 중요한 부..

오늘은 기존에 쓰던 react-simplemde-editor 마크다운 에디터를 버리고 toast-ui 에디터로 바꾸었다. 다른 건 다 그렇다 치는데 Next에서 렌더링이 안되었고 그 해결책을 찾기가 어려웠다. 그래서 바꾸고 난 뒤에 Next에서 사용할 수 있게끔 처리를 해서 페이지에 띄우는 데는 성공하였다. 이제, 용어의 이름과 마크다운 각각에 대해 값이 들어가있는지의 여부를 파악하는 useState Hook을 두가지 만들었다. import React, { useState, useCallback } from 'react' const TermRelated = () => { interface ITerms { id: number text: string } const [inputTerm, setInputTerm..

이 껍데기는 완성이 된 상태이고, 관련용어 추가 기능 구현도 전부 되어있다. 그래서 '저장하기'를 활성화하기 위한 조건에 대해 코드를 짰다. 아래에 적을 세 가지 조건을 각각 컴포넌트로 만들어서 처리를 할 것인지, 아니면 한 컴포넌트에 몰아넣고 한꺼번에 관리할 것인지에 대한 고민이 생겼다. 우선 '저장하기'를 통해 데이터에 저장이 되려면 기본적으로 두 가지 조건이 충족되어야 한다. 추가할 용어 (용어의 칸이 비워져있지 않아야 함) 마크다운 (마크다운 에디터 내의 값이 비워져있지 않아야 함) (옵션)관련 용어 추가 (글 작성 당시에는 필수 요소가 아님) 그래서 우선은 axios 처리를 위해 아래의 세 가지 과정이 필요하다. 1. '추가할 용어' input에 추가되는 값(e.target.value)을 그대로..

링크 https://www.acmicpc.net/problem/18352 난이도(solved.ac 참고) 실버2 풀이 1: BFS 활용 일반적인 BFS문제와 같으나 방문하지 않았을 경우 방문처리 하고 그 위치까지의 거리를 +1을 해준다. 그 뒤 +1해준 거리가 목표 거리 K와 같아질 경우 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다. 풀이 2: 다익스트라 알고리즘 활용 13행 for문 내부 append에서 가중치를 1로 두고 넣었다. 거리와 현재 노드의 위치를 순서대로 힙에서 빼낸 뒤 cost에 현재까지의 거리(dist) + 가중치 를 넣는다. 여기서는 가중치가 1이므로 +1씩만 더해졌다. 현재 distance의 기본값이 10^9이므로 모든 위치..

프론트 파트를 담당하고 진행하면서, 리액트나 타입스크립트 때문이 아니라 CSS 때문에 골치가 아팠다. body에서 지정한 width를 넘어갔을 때 저렇게 각자가 원래 가져야 할 width가 무너졌고, 다음 줄로 넘어가게 해야 했는데 그냥 끝없이 width를 먹어가면서 길어졌었다. 사용자 입장에서 보면 누가 저렇게 바뀌는 걸 좋아할까 싶었다. 그래서 CSS를 찾아봤고, 두 가지 결론에 도달했다. 1. min-width: fit-content 이 성질을 li 태그에 주고 나서 아무리 길어져도 본래의 li 태그 각각이 가지는 width 성질을 그대로 보존할 수 있게 되었다. 길게 쓰려면 쓸수야 있겠으나, mozilla에 잘 설명되어 있으므로 따로 설명하지 않고 넘어간다. 2. overflow: x-scroll..

링크 https://www.acmicpc.net/problem/2579 난이도(solved.ac 참고) 실버3 풀이 세번째 계단까지는 명확하다. 첫 번째 계단: 그냥 한 칸 오르는 게 최대값 두 번째 계단: 두칸을 차례대로 오르는 게 최대값 세 번째 계단: 첫 번째 계단과 두 번째 계단 중 더 큰 값을 갖고 있는 계단에서 올라오는 게 최대값 이제 네번째 계단부터는 일반화를 해야한다. 세 개의 계단을 동시에 오를 수 없으므로, 두 번째 계단에서 두 칸을 오르는 것과 세 번째 계단에서 두 칸을 오르고 첫 번째 계단에 도달한 뒤 거기에서 한 칸을 오르는 것 중에서 더 큰 값이 최대값이 된다. 이를 도식화한 것이 아래의 코드이다. for i in range(3, n): dp[i] = max(dp[i-2], dp..

링크 https://www.acmicpc.net/problem/1793 난이도(solved.ac 참고) 실버1 풀이 어제 포스팅한 바닥 공사 문제와 같아서 title 함수에 대한 코드는 별로 필요없을 것 같고, while True만 보면 될 것 같다. 이 문제는 특이하게 n이라는 값을 따로 지정해주거나 하지 않고, input값이 들어올 때마다 그에 따른 반환값을 계속 출력하도록 하였다. 이부분은 몰라서 구글링한 동아리원한테 들어서 그대로 썼다. while True: try: print(title(int(f()))) except: break try 블록 수행 중 오류가 발생하면 except 블록이 수행된다. 하지만 try 블록에서 오류가 발생하지 않는다면 except 블록은 수행되지 않는다. 즉 별 일이 ..

링크 https://www.acmicpc.net/problem/1932 난이도(solved.ac 참고) 실버1 풀이 이 문제를 풀 때 처음에 좀 막막했다. 예제 입력에서 제일 꼭대기층 7에 대해 그 아래층의 3과 8중에 어디를 가야될지를 고민을 많이 했다. 그리디처럼 생각을 하고 가장 큰 값만 집어넣자니 범위 설정이 되어있어서 그렇게 할 수 없었다. 근데 생각해보니까, 최종합이 가장 큰 경로로 가기 위해 꼭 매 층마다 어떤 수를 넣어야될지 고려할 필요는 별로 없었다. 단지, 쭉쭉 직접 값을 구하면서 내려가면서 더 큰 값을 집어넣기만 하면 되는 것이었다. 예를 들면 7 3 8 이 2층짜리 삼각형이 있다고 한다면 아래로 내려가면서 각각을 더해주는 것이다. 7 10 15 이렇게 말이다. 이런식으로 더해나가는 ..