TIL

https://www.acmicpc.net/problem/2579 계단 오르기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 91500 31384 22863 35.025% 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음..

https://www.acmicpc.net/problem/2193 이친수 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 62874 25374 18924 38.628% 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1 ≤ N ≤ 90)이 주어..

RGB거리 https://www.acmicpc.net/problem/1149 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용..

주의 모든 DP문제는 재귀로 풀리지 않는다. "일부"만 재귀로 풀릴 뿐, Top-down, Bottom-up 방식 모두 고려해야 한다. RGB거리 https://www.acmicpc.net/problem/1149 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입..

Makefile Shell에서 컴파일을 할 때, make 명령어를 활용해서 컴파일을 할 수 있다. Makefile이 디렉토리에 있다면 해당 디렉토리에서 make 명령어만 치면 컴파일이 실행이 된다. 프로그램들과 달리 Shell에서 컴파일을 하려면 어떤 파일들을 컴파일 하고, 어떠한 방식으로 컴파일 할 지 직접 컴파일러에게 알려줘야 한다. 예를들어 아래와 같다. $gcc a.c b.c 이 코드를 실행하면 $ls main.c main.o 이처럼 main.o 파일이 생성된 것을 알 수 있다. 이 main.o 파일은 main.c 파일을 컴파일 한 어셈블리 코드가 담겨있는 파일 입니다. 여러 파일을 컴파일하는 경우 아래의 사진과 같이 진행된다고 보면 된다. 링킹(Linking) 링킹이 이름 그대로 링크 하는 작업..

TRIANGLEPATH https://www.algospot.com/judge/problem/read/TRIANGLEPATH (i, j) 번째 노드에서 아래쪽, 또는 오른쪽 아래로 내려가는 Path가 만들어지고, 최종적으로 n번째 depth에 다다랐을 때, 경로의 최댓값을 찾는 문제. 첫 시도에 풀지 못한 이유 : 문제분석을 제대로 못함. : 문제 이해를 잘못함 문제분석을 제대로 한 이후에는 완전탐색으로 문제를 풀려고 했음. 완전탐색으로 푸는 방법밖에 없다고 생각했는데, 굳이 겹치는 경로가 없기 때문에 memoization을 적용할 필요가 없다고 생각했기 때문이다. 어찌되었든 문제에 대한 이해가 잘못되어있었다. 겹치는 경로는 존재했으며, memoization을 적용시켜야 했다. 생각의 관점을 달리하면? ..

20210818 (수) [TOC] 등운동 유의점 : 등운동은 대부분 미는 운동보다는 당기는 운동으로 이루어져있다. 어디를, 어떻게 당겨야 하는가? 이전에 했던 풀업 : 손에 힘을 주고 바를 밑으로 당기려고 애썼었다. 바를 밑으로 당기면 어깨 개입이 커지고 가동범위게 문제가 생긴다. 어깨도 늘어난다. 타겟부위는 등인데 등이 타겟되지 않는다. 손에 힘을 주고 팔을 밑으로 당기려고 했었다. 어느정도 자극이야 오지만, 충분하게 자극이 오지 않았으며, 성장이 멈췄었다. 현재 하는 풀업 : 1번 깨달음 : 이전에 하던 풀업과의 차이점이 있다. 이전에 하던 풀업은 "손과 팔을 아래로 당겨" 몸을 위로 당겼었다. 몸을 당기는것이 부수적인 움직임으로 따라왔었다. 현재 하는 풀업은 "몸통을 바쪽으로 당긴다." 손과 팔은 ..

1. 학습 날짜 : 20210818(화) 2. 학습 시간 : 6시간 3. 학습 주제 : Dynamic Programming, Topological sorting, 다익스트라, 벨만-포드 알고리즘 정리 4. 동료 학습 방법 : 개인 5. 학습 목표 : 동적 계획법에 대한 이해 이항 계수 이해 이항 계수와 동적 계획법 동적 계획법 관련 문제 Topological sorting 구현 다익스트라 구현 벨만-포드 구현 6. 학습 내용 : 이항계수와 DP 이항계수와 이항정리 이항정리 이항식(두 단항식의 합 == 항이 두개인 식)의 거듭제곱을, 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리. (https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EC%A0%95%..