링크 https://www.acmicpc.net/problem/12904 난이도(solved.ac 참고) 골드5 풀이 나는 역으로 접근해서 B에서 A를 만들 수 있는지를 확인하였다. 두 가지 연산 모두 A 또는 B가 추가되는 연산이다. 따라서 역으로 생각하면 이것들을 하나씩 지워주면서 B의 길이를 줄여나가면 되는 것이었다. BtoA라는 함수를 만들어서 b의 값을 이 함수를 적용시킨 값으로 해주었다. 마지막 값이 A라면 그 A값을 지운 새로운 new_b를 return하였고, 마지막 값이 B라면 b의 길이가 1보다 큰 때와 1일 때를 나눴다. 이유는 이렇게 나누지 않으면 계속 줄어들어서 결국 0이 되기 때문이다. b의 길이가 1보다 큰 경우라면 마지막 값을 없앤 값을 reverse하고 그것을 리스트로 바꿔준..
링크 https://www.acmicpc.net/problem/4358 난이도(solved.ac 참고) 골드5 풀이 딕셔너리로 구했는데 자꾸 시간 초과가 떠서 defaultdict를 사용해서 풀었다. 처음에는 try except로 하려고 했는데 생각해보니까 input값에서 공백을 제거한 값이 아무것도 없으면 더이상 진행하지 않으면 되는 것이었다. defaultdict(int)를 주게 될 경우, 값을 부여했을 때 숫자 형태로 저장이 된다. 아래 예시를 보면 이해가 될 것이다. from collections import defaultdict a = defaultdict(int) b = defaultdict(list) c = input() a[c] += 1 b[c] = ['steadily', 'worked']..
링크 https://www.acmicpc.net/problem/15654 난이도(solved.ac 참고) 실버3 풀이 다르게 풀 수도 있겠지만, 나는 permutations(순열) 모듈을 불러와서 사용했다. 순열은 수학에서 nPr이다. n개 중에 r개를 뽑는 경우의 수이다. from itertools import permutations a = [1, 2, 3, 4] for i in permutations(a, 2): print(i) # (1, 2) # (1, 3) # (1, 4) # (2, 1) # (2, 3) # (2, 4) # (3, 1) # (3, 2) # (3, 4) # (4, 1) # (4, 2) # (4, 3) 사전 순서로 증가하는 순으로 출력해야 되었기 때문에 a를 정렬한 값을 기준으로 순열..
웹 프론트엔드 파트를 공부하다 보면, 필연적으로 알아야 할 것이 서버와의 API 통신이다. 프론트엔드 개발자라고 하더라도 서버에서 어떤 식으로 API를 만드는지, 그리고 어떠한 방식으로 데이터가 각 URL에 저장되는지는 알아야 한다. 그래서, 간단하게 로컬 DB를 만든 뒤에 express를 사용해서 API를 설계하는 방법에 대해 포스팅해보려고 한다. 시작하기에 앞서 폴더 구조가 이러한 형태로 되어있음을 참고하기 바란다. 이 포스팅에서는 messages만 다룬다. 1. 프로젝트 기초 세팅 yarn init -y yarn add express cors uuid yarn add --dev nodemon yarn init -y는 프로젝트를 새로 시작하면서, 패키지 생성파일을 설치하는 과정이다. express: ..
링크 https://www.acmicpc.net/problem/17626 난이도(solved.ac 참고) 실버5 풀이 input값 n을 받았을 때, 우선 9행에서 이 수가 특정 수의 제곱수인지 여부를 걸러낸다. 처음에는 무조건 그 수와 가장 가까운 제곱수를 찾아내 그 수를 더하고 남은 값을 DP 처리하는, 그리디 방식으로 생각했다. 근데 그렇게 하자니, 12라는 훌륭한 반례가 있다. 12 = 3^2 + 1^2 + 1^2 + 1^2 (총 4개) = 2^2 + 2^2 + 2^2 (총 3개) 그 수와 가장 가까운 제곱수를 항상 더하는 방식으로 가져간다면 위의 12처럼 12와 가장 가까운 제곱수인 3을 가져갔을 때의 개수가 2를 세 개 가져갔을 때의 개수보다 더 많다. 그렇기 때문에 그리디와 같은 방식으로 풀면..
링크 https://www.acmicpc.net/problem/1013 난이도(solved.ac 참고) 골드5 풀이 파이썬 정규표현식 문제이다. re(regular expression) 모듈을 불러와서 사용한다. (100+1+ | 01)+ 을 해석해보려고 했는데, 이게 리스트로 하나하나 나열하는 게 불가능하다는 판단 하에 정규표현식에서 compile을 사용해서 풀어보기로 하였다. +와 (), | 등은 실제로 정규표현식에서 많이 쓰이는 연산자이다. 이 세 표현에 대해 잠깐 정리하자면 +: + 앞에 붙은 요소가 최소 하나는 들어가야 한다는 뜻이다. 예를 들면, ab+c라고 해보자. 이것을 만족하는 배열은 { abc, abbc, abbbc, abbbbc, ... } 이렇게 있다. (): 괄호 안의 요소들을 하..
백준 문제를 풀다가 제출 현황을 보면 자주 볼드체 + 색상 처리가 되어있는 아이디를 볼 수 있었다. 내 아이디는 반면에 너무 심심해서 한번 색상을 입혀봐야겠다는 생각이 들어 찾아봤다. 찾아보니까 외국 알고리즘 대회 사이트에서 주최하는 대회에 참여해서 문제를 풀었을 때 부여되는 레이팅에 해당하는 색상이 입히고 백준에서 그 대회 사이트와 계정 연동을 했을 때 백준에도 반영이 되는 것이다. (레이팅 부여 후 색상 입혀지기까지 1-2일 소요) 나는 Codefordes에서 하는 대회를 참여했다. 여기에 들어가면, 위 사진처럼 예정되어있는 대회들을 확인할 수 있고, Before registration 시간이 다 지나면 등록 버튼이 활성화된다. UTC를 기반으로 하기 때문에 KST 기준으로는 +9시간 뒤에 시작된다...
링크 https://www.acmicpc.net/problem/11279 난이도(solved.ac 참고) 실버2 풀이 Python의 heapq 모듈만 알고 있으면 너무 쉬운 문제이고, 나 또한 그것을 알고 있어서 금방 풀었지만 포스팅을 하는 이유는 최소힙이 아니라 최대힙이므로, 이를 만드는 쉬운 방법을 공유하기 위함이다. heapq 모듈을 사용하면서 약간의 트릭을 넣음으로써 최대 힙을 구현할 수 있다. heapq.heappush를 할 때 -의 값으로 집어넣는 것이다. 그렇다면, 기본적으로 heapq 모듈은 최소힙을 가정하므로 - 값이 가장 클 수록 상위에 위치하게 된다. 이것을 출력할 때 절댓값만 씌워주면 최대힙과 똑같다. (물론 음수는 들어가지 않는다는 전제하에. 이 문제는 음수는 입력하지 않는다고 했..
링크 https://www.acmicpc.net/problem/1541 난이도(solved.ac 참고) 실버2 풀이 숫자 외에 연산자가 들어간 input값 처리는 거의 해본 기억이 없어서 좀 헤맸다. 여기서 내가 생각하는 키포인트는, -를 기준으로 나누면 + 연산자를 끼고 있는 숫자들은 전부 리스트의 원소로 따로 들어가게 된다는 점이다. 여기에서 최소값을 만들려면 + 연산자로 묶여있는 두 수는 무조건 빼야 한다. -를 기준으로 split 메소드를 사용해 나눈 것이므로 무조건 빼주더라도 출력을 구하는 데 지장이 없다. 이제 문제는, ['50+40']의 형태로 되어있는 리스트를 [50, 40]으로 쪼개는 방법이었는데, 이 또한 +를 기준으로 split을 한 결과를 새로운 리스트에 저장한 뒤, 그 리스트를 돌..
링크 https://www.acmicpc.net/problem/1976 난이도(solved.ac 참고) 골드4 풀이 input값으로 인접 행렬 형태가 들어갈 거라고는 생각도 안하고 있다가 시간을 좀 날렸다. 핵심은 27행~31행인데, i에 대한 for문을 진행할때마다 list input을 받아서 j에 대한 for문을 다시 돈 다음, j-1번째 인덱스의 값이 1인지 아닌지 여부를 판단하였다. 이게 1이라면, 예를들어 (1, 2) 좌표가 1이라면 도시 1과 도시 2는 연결이 되어있는 것이다. 따라서 union으로 이 두 개를 합집합 처리를 한다. 이제 이렇게 할 경우 1로 들어간 부분에 대해서는 전부 합집합 처리가 되어, 연결이 되어있는 상태가 되었다. 이제 최상위 부모 노드를 찾는 find_parent를 ..