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을 적용시켜야 했다. 생각의 관점을 달리하면? ..

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%..

1. 학습 날짜 : 2021 08 12(수) 2. 학습 시간 : 3. 학습 주제 : 철권7 대회 조추첨 프로그램 제작 4. 동료 학습 방법 : 개인 5. 학습 목표 : 철권7 대회 조추첨 프로그램 설계, 제작 6. 학습 내용 : 요구사항 아래와 같은 엑셀 데이터가 존재하며, 데이터 내에서 스팀 닉네임과 계급은 선택적으로 들어가는 데이터이다. 순번 / 인덱스 플레이어 이름 스팀 닉 계급 1 a aa vindicator 2 b bb emperor 3 c cc tekken king 4 d dd 1st dan 5 e ee 2st dan 6 f ff 3st dan 7 g gg 4st dan 8 h hh 5st dan 9 i ii 8st dan 참가자 n명이 존재한다. 아래 엑셀 행을 1.무작위 or 2.계급 에 ..