hyesungoh / aa_algorithm Goto Github PK

BOJ 2588

간단한 문제, input을 어떻게 사용하는 지 까먹은 내가 레전드. 조금 더 잘 풀어볼 수 있을 거 같다.

BOJ 1330

동시에 입력되는 두 수를 비교한 결과를 출력하는 문제, map 함수를 이용하여 아주 조금은 효율적으로 풀지 않았나 생각한다.

BOJ 2753

윤년인지 확인하는 문제, 단순히 문제에서 말해준 규칙을 if문으로 나열해 풀었다. 이게 최선인가?

BOJ 14681

두 수를 입력받고 어느 사분면에 속하는 지 출력하는 문제, 변수를 사용하지 않고 if문에 input을 사용했다.

BOJ 2884

24시간 기준으로 45분을 뺀 시각을 출력하는 문제, 입력받은 분에 45를 뺀 값으로 비교를 했으며 0시 일 때를 따로 확인하여 23시로 바꿔주었다.

BOJ 5543

5개의 수를 입력받고, 각 3개, 2개 중 제일 작은 수를 더한 값에 50을 뺀 값이 정답인 단순 구현문제, lambda를 쓸 생각은 했지만 접근 방법이 달랐던 것 같다. min 함수를 쓸 생각은 했다는 것에 일단 만족

BOJ 2523

입력받은 수까지 올라갔다가 다시 내려가는 별 찍기 문제, 처음엔 1부터 n까지, n에서 1까지의 range를 합치고 n이 1일 때를 예외처리 했다. ([,1] 이렇게 되기 때문) 다른 풀이는 출력문에 + n * 절댓값(i)를 해주고 n-1 ~ -n 까지 -1되는 range를 만들었다. (n이 3일 때 [2,1,0,-1,-2]) 역시 별 찍기가 뇌를 깨우기 좋은 것 같다.

BOJ 10996

별 찍기, 처음보는 유형의 별 찍기여서 상당히 헤맸다. 찾은 규칙으로는 열의 수는 n*2인 것과 / 한 열에 별과 공백의 총 수는 n / 홀수열일 때 별으로 시작이였다. 첫 풀이는 이를 가지고 이중 반복문으로 구현을 했다. 다른 풀이는 나와 달리 반복문 한 개를 가지고 구현했는데 n을 2로 나눈 값을 가지고 구현했는데 조금 더 생각해보면 나도 생각할 수 있었을 것 같다. 화이팅

BOJ 10818

한 열에 여러 수를 입력받고 그 중 제일 큰 수와 작은 수를 출력하는 문제, min과 max를 사용해서 풂

BOJ 1193

입대 전에 풀었다가 실패한 문제, 위 글을 참조하여 풀었으며 분모, 분자의 합과 stage + 1이 같다는 것을 이용하면 다르게도 풀 수 있을 것 같다.

BOJ 2562

9가지의 수를 입력받고 그 중 재일 큰 수와, 그 수가 몇 번째로 입력 되었는 지 출력하는 문제. max를 이용하여 숏코딩을 할 수 있었지만 반복문을 한 번 사용하여 확인을 하는 것이 더욱 효율적이라 생각돼 이 방법을 택했다.

BOJ 3052

입력받는 10개의 수들을 42로 나눈 나머지 값이 겹치지 않게 몇 개인지 출력하는 문제. 중복되는 요소가 없는 set 자료형을 이용하여 간편하게 풀었다.

BOJ 11650

2차원 좌표를 받고 X 좌표가 증가하는 순으로 정렬, X 좌표가 같을 시 Y 좌표가 증가하는 순으로 정렬하여 출력하는 문제. 파이썬의 sort 메소드의 key를 lambda식을 사용해서 풀었다.

BOJ 11651

위 문제의 우선순위가 XY에서 YX로 바뀐 문제 lambda식을 바꿔서 풀었다.

BOJ 15596

list를 매개변수로 갖는 함수 solve는 list에 들은 모든 값을 더한 값을 반환해준다. 위 함수를 구현하는 문제. sum 메소드를 사용해서 간단히 풀었다.

BOJ 2798

n과 m을 입력 받은 후, 길이가 n인 수들의 배열 l을 입력 받는다. l에 존재하는 수들 중 3개를 합친 값이 m이 넘지 않으며, m과 최대한 가까운 값을 구하는 문제. 3중 반복문을 이용하여 브루트포스 방법을 통해 풀었다.

BOJ 10828

스택을 구현하는 문제이다. 처음엔 전역 변수 list, l과 함수들로 구현하였지만 백준 체점 도중 런타임 에러로 인하여 class로 스택을 구현하였으나 이 또한 백준 체점 도중 시간초과로 인해 input = sys.stdin.readline를 이용하여 시간을 단축시켰다. 풀이는 쉬웠으나 체점 기준에 맞추기 힘들었다.

BOJ 15719

n과 1 ~ n-1까지 이루어진 수열을 입력받는 다. 수열에는 중복된 수가 한 개 존재하며, 그 것이 문제의 정답이다. 첫 풀이는 단순히 수열을 기준으로 반복문을 수행하고 dictionary에 key에 수열의 수를 넣어 이미 존재하는 수일 때 break하여 그 수를 출력하는 것으로 풀이를 하였으나 백준 체점 기준으로 메모리 초과 결과가 나와 검색해보니 sys.stdin.read()를 사용해야한다 ... 해서 사용해봤으나 EOF를 따로 입력해야하는 read() 특성상 마음대로 구현이 되지 않아 이 부분은 다른 분 풀이를 참고하여 read() 함수를 구현했다. read()를 참고하며 본 방법인데 중복된 문자는 1개, 1 ~ n-1까지의 수로 이루어진 수열이라는 특징을 이용해 1 ~ n-1의 총 합(n*(n-1)//2)에서 수열에 존재하는 모든 수를 뺀 값에 -를 붙이면+ 정답이 나오게 된다.. 역시 배울 게 남아도 너무 많이 남았다고 생각한다.

BOJ 1436

666이 들어간 수 중에 n번째로 큰 수를 출력하는 문제. 브루트포스 방법으로 풀었다.

BOJ 15668

숫자 n을 입력받고 n = n1 + n2 방식으로 표현할 때 n1과 n2에서 0~9까지 겹치는 수가 없는 경우를 출력하는 문제. 파이썬의 i "in" word와 같이 사용하는 메소드를 사용하여 풀었다. 첫 풀이에서 큰 수는 생각하지 못한체 반복문의 범위를 n//2+1으로 설정하여 시간초과가 나왔지만 range(1, min(100000, n))으로 바꾸었더니 정상적으로 정답을 맞을 수 있었다. 추가적으로 exit() 함수를 배웠다. 앞으로 유용하게 사용할 것 같다.

BOJ 13420

숫자 n만큼 '2 + 2 = 4'와 같은 수식을 입력받고 정답이 맞을 때와 아닐 때 출력을 나눠 하는 문제. 문자열 형식을 실행하는 eval() 메소드를 이용하여 풀었다.

BOJ 5524

숫자 n만큼 대문자와 소문자가 섞여있는 문자열을 입력받고 모든 문자열을 소문자로 출력하는 문제. 문자열의 lower() 메소드를 이용하여 풀었다.

BOJ 2935

10의 제곱 형태인 두 수와 +, _ 중 하나를 입력받고 연산된 수를 출력하는 문제. 첫 풀이에서는 연산 속도를 위해 _ 일 때 두 수의 0을 세어 더한 값 A를 '1', '0' * A해서 풀었다. 두 번째 풀이는 eval을 이용하여 숏코딩 스타일로 풀었다.

BOJ 1408

12:30:30과 같은 형식으로 입력되는 두 시간들의 차를 구하는 문제. 파이썬의 datetime을 이용하여 풀었으나 백준 기준으로 런타임 에러로 인해 두번째 풀이는 시간과 분을 초로 바꿔 연산하여 풀었다.

BOJ 12090

한글로 이루어진 문자열을 입력받은 후 그 문자열의 초성을 출력하는 문제. 한글 초성의 유니코드 상 순서로 이루어진 list를 만들고 각 글자마다 계산하여 ans 문자열에 추가하여 풀었다.

BOJ 10845

큐를 구현하는 문제이다. 스택과 마찬가지로 클래스를 이용하여 구현하였다. 백준 풀이상 시간초과 오류로 인해 sys.stdin.readline을 사용하였다.

BOJ 16394

1946 이상의 수를 입력받고 해당 년도에 홍익대학교의 개교 몇주년인지 출력하는 문제.

BOJ 16503

1 + 2 _ 3와 같은 형태로 연산자 + - _ /, 4가지와 1 이상의 수 3가지를 입력받는다. 계산 순서에 따라 달라지는 두 값중에 작은 순으로 출력하는 문제. 하지만 나눗셈 연산중에 피연산자 중 하나가 음수이면 양수로 바꿔 계산한 값에 음숫값을 취한다. 첫 풀이는 입력받은 값을 list형으로 변환하여 괄호를 넣어 eval을 이용하여 풀었으나 피연산자가 음수인 나눗셈 연산일 경우를 위해 새롭게 풀기로 하였다. 두번째 풀이는 리스트 슬라이싱을 통해 먼저 계산을 하고 입력되는 숫자는 모두 양수인 것을 이용하여 먼저 계산한 값과 연사자만을 확인하여 연산해주었다. 다른 사람 풀이는 5개의 수, 연산자만 입력되는 것을 이용하여 eval을 이용하여 간단히 푼 것을 볼 수 있는데, 연산 과정에서 나눗셈 연산을 위와 같이하는 줄 모른 내 잘못이 컸다.

BOJ 10866

덱을 구햔하는 문제이다. 위 스택과 큐와 같이 클래스를 이용하여 구현했으며 백준 풀이상 시간초과 오류로 인해 sys.stdin.realine을 사용하였다. list.pop(-1)도 마지막 요소를 pop해준 다는 것 또한 알게 되었다.

BOJ 2789

문자열을 입력받은 후 'CAMBRIDGE'에 포함된 알파벳을 모두 지워 출력하는 문제. 파이썬의 in 연산자를 사용하여 풀었다.

BOJ 3040

9개의 수를 입력받고 합이 100인 7개의 수를 찾는 문제. 이중 반복문을 이용하여 9개의 수를 전부 합한 값에 100을 뺀 값과 비교를 하여 찾은 후 list.remove()하여 풀었다. 다른 풀이는 sum - 100 - 현재 반복중인 값 i으로 비교할 수를 구하고 그 수를 in 연산자를 이용하여 찾아 없애는 풀이다.

BOJ 3046

a + X / 2 = b일 때, a와 b를 입력받고 X를 구하는 문제. b*2-a하여 간단히 풀었다.

BOJ 1026

n개의 수로 이루어진 두개의 배열을 입력받는다. 두 배열의 요소들을 각각 곱한 값들 중 최솟값을 출력하는 문제. 첫 풀이는 n번 반복하며 min과 max를 이용하여 곱한 값을 더해주었다. 두번째 풀이는 sorted와 map, lambda를 이용하여 조금 더 간단히 풀었다.

BOJ 2420

-2,000,000,000 ≤ N, M ≤ 2,000,000,000의 범위를 가진 두 수를 입력받고 두 수의 차이값을 출력하는 문제. n-m값에 abs함수를 이용하여 풀었다.

BOJ 11784

1000줄 이하의 16진수로 된 문자열을 입력받은 후 이를 영어로 디코딩하여 출력하는 문제. sys.stdin.read를 이용하여 eof까지 읽어왔으며 .split('\n')을 이용하여 줄바꿈마다 나눠준 후 나눠진 각 문자열들을 bytearray.fromhex(str).decode()을 이용하여 번역 후 출력하였다.

BOJ 1009

n과 m을 입력받은 후 nm의 일의 자릿수를 (0일 때는 10) 출력하는 문제. 첫 풀이는 단순히 str(nm)[-1]을 통해 풀었으나 수가 커질 수록 걸리는 시간이 크게 늘기 때문에 l = [[10], [1], [6,2,4,8], [1,3,9,7], [6,4], [5], [6], [1,7,9,3], [6,8,4,2], [1,9]] 위와 같이 규칙을 찾아 2차원 리스트로 만든 후 n과 m에 나머지 연산을 통해 출력하였다.

BOJ 18258

큐를 구현하는 문제. 첫 풀이는 저번과 같이 sys.stdin.readline으로 시간을 줄이고 class로 구현을 하였다. 하지만 이번 문제에서는 pop후에 요소들을 1칸씩 당기는 과정에ㅐ서 O(n)의 계산량때문에 시간초과 결과를 받게 되어 from collections import deque를 사용하여 구현하였다.

BOJ 2824

정수 n을 입력받은 후 n개의 수를 입력받는다. 모든 수를 곱한 값이 A, 같은 방식으로 m과 B를 입력받는다. A와 B의 최대공약수를 출력하는데 만약, 9자리보다 길다면, 마지막 9자리만 출력하는 문제. a % b = r일 떄, b % r = r1, r % r1 = r2와 같은 방식으로 나머지값이 0일 때까지 연산하는 유클리드 호제법을 이용하여 풀었으며 파이썬의 문자열 슬라이싱을 이용하여 9자리 이상일 때 예외처리를 하였다.

BOJ 16430

1kg의 치즈가 있을 때, a/b kg을 도둑맞았다고 할 때 남은 치즈의 무게를 출력하는 문제. b-a와 b를 공백으로 나누어 출력하여 풀었다.

BOJ 1712

노트북을 만들어서 판매할 때 기본 비용 x, 1대 생산시 소모되는 비용 y, 1대가 판매되는 가격이 z라고 했을 때 흑자가 되는 판매 개수를 출력하는 문제. z가 y보다 작을 때는 손익분기점을 넘지 못하므로 -1을 출력하고 그 외의 상황에서는 x//(z-y)+1, 1대 생산하여 보는 이득을 기본 비용에 나눈 값에 1을 더하는 수식을 이용하여 풀었다.

BOJ 2869

v라는 높이에 있는 곳을 오르려는 달팽이는 낮에 a만큼 올라가며 밤에는 b만큼 미끌어진다고 한다. v에 도달했을 때는 미끄러지지 않을 때 며칠째에 도착하게 되는 지를 출력하는 문제. 첫번째 풀이는 반복문을 수행하며 v <= (a-b) * t + a라는 수식될 때까지 t를 1씩 더하며 풀었으나 당연히 시간초과를 만났다. 두번째 풀이는 t, (v-b) // (a-b)을 두고 (v-b) % (a-b)가 0일 때, t를 출력하고 아닐 시 t + 1을 출력하여 풀었다. a가 v보다 클 때를 위해 위처럼 풀었으며 다른 사람의 풀이는 (v-b-1)//(a-b)+1를 출력하여 단순히 푼 것을 배웠다. 수학적 사고능력의 부족함을 뼈저리 느꼈다.

BOJ 2231

245의 분해합은 (245+2+4+5)하여 256이며 245는 256의 생성자일 때, n을 입력받고 그 수의 생성자를 출력하며 생성자가 없는 수일 때는 0을, 여러 개일 때는 제일 작은 수를 출력하는 문제. 브루트포스 방식을 이용하여 n까지 for문을 수행하며 수를 문자열 타입으로 바꾼 후 sum 함수를 이용한 후 비교해 주었다. 제일 작은 생성자만 출력하면 되기 때문에 출력 후 exit() 해주었으며 반복문이 끝났을 때 0을 출력 해 주었다.

BOJ 2407

두 수, n과 m을 입력받은 후 조합 nCm을 출력하는 문제. 팩토리얼은 알았어도 수열과 조합은 무지했던 나는 공식을 찾아본 후에야 풀 수 있었다. 파이썬 itertools의 combinations는 리스트를 반환하므로 문제와 맞지 않아 math의 팩토리얼을 import하여 n! / m! * (n-m)!하여 풀 수 있었다. 부족한 부분이 너무 많다

BOJ 3009

x y 형태로 입력되는 3개의 점의 좌표를 입력받은 후 직사각형을 만들기 위해 필요한 네 번째 점의 좌표를 구하는 문제. 첫 풀이는 x와 y 좌표의 딕셔너리를 만들어 몇 번 나왔는 지 확인하기 위해 key에 좌표를, value에 in 연산자를 이용하여 해당하는 값을 넣어주었다. 그 후 dict.items()를 반복돌며 value가 1인 key를 출력하는 형태로 풀었다. 이 과정이 직관적이긴 하여도 효율적이지 못하다는 생각이 들어 두 번째 풀이는 XOR 연산자를 이용하여 풀 수 있다는 참고를 받아 풀어보았다. 첫 번째 풀이보다 상당히 효율적이라 생각한다.

BOJ 9093

숫자 n과 n개의 문자열을 입력받는다. 문자열의 공백을 기준으로 단어별 거꾸로 출력하는 문제. 파이썬의 reversed를 이용하여 풀었다.

BOJ 17413

abc와 같은 문자열이 입력됐을 때 cba같이 <>안의 문자열은 반대로 출력하지 않고 <>밖의 문자열은 반대로 출력하는 문제. 문자열을 리스트화하여 반복문을 수행하고 현재 문자가 '<', '>', ' '일 때 예외를 두어 출력하고 그 외에 빈문자열에 문자를 계속 더하는 방법으로 풀었다

BOJ 9987

포켓몬스터의 번호를 입력받으면 해당 포켓몬의 이름과 속성을 출력하는 문제. 포켓몬스터 홈페이지 크롤링을 직접하지는 않았고 복사하여 딕셔너리 형태와 배열 형태로 저장된 것을 이용하여 풀었다. 첫번째 풀이에서 런타임 에러를 단순 배열이 잘못된 줄 알았지만 포켓몬의 속성이 한 개인 포켓몬도 있었기 때문에 발생한 오류였다. 해당 포켓몬의 속성 배열을 기준으로 for문을 사용하여 출럭하였다.

BOJ 17298

n만큼의 수열을 입력받는다. 그 수열들의 오큰수를 출력하는 문제인데, 오큰수란 수열의 오른쪽에 있으면서 자기보다 크며 가장 왼쪽에 있는 수를 뜻한다. 첫 풀이는 이중 반복문을 이용하여 풀었는데 백준 상 시간초과로 인하여 스택을 이용하여 풀어 볼 예정이다.

BOJ 14918

두 수를 공백으로 나눠 입력받은 후 더한 값을 출력하는 문제 sum, map, split을 이용하여 간단하게 풀었다.

BOJ 17298

위 문제의 시간초과로 인하여 스택을 이용하여 풀어 보았다. range(n-1)을 반복하며 s[i]보다 s[i+1]이 클 떄 정답 리스트인 ans_l에 [i]에 넣었다. 그렇지 못할 때 스택에 push하는데 스택에는 s[i]를 저장하는 list와 i를 저장하는 init_len 리스트를 두어 반복문 수행안에 while 스택의 길이가 0보다 크며 s[i+1]이 스택의 맨 마지막에 들어온 것보다 클 때 ans_l에 추가하여 풀었다. 다른 사람의 풀이를 보니 아직 배울 점이 많은 걸 또 깨달았다.

BOJ 10818

태국은 석가모니가 열반한 해를 기준으로 연도를 세는 불기를 사용한다. 불기 연도를 입력받은 후 서기 연도를 출력하는 문제. 543년 차이가 나기 때문에 간단한 사칙연산을 이용하여 풀었다.

BOJ 17496

작물을 판매할 수 있는 총 가격을 출력하는 문제. 입력받는 d, g, n, p는 각 기를 수 있는 일 수, 자라는 데 걸리는 일 수, 한 번에 심을 수 있는 수, 가격이다. 문제에서 처음 심는 날을 1일으로 정해놓았기 때문에 (d-1)//gnp를 계산하여 풀었다.

BOJ 11931

n개의 수를 각 줄마다 입력받고 내림차순으로 정렬하여 각 줄마다 출력하는 문제. 첫풀이에서 시간초과 결과를 받게 되어 sys.stdin.readline을 import하였디. 그 후 sorted(퀵 정렬)와 reverse=True를 이용하여 풀었다.

BOJ 4470

n개의 문자열을 입력받고 각 입력받은 문자열 앞에 '1. ~', '2. ~', '3. ~'과 같이 줄 번호를 붙여서 출력하는 문제. for 반복문을 range(n)을 기준으로 돌며 i+1과 '. '을 input()한 것에 더 한 것을 출력하여 풀었다

BOJ 17293

n을 입력받은 후 n ~ 0까지 이어지는 노래 가사를 출력하는데 가사의 첫 줄은 n bottles, n이 1일 때는 bottle, 0일 때는 no more bottles로 나누어 출력해야 한다. 두번째 줄은 n-1 bottles, n-1이 1일 때는 bottle, i-1이 0일 때는 no more bottles로 출력해야 한다. 추가적으로 마지막 문장은 다르며 n bottles 혹은 bottle을 출력해야한다. 첫 풀이는 단순 if문과 삼항연산자를 이용하여 풀었으며 두번째 풀이는 함수를 이용하여 풀었으나 백준 풀이상에서는 틀렸다고 나오는 데 이유를 아직 못찾았다.

BOJ 2455

4개의 줄을 입력받으며 각 줄마다 열차에 '하차한 승객 수' '승차한 승객 수'를 입력받는 다. 승객이 가장 많이 탑승하고 있을 때가 몇명인지 출력하는 문제. 반복문을 4번 수행하며 t 변수에 t + 승차한 승객 수 - 하차한 승객 수를 계산하였고 max 함수를 이용하여 t와 저번 반복문에 수행된 ans와 비교를 하여 풀었다.

BOJ 2460

위 문제와 동일하며 다른 점은 10번 반복을 한다는 점. 반복문을 10번 수행하게 바꾸어서 풀었다.

BOJ 15963

한 문자열에 공백을 기준으로 두 개의 수를 입력받고 같으면 1 다르면 0을 출력하는 문제. split()과 삼항연산자를 이용하여 풀었다.

BOJ 14405

문자열이 입력되고 'pi', 'ka', 'chu'를 제외한 다른 단어가 있을 때 NO, 세 단어로만 이루어져 있을 때 YES를 출력하는 문제. 첫 풀이 때 replace('pi', '')와 같이 단어를 공백으로 바꿔주었는데 'kpia'와 같은 문자열에서 pi가 없어져 'ka'가 있다고 판단하기 때문에 replace를 '/'로 하였고 최대 문자열의 길이인 '/'*5000과 in 연산자로 비교하여 '/'가 아닌 다른 문자가 있을 때 NO를 출력하게 풀었다. 다른 풀이는 replace를 ' '으로 하여 strip 함수를 이용하여 푸는 것이다

BOJ 1271

숫자 n과 m을 입력받은 후 나눈 값과 나머지를 출력하는 문제

BOJ 2338

숫자 n과 m을 입력받은 후 +, -, x 연산을 하야 출력하는 문제

BOJ 2475

5가지 수를 입력받은 후 각 수를 제곱한 수들의 합에 10으로 나눈 나머지를 출력하는 문제. 함수를 만들어서 풀었다.

BOJ 2845

두 수 n, m을 입력 받은 후 곱한 값에 다음 줄에 입력되는 5가지 수와 비교한 값을 출력하는 문제. input.split한 값을 기준으로 for문을 수행하여 풀었다.

BOJ 2914

n과 m을 입력받은 후 A를 구하면 된다. A / n이 m이지만 A / n에서 소수값이 있을 때 m은 +1한 정수가 되게 된다. n * (m-1) + 1 수식을 이용하여 풀었다.

BOJ 3003

정해진 수들과 비교하여 차이값을 출력하는 문제 input.split한 리스트와 range(6)을 기준으로 수행되는 for문을 이용하여 풀었다.

BOJ 5522

5개의 줄에 입력되는 수들의 총합을 출력하는 문제.

BOJ 5554

4개의 줄에 입력되는 수들을 분과 초로 출력하는 문제. 60으로 나눈 값과 나머지를 출력하여 풀었다.

BOJ 1085

x, y, w, h를 입력받는 다. (x, y)는 현재 내 위치이고, 사각형의 왼쪽 아랫점은 (0, 0), 오른쪽 위의 점은 (w, h)라고 할 때 사각형 밖으로 나갈 수 있는 제일 짧은 거리를 출력하는 문제. min을 사용하여 x, y, w-x, h-y를 비교하여 풀었다.

BOJ 17256

숫자 세개로 이루어진 두 개의 문자열을 각각 a,b,c / x,y,z라고 할 때 x-c, y//b, z-a라는 수식을 도출해 출력하는 문제

BOJ 5596

공백으로 나누어진 4개의 수를 두 줄 입력받은 후, 총합이 큰 것을 출력하는 문제. max와 sum 함수를 이용하여 풀었다.

BOJ 1247

3번에 걸쳐 정수 n만큼 수를 입력받은 후 총합의 부호를 출력하는 문제. 현재 시간초과 결과를 보여주어, sys.stdin.readline을 import하여 해결하였다.

BOJ 2480

공백으로 나누어진 3개의 수를 입력받은 후, 같은 수가 3개일 때 10000 + (같은 수) _ 1000, 같은 수가 2개일 때 1000 + (같은 수) _ 100, 같은 수가 없을 때는 (제일 높은 수) * 100 한 값을 출력하는 문제. 내 풀이는 리스트의 count 메소드를 사용하여 a, b 각 count하여 변수 n과 num에 같은 수가 몇 개인지, 그 수는 무엇인지 저장을 하여 if문으로 나누어 따로 출력하는 부분을 만들었다. 상당히 비효율 적으로 풀었다 생각하여 다른 사람의 풀이를 본 결과 sorted 함수를 사용하여 간단히 풀 수 있는 걸 배우게 되었다.

BOJ 2530

공백을 기준으로 나누어진 시간, 분, 초를 입력받은 후 초를 입력받아 시간을 계산해서 출력하는 문제. 입력받은 시간을 초로 계산 후 더한 다음, 다시 계산하여 풀었다.

BOJ 1267

휴대폰 요금제 2개가 있을 떄 어떤 요금제가 더욱 싼지 출력하는 문제. 나누기 연산과 삼항 연산자를 이용하여 풀었다.

BOJ 1254

문자열 s를 입력받은 후 문자열의 뒤부터 0개 이상의 단어를 추가해서 만들 수 있는 펠린드롬 단어중 제일 짧은 단어의 길이를 출력하는 문제. 내 풀이는 펠린드롬 인지를 확인하는 함수를 만든 후, 문자열의 길이만큼 반복문을 수행하며 s에 s[0:i+1]을 reversed하여 더한 문자열을 펠린드롬 확인 함수를 사용하여 정답을 출력하였다. 1234 + 1 > 1234 + 21 > 1234 + 321 다른 사람의 풀이는 s를 앞에서부터 슬라이싱한 값에 reversed한 문자열이 있는 지 확인하는 방식이다.

BOJ 1260

정점의 개수 n, 간선의 개수 m, 시작할 정점의 번호 start를 입력받은 후 그래프를 dfs, bfs로 읽었을 때 순서를 출력하는 문제. 그래프는 양방향으로 이어지는 정점 x y를 입력받는데, 이를 딕셔너리로 저장을 하였다. bfs와 dfs 모두 함수로 구현을 하였으며 deque를 import하여 사용을 하였으며 bfs는 큐를 이용하여 sorted한 연결된 정점들을 큐에 넣으며 풀었으며, dfs는 스택을 이용, reverse=True한 sorted한 연결된 정점들을 스택에 넣으며 풀었다.

BOJ 2606

정점 1과 연결된 모든 정점들의 수를 출력하는 문제. 스택을 사용하는 dfs를 구현하여 len(visit)-1 하여 풀었다.

BOJ 2667

n*n의 크기의 0과 1로 이루어진 2차원 배열을 입력받은 후, 상하좌우 연결된 1의 수의 집합들의 수와 각 집합의 수를 정렬하여 출력하는 문제. 재귀적으로 배열의 상하좌우가 1인지 확인하며 count에 1씩 더하며 count를 반환하며 해당 배열 인자를 0으로 바꾸는 함수 dfs를 만들었으며, 이 중 배열의 크기를 넘는 경우를 위해 두 개의 조건문 중에 배열의 크기 확인을 and 앞에두는 것으로 방지할 수 있다는 것을 배웠다. 이후 배열의 모든 부분을 2중 반복문을 사용하여 1인지 확인하여 ans 리스트에 append한 후 sorted와 len 함수를 사용하여 풀었다.

BOJ 10872

숫자 n을 입력받은 후 n!을 출력하는 문제. math 라이브러리의 factorial을 import해서 풀었으며, 재귀 함수를 구현해서 풀기도 하였다.

BOJ 13752

테스트케이스 횟수 n을 입력받은 후 입력되는 숫자만큼 '='을 출력하는 문제 반복문과 문자열 곱하기 연산을 이용하여 풀었다.

BOJ 15000

입력되는 문자열을 대문자로 변환하여 출력하는 문제. 문자열 내장 함수 upper을 이용하여 풀었다.

BOJ 2178

미로의 크기 n, m이 주어진 후 1과 0으로 이루어진 미로가 입력된다 1은 이동할 수 있는 곳, 0은 이동할 수 없는 곳이라고 하였을 때, (0, 0)에서 출발하여 (n-1, m-1)까지 걸리는 최단 거리를 계산하는 문제. 방문했는지 확인, 거리를 저장할 2차원 배열을 만들었으며, 상하좌우 방문 확인 배열의 값이 False인지, 그래프의 값이 1인지를 확인한 후 deque에 append하여 풀었다.

BOJ 1325

두 개의 컴퓨터 번호 x, y가 주어졌을 때 y를 해킹하면 x도 해킹할 수 있다고 한다. 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 문제. 첫 풀이는 dfs, 깊이우선탐색으로 구현을 하였으나 백준풀이상 시간초과 결과를 받게 되었고, 검색 후 deque를 사용한 bfs와 sys.stdin.readline을 사용하여 시간을 줄이고 기존 내 풀이와 다르게 그래프를 2차원 배열로 저장하였다. 그렇게 하여도 백준 python3 채점 기준에는 통과하지 못하여 pypy3로 변경하여 풀 수 있게 되었다.

BOJ 5567

정해진 수만큼의 x y와 같이 연결된 정점이 입력된다. 정점 1과 연결된 정점들의 정점까지 갯수를 출력해야 한다. 정점 1과 연결된 정점이 2와 3이면 정점 2, 3을 포함한 2, 3 정점과 연결된 정점의 수를 출력하는 문제. 입력되는 수를 바탕으로 양방향 그래프를 만든 후, extend를 사용하여 1과 연결된 정점들을 리스트 que에, 중복을 제거하기 위해 집합 자료형 visit에 graph[1]을 넣었다. que에 든 정점 1과 연결된 정점 i를 사용하여 반복문을 수행하며 그 안에 graph[i]를 기준으로 반복문을 수행하며 안의 값을 집합 자료형 visit에 넣었다. 정답은 1을 제외해야하기 때문에 len(visit) - 1을 하여 풀었다.

BOJ 1620

n, m을 입력받은 후 n개의 포켓몬 이름을 입력받는다. 그 후 m만큼 문자열을 입력했을 때, 해당 포켓몬의 번호를, 숫자를 입력했을 때, 해당 포켓몬의 이름을 출력하는 문제. 첫 풀이는 try, except를 이용하여 숫자인지 문자열인지, list.index()를 이용하여 해당 포켓몬 번호를 출력하여 풀었으나 시간초과 결과를 받게 되었고 두번째 풀이는 딕셔너리 자료형에 key를 포켓몬 이름으로, value를 포켓몬 번호로 저장하여 int(s)에서 except됐을 때 딕셔너리 자료형을 이용하여 출력하여 풀었다. 다른 사람의 풀이에서 문자열에 isdigit 함수가 있는 것을 보고 바꾼 것이 세번째 풀이이다.

BOJ 1676

n!의 뒤에서부터 0이 몇 개까지 이어지는 지 출력하는 문제. 첫 풀이는 팩토리얼을 재귀적으로 계산하는 함수를 만든 후 reversed와 반복문을 이용하여 정수형 변수 ans를 1씩 더하여 풀었다. 다른 사람의 풀이를 보니 수식으로 풀 수 있다는 것을 알아 두번째 풀이에서 적용해 보았으며 뒷자리 0의 갯수는 2와 5의 갯수로 판단되는 것을 알게 되었다.

BOJ 7576

n, m 크기를 가진 2차원 배열을 입력받는다. 1은 익은 토마토, 0은 안익은 토마토, -1은 벽을 뜻한다. 익은 토마토는 하루에 상하좌우 안익은 토마토를 익게할 수 있는데 이 때 모든 토마토들이 익는 날짜를 출력하는 문제. 이미 모든 토마토들이 익은 상태일 때는 0을, 모튼 토마토들이 익을 수 없을 땐 -1을 출력하는 문제. 방문여부와 거리날짜를 확인할 2차원 리스트 check와 dist를 사용했다. 입력간에 1이 아예 없을 때를 확인하여 -1을 출력한 후 실행을 종료할 isnone 변수도 사용하였다. 추가적으로 입력간에 1일 때를 확인하여 큐에 추가, check와 dist를 True와 0으로 변환하였다. 그 후 큐를 이용하여 상하좌우 check가 false이며 그래프의 값이 0인 요소를 찾아 1로 바꾸었다. dist는 현재 큐의 값에 1을 더하였다. 문제의 정답을 위해 2중 반복문을 수행하여 그래프에 0이 있을 때 -1을 출력한 후 실행을 종료, 제일 큰 dist의 값을 day에 저장하여 출력하여 풀었다.

BOJ 7569

7576번 문제가 2차원 배열의 토마토 상자였으면, 이번 문제는 3차원 배열의 토마토 상자인 문제이다. 7576번 문제의 풀이와 다르게 visit 배열을 만들지 않고 풀었으며 dx, dy, dz 배열에 6개 요소를 넣어 6번 반복을 하여 날짜를 계산하는 dist 배열에 값을 넣어 3중 반복문을 통해 비교하여 출력하여 풀었다.

BOJ 11723

1부터 20의 범위를 갖는 공집합이 있을 때 추가, 삭제, 확인, 토글, 전체 1로 만들기, 전체 0으로 만들기 기능이 있는 공집합을 구현하는 문제. 첫 풀이는 파이썬의 set 자료형을 사용하여 풀려했으나 확인 후 출력할 때 효율적이지 못할 거 같아 21의 크기를 갖는 리스트 자료형을 만들어 0과 1로 구분지어 풀었다. 토글은 not 1 or 0을 int로 저장하여 풀었다.

BOJ 5532

방학의 일수, 국어 숙제량 A, 수학 숙제량 B, 하루에 풀 수 있는 국어, 수학 숙제량 각 C, D라고 할 때 숙제를 안하고 노는 방학의 일수를 출력하는 문제. 삼항 연산자를 이용하여 나누기, 나누기 값 연산을 비교해서 풀었다. 다른 사람의 풀이로는 (A+C-1)//C와 같은 연산을 이용하여 푼 것을 배웠으며 내 수학적 사고능력이 너무 부족하다 생각된다.

BOJ 9095

숫자 1부터 10 이하의 숫자가 입력됐을 때 1, 2, 3만을 이용하여 더하여 나타냈을 때의 경우의 수를 출력하는 문제. 첫 생각은 n을 1로만 더한 식을 이용하여 1 + 1 > 2, 2 + 1 > 3으로 모든 경우에 적용하여 풀 생각을 하였으나 비효율적이라 생각되어 고민 후에 1, 2, 3의 경우의 수를 더하면 4의 경우의 수이며 2, 3, 4의 경우의 수를 더하면 5의 경우의 수인 것을 알게 되었다. l[-3::]와 같이 리스트를 슬라이싱하여 풀었다.

BOJ 11726

2xN 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 출력하는 문제. N이 1일 때 1, 2일 때 2, 3일 때 3, 4일 때 5, 5일 때 8이다. 이를 통해 n[i] = n[i-2] + n[i-1]인 규칙을 알아내어 리스트를 [-2::]로 슬라이싱한 값을 sum함수를 이용하여 풀었다.

BOJ 7662

최솟값과 최댓값을 기준으로 두가지의 우선순위를 갖는 큐를 구현하는 문제. bisect를 사용하여 이진탐색 후 deque에 위치파악 후 삼입하는 방법을 사용하여, q[0]에 최솟값, q[-1]에 최댓값이 위치하도록 하였다. 또한 중복되는 값을 허용하며 삭제 시에는 값을 하나만 삭제하기 때문에 딕셔너리 자료형을 사용하여 중복되는 수를 계산하여 주었으며, if not deque처럼 사용하여 deque가 비었을 때 'EMPTY'를, 아닐 때 최댓값과 최솟값을 출력하여 풀었다

BOJ 2630

정수 n을 입력받은 후 n * n 크기의 0과 1로 이루어진 배열을 입력받는다. 그래프에서 0은 흰색, 1은 파란색을 뜻한다. 그래프 안에서 색이 동일한 정사각형의 갯수를 출력하는 문제이며, 동일한 색이 아닐 때 가로와 세로 중간을 잘라 확인을 반복한다. 동일한 색으로 이루어져 있는지 확인하는 함수 isunity의 매개변수로 x와 y의 시작지점과 정사각형의 크기를 뜻하는 size를 입력받는다. 그 후 색을 확인하며 반복문 수행중에 색과 동일하지 않을 때 1, 2, 3, 4분면 각각 size//2를 이용하여 함수를 재귀하여 사용하여 풀었다.

BOJ 11399

정수 n명의 사람이 ATM기를 이용하는데 걸리는 시간을 공백으로 나눠 입력받는다. 이 때 모든 사람들이 걸리는 시간의 최소합을 출력하는 문제. 그리디 알고리즘을 사용하여 sorted 함수를 이용하여 풀었다. 첫번째 풀이는 n+1까지 반복문을 수행하며 리스트를 [0:i]로 슬라이싱한 값을 sum을 이용하여 더한 값을 출력하여 풀었다. 다음 풀이는 입력받은 리스트를 이용하여 반복문을 수행하며 t에 현재 반복인자가 걸리는 시간을 더하며 다른 변수 ans에 t를 더하는 식으로 풀었다.

BOJ 1012

0과 1로 이루어진 2차원 배열을 입력받은 후 상하좌우 연결된 그룹의 수를 출력하는 문제. 첫 풀이로 각 정점을 이차원 배열에 입력한 후, 이차원 배열의 크기만큼 반복문을 수행할 때 방문 여부를 저장하는 배열, 그룹 숫자를 저장할 배열을 이용하여 풀었다. 두번째 풀이에서는 방문 확인 배열 대신 그래프의 값을 수정하는 식으로 수정, 그룹 숫자를 저장하는 배열 대신 정수형 변수를 사용하여 풀었다.

BOJ 1931

회의실 한 개를 사용할 때, n개의 회의 시작시간, 회의 종료시간이 입력된 후 최대한 많은 회의를 할 때 그 수가 무엇인지 출력하는 문제. 입력되는 회의들을 sorted의 key 메소드를 lambda식을 이용하여 종료시간으로 정렬 후 시작시간으로 재정렬한 후, 종료시간과 시작시간을 확인하여 정수형 변수를 1씩 늘려 풀었다.

BOJ 11724

입력될 노드의 수 n과 간선의 수 m을 입력받은 후 뱡향 없는 그래프를 x, y를 입력받는다. 그 후 연결 요소의 개수를 출력하는 문제. 그래프를 n+1 크기를 갖는 2차원 배열로 만들어 0과 1로 연결돼 있는 지 판단 했으며 방문한 적이 있는지 확인할 리스트를 n+1 크기로 만들어 사용했다. dfs 함수를 각 연결된 노드들을 재귀적으로 호출하여 visit 리스트의 값을 1로 수정하여 풀었다. 추가적으로 지금까지 A == 1, A == 0으로 사용했던 것을 가독성을 생각해 A, not A와 같이 바꾸어도 보았다.

BOJ 2443

역삼각형을 만드는 별찍기 문제. n부터 0까지 반복문을 사용했으며 공백을 n - i개 출력, 별을 i * (i - 1)개 출력한 후 줄바꿈하여 풀었다.

BOJ 10886

0과 1을 n개 입력받은 후 더 많이 입력된 값에 해당하는 문자열을 출력하는 문제. 정수형 변수에 삼항연산자를 사용하여 1을 더하거나 빼었다. 그 후 0과 크기를 비교하여 문자열을 삼항연산자를 사용하여 출력해 풀었다.

BOJ 11279

�최대 힙을 구현하는 문제. 0이 입력됐을 때 해당 배열에서 제일 큰 수를 출력 및 제거하고 다른 수가 입력됐을 때 배열에 추가하는 문제. bisect의 insort를 이용하여 배열에 추가할 때 정렬하여 넣은 후, 리스트의 pop을 이용하여 출력하였다

BOJ 1927

최소 힙을 구현하는 문제. 0이 입력됐을 때 해당 배열에서 제일 작은 수를 출력 및 제거하고 다른 수가 입력됐을 때 배열에 추가하는 문제. 첫 풀이는 위 문제와 동일하게 insort를 사용했다. 추가적으로 리스트의 pop(0)의 시간복잡도보다 우위에 있는 deque의 popleft를 사용했는데도 시간초과 결과를 받게 되었다. 두번째 풀이는 파이썬의 내장 heapq를 import하여 heappush와 heappop을 사용하여 풀었다.

BOJ 18870

n개의 수열이 입력되며 해당 수열을 좌표 압축하여 출력하는 문제. 첫 풀이는 sorted를 이용하여 정렬, set을 이용하여 중복된 값 제거를 한 후 zip을 이용하여 2개의 인자를 갖는 for문을 이용하여 딕셔너리 자료형에 저장, 딕셔너리 자료형을 이용하여 출력하여 풀었다. 두번째 풀이는 enumerate를 사용하여 더욱 편하게 풀었으며 이 때문에 n을 사용하지 않고 풀었다.

BOJ 1697

현재 위치와 목표 위치 n, x가 입력된다. 현재 위치에서 1초 후에 n*2, n+1, n-1의 위치로 이동할 수 있을 때 목표 위치 x에 도착하는 가장 빠른 시간이 몇 초 후인지 구하는 문제. 첫 풀이는 너비 우선 탐색 bfs로 구현을 하였다. 딕셔너리를 만들어 방문 확인을 했으며 방문하지 않았을 때 q에 추가하여 풀었다. 이 방법으로 풀었을 때 백준상 메모리초과 결과를 얻게 되었고 이유는 딕셔너리를 계속하여 추가하는 것과 노드의 최대 크기인 100,000을 넘어서까지 계산된 것으로 유추된다. 두번째 풀이는 방문 확인을 100001의 길이를 가진 리스트로, 큐에 위치와 걸린 시간으로 이루어진 배열을 넣어 풀었으며 q에 추가할 때 범위 100,000보다 작은 지 확인하여 추가하여 풀었다.

BOJ 1074

n, r, c를 입력받은 후 2^N * 2^N 크기의 배열을 Z모양으로 탐색할 때, 쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문하면 (r, c)를 몇 번째로 방문하는지 출력하는 문제. 첫 풀이는 배열의 크기, 좌표 4등분을 재귀적으로 사용하는 함수를 구현하여 풀었으나 런타임 에러 결과를 받게 되었다. 재귀의 제한을 늘리니 메모리 초과 결과를 받게 되었다. 두번째 풀이는 목표 좌표가 어느 사분면에 있는 지 계산하여 다른 사분면의 크기만큼 더하는 것과 배열의 크기를 줄이는 것을 반복하여 풀었다.

BOJ 10822

쉼표로 나누어져 있는 정수들로 이루어진 문자열의 총합을 구하는 문제. split(',')과 sum을 이용하여 풀었다.

BOJ 10823

여러 줄로 입력되는 쉼표로 나누어져 있는 정수들로 이루어진 문자열의 총합을 구하는 문제. readlines를 이용하여 EOF까지 입력을 받은 값을 replace('\n', '')을 이용하여 줄바꿈을 공백으로 바꾼 후 문자열에 더한 값을 split()과 sum을 이용하여 풀었다.

BOJ 10870

n번째 피보나치 수열의 수를 출력하는 문제. 재귀를 이용하여 풀었다.

BOJ 10826

n번째 피보나치 수열의 수를 출력하는 문제. 위 문제와 다르게 큰 수가 입력되어 재귀를 이용해서 풀었을 때 시간초과 결과를 받게된다. 단순 반복문을 이용하여 풀었다.

BOJ 5717

0 0이 입력될 때 까지 입력되는 두 수들의 합을 출력하는 문제. while과 break를 이용하여 풀었다.

BOJ 18406

짝수의 수가 입력되고 좌우 절반으로 나누었을 때, 각 수들을 합친 값을 비교하여 출력하는 문제. 문자열을 len을 이용하여 슬라이싱한 값을 map을 이용하여 형변환, sum을 이용하여 합친 값을 삼항연산자를 이용하여 비교, 출력하였다.

BOJ 10798

5개의 줄에 최대 길이가 15인 문자열이 입력된다. 이 문자열들을 세로로 읽으나 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다는 조건을 지켜 공백없이 연속하여 출력하는 문제. 첫 풀이는 이중반복문과 try, except를 이용하여 풀었다. 두번째 풀이는 해당 문자열의 길이와 비교하여 출력 여부를 결정하도록 풀었다.

BOJ 1913

홀수 n의 크기를 갖는 달팽이 모양의 2차원 배열을 출력하고 n*n 이하의 입력받는 정수의 위치를 출력하는 문제. 반복문 도중 배열의 마지막 값일 때 exit을 이용하여 코드를 중단하도록 풀었다. 방향은 2차원 배열을 이용하여 관리해 주었으며, 같은 방향으로 진행되는 값이 추가되는 조건을 확인하여 방향을 관리하는 반복문 안에 넣어 같은 방향으로 반복되게 풀었다.

BOJ 15650

자연수 n, m이 입력될 때 1부터 n까지 자연수 중에서 중복 없이 m개를 고른 수열, 고른 수열은 오름차순. 위 두개의 조건을 만족하는 수열들을 출력하는 문제. 두가지 풀이 모두 m과 비교를 하여 출력과 return으로 함수의 종료를 작성하였다. 첫번째 풀이는 한 개의 매개변수를 사용하여 풀었으며 반복문 안에서 i보다 큰 수들의 방문 확인 배열 값들을 바꿔주는 2중 반복문을 사용하였다. 두번째 풀이는 크기와 현재 인덱스 값을 저장할 매개변수 두 개를 사용하였다. 인덱스값부터 n까지 반복문을 실행하고 방문하지 않은 값일 때 방문 확인, 배열에 추가 후 현재 반복중인 i를 이용하여 재귀적으로 호출하였다. 그 후 다음 반복을 위해 현재 i값만 방문 확인 값을 바꿔주었다.

BOJ 15649

자연수 n, m이 입력될 때 1부터 n까지 자연수 중에서 중복 없이 m개를 고른 수열들을 출력하는 문제. 방문 확인 배열을 사용했으며 매개변수로 길이를 확인하여 출력 및 return으로 함수를 종료하였다. n까지 반복문을 수행하고 방문 확인을하여 넘어가도록 하였다. 그 후 배열에 추가 및 방문 확인 배열을 수정한 후 재귀적으로 함수를 호출하였다. 그 후 다음 반복을 위해 방문 확인 배열을 재수정, 방금 들어간 배열의 요소를 삭제하기 위해 pop하여 풀었다.

BOJ 15654

자연수 n, m이 입력된 후 n개로 이루어진 수열이 입력된다. 이 때 중복 없이 m개를 고른 수열들을 출력하는 문제. sorted를 이용하여 입력되는 수열을 정렬하여 저장하였다. 위에 백트래킹 문제들은 리스트를 사용하여 방문 확인을 하였지만 이번 문제에서는 수열에 규칙이 없어 딕셔너리 자료형을 이용하여 방문 확인을 하여 풀었다.

BOJ 5218

테스트 케이스가 주어진 후 공백으로 구분된 길이가 똑같은 단어가 입력된다. 각 단어의 자릿수마다 차이값을 출력하는 문제. 'B'와 'D' 사이의 거리는 4 - 2 = 2이고, 'D'와 'B' 사이의 거리는 (2+26) - 4 = 24처럼 차이값을 계산하면 된다. 계산을 위한 함수를 구현했으며 아스키코드 값을 반환하는 ord 함수를 이용하여 풀었다.

BOJ 15651

자연수 n, m이 입력될 때 1부터 n까지 자연수 중에서 m개를 고른 수열을 같은 수를 여러 번 골라도 되는 조건하에 출력하는 문제. 이전 백트래킹 문제과 같이 길이를 비교하여 출력 및 종료, 배열에 추가, 재귀적으로 호출, 배열 pop을 동일하게 사용하여 풀었으며 같은 수를 여러 번 골라도 되기에 방문 확인을 빼서 풀었다.

BOJ 5555

길이가 최대 10인 문자열이 s가 입력되며 n만큼 길이가 최대 10인 문자열들 l이 입력된다. l의 문자열은 끝에서부터 처음으로 이어서 읽을 수 있을 때 s가 들어있는 l의 수를 출력하는 문제. s의 길이가 더욱 클 수 있다면 s의 길이에 따라 l을 계속 곱해야겠지만 둘의 최대 길이가 같다. 그렇기 때문에 l * 2한 값에 s가 있는지 in을 사용하여 간단히 풀었다.

BOJ 15652

자연수 n, m이 입력된 후 '1부터 N까지 자연수 중에서 M개를 고른 수열', '같은 수를 여러 번 골라도 된다', '고른 수열은 비내림차순이어야 한다'. 위 세 조건을 만족시키는 수열을 모두 구하는 문제. 백트래킹 문제로써 방문 확인을 하지 않고 함수의 매개변수 index를 추가 및 판단하여 풀었다.

BOJ 9465

자연수로 이루어진 2행 n열의 배열이 주어질 때 상하좌우의 값은 더하지 못하는 조건하에 더한 최대 값을 출력하는 문제. 인덱스 1의 값은 왼쪽 대각선의 값을 더한 후, 인덱스 2부터 n-1까지 왼쪽 대각선 값과 그 왼쪽의 값을 비교해 더 큰 값을 해당 인덱스의 값과 더한 것을 저장했다. n-1의 상하 값 중에 큰 것을 비교하여 출력해 풀었다.

BOJ 1149

n개의 줄만큼 3개의 정수들이 입력된다. 앞뒤로 같은 인덱스에 있는 값을 선택하지 못하는 조건을 지키며 각 줄마다 한 개의 정수를 더한 최솟값을 출력하는 문제. 간단한 dp 문제로써 2차원 배열을 사용하여 풀었다. 1부터 n-1까지 반복을 수행하며 dp[i][0]에 dp[i-1][1]과 dp[i-1][2] 중 작은 값들 더하는 행위를 반복하였다. 마지막에 dp[n-1]중 제일 작은 값을 출력하여 풀었다.

BOJ 9663

[n][n] 크기의 체스판에서 n개의 퀸이 있을 때 서로 공격할 수 없는 자리의 경우의 수를 출력하는 문제. 첫 풀이는 False로 이루어진 2차원 배열을 사용하였다. 2중 반복문을 수행하고 False일 때 해당하는 상하좌우와 대각선을 체크해주는 함수를 만들어 값을 변환시킨 후 재귀적으로 호출하였다. 하지만 이 방법은 성공한 풀이가 되지 못했다. 값을 false로 바꿀 때 현재 반복중인 퀸이 체크한 부분만 false를 해야하는데 해당 방법을 해결하지 못했다. 두번째 풀이는 좌표를 압축하여 사용할 3가지 1차원 배열을 만들었다. 대각선 배열의 길이는 2*n-1의 수식을 사용하였다. 백트래킹의 기본적인 부분은 똑같으나 n과 비교하는 depth를 하나의 행으로 사용하며 해당 대각선을 계산하는 공식이 나는 유추해내지 못했을 것 같다. 오른쪽 위로 향하는 대각선은 depth + 현재 반복 인자인 i이며 왼쪽 위의 인덱스가 0이다. 오른쪽 아래로 향하는 대각선은 depth - i + n - 1의 수식을 사용하며 오른쪽 위의 인덱스가 0이... 더 열심히 해야겠다.

BOJ 1225

12 과 34가 입력 됐을 때, 1x3 + 1x4 + 2x3 + 2x4처럼 두 수의 각 자리수를 곱하여 더한 값을 출력하는 문제. 0을 replace로 없애 시간을 줄였으며 그 후 이중반복문을 이용하여 계산하였다.

BOJ 2083

이름과 키, 몸무게가 입력됐을 때 조건에 맞게 고급반, 초급반을 나누어 출력하는 문제. map과 비교 연산자를 이용하여 간단히 풀었다.

BOJ 2522

별찍기 문제. 3이 입력됐을 때 공백2개 별 1개, 공백 1개 별 2개, 별 3개, 그리고 다시 공백 2개 별 1개까지 찍으면 되는 문제. -n부터 n까지 반복문을 작성하고 절댓값을 사용하여 풀었다.

BOJ_14425

정수 i와 j를 입력받은 후 j개의 문자열 중에 i개의 문자열에 몇 개 있는지 출력하는 문제. i개의 문자열을 중복되지 않고 리스트보다 찾을 때 빠른 집합 자료형을 이용하여 풀었다.

BOJ 11725

그래프의 루트가 1일 때 n개의 노드들을 입력받은 후 2번째 노드부터 부모 노드를 출력하는 문제. n의 길이만큼 0으로 이루어진 리스트를 만든 후 노드를 쌍방향으로 저정한다. 자식 노드를 찾고 리스트의 해당 자식 노드 -1 인덱스의 값이 0일 때 현재 노드의 값을 저장하는 함수를 만들고 재귀적으로 호출한다. 리스트의 2번째 인자부터 출력하여 풀었다.

BOJ 13549

BOJ 1697의 변형 문제. 기존 좌표 x*2에는 1초가 추가됐으나 이번 문제에서는 초가 추가되지 않는다. 문제에서 n이 k의 좌표까지 가는 가장 빠른 시간을 요구하기 때문에 queue에 추가할 때 왼쪽에 추가하여 우선도를 높여 풀었다.

BOJ 1932

다이내믹 프로그래밍 문제. n개의 층으로 이루어진 삼각형을 입력받은 후. 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합의 최대를 출력하는 문제. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있는 조건이 있다. 0~n층까지 i라고 했을 때. 각 층은 i+1개의 요소로 이루어져 있는 것을 이용하여 [i-1][j]에 [i][j]와 [i][j+1] 중 큰 것을 더하여 풀었다.

BOJ 10995

별 찍기 문제. 열에 따라 ' *'와 '* '을 나누어 곱한 값을 출력하여 풀었다.

BOJ 12865

정해진 무게 한도에 맞춰서 최대의 가치를 출력하는 배낭, 다이내믹 프로그래밍 문제. [물건의 수][무게의 크기] 만큼 배열을 만든 후 물건 > 무게순으로 반복을 수행한다. 그 후 현재 반복중인 무게에 따라 넣을 수 없으면 같은 무게, 저번 반복 배열 값을 할당. '들 수 있으면 같은 무게, 저번 반복' 값과 '현재 물건의 가치 + 저번 물건의 현재 반복 무게 - 현재 물건의 무게 배열' 값 중 큰 것을 할당하여 풀었다.

BOJ 1991

이진 트리를 '부모 왼쪽자식 오른쪽자식' 형태의 문자열로 입력받은 후 전위, 중위, 후위 순회한 결과값을 출력하는 문제. 딕셔너리 형태로 graph[부모] = [왼쪽자식, 오른쪽자식] 형태로 저장했다. 모든 순회는 재귀형식으로 작동하며 전위 순회는 출력 후 왼쪽, 오른쪽자식 순으로 재귀적으로 호출. 중위는 왼쪽 자식 호출 후 출력, 오른쪽 자식 호출. 후위는 왼쪽, 오른쪽 자식 호출 후 출력하여 풀었다.

BOJ 11659

n과 m을 입력받은 후 n만큼의 크기의 일차원 배열을 입력받는다. 그 후 m번만큼 인덱스 i, j까지의 합을 출력하는 문제. 완전 탐색을 사용하여 풀 경우 시간초과 결과를 받게되어 누적합을 이용하여 풀었다. l_add 리스트에 n만큼 반복을 하는 i를 이용하여 l_add의 마지막 값과 입력받은 일차원 배열의 i번째 값을 더하여 누적합 리스트를 구현했다. i가 1일 때 누적합 리스트의 j번째 요소를 출력, 아닐 때 누적합 리스트의 j번째 값에 i-1째 값을 빼 출력하여 풀었다.

BOJ 11660

n과 m을 입력받은 후 n*n의 크기의 이차원 배열을 입력받는다. 그 후 m번만큼 (y1, x1), (y2, x2)의 합을 구하는 문제. 완전 탐색을 사용하여 풀 경우 시간초과 결과를 받게되어 누적합을 이용하여 풀었다. n을 이용하여 2중 반복문을 수행하며 열마다 누적합 리스트를 만들었다. 그 후 y1-1부터 y2까지 반복하여 정수형 변수 ans에 누적합 결과를 더한 후 출력하여 풀었다. 2차원 누적합을 공부 및 구현할 필요를 느꼈다.

BOJ 1753

정점의 개수 v, 간선의 개수 e, 시작 정점 k를 입력받은 후 각 '출발지 도착지 거리'를 u, v, w로 입력받은 후 1부터 v까지 모든 정점을 가는 데 걸리는 최�단 경로 값을 출력하는 다익스트라 문제. graph[출발지] = {도착지: 거리, 도착지1: 거리}와 같이 입력받아 사용하였다. 두 풀이 모두 힙을 사용하여 최소 거리를 먼저 연산하였다. 첫번째 풀이는 큐에 [거리, 도착지, 출발지]와 같이 넣어 출발지가 시작 노드가 아닐 때 dist[출발지] 값과 거리를 계산하여 넣어 풀었으나 시간초과 결과를 받게 되었다. 두번째 풀이는 큐에 넣는 연산을 하는 반복문에서 dist에 값을 할당하여 풀었다. 자세한 풀이는 주석에 설명해 놓았다.

BOJ 1446

다익스트라 문제인 줄 알았던 다이내믹 프로그래밍 문제. 지름길의 수 n과 도착지의 거리 d가 주어진다. 그 후 u, v, w 각각 시작점, 도착점, 소모시간이 주어진다. 뒤로 돌아갈 순 없을 때 도착지까지 걸리는 최소 소모시간을 출력하는 문제. 지름길을 {시작점: [[도착지, 소모시간], [도착지1, 소모시간1]]} 형태로 저장하였다. d의 최대 크기인 10000까지의 배열을 생성 후 입력된 정수현 변수 count가 d와 같을 때까지 반복을 수행한다. 그 후 현재 count가 시작점인 지름길이 있을 때 도착지의 값을 현재 값과 소모시간 값을 더한 것과 현재 저장된 값 중 작은 것을 할당한다. 그 후 배열의 다음 값을 저장된 값고 현재 값 + 1중 작은 것을 할당하여 풀었다.

BOJ 1967

노드의 수 n과 n-1만큼의 '출발지 도착지 거리'를 입력 받는다. 이 때 노드와 노드의 거리가 최대인 일명 '트리의 지름'을 출력하는 문제. 첫번째 풀이는 힙을 사용할 때 '-가중치'하여 max 힙을 이용하여 루트 1부터 모든 노드까지의 거리를 이용할려 했으나 다시 처음부터 풀기로 하였다. 두번째 풀이는 큐를 이용하여 시작 노드부터 다른 모든 노드들까지의 최대 거리와 최대 거리를 갖는 노드를 반환하는 함수를 작성하여 위 함수를 두번 호출하여 풀었다. 자세한 풀이는 주석에 설명해 놓았다.

BOJ 1167

위와 같이 '트리의 지름'을 구하는 문제. 다른 점은 트리를 입력받을 때 '시작점 도착지1 거리1 도착지2 거리2 -1'과 같은 형태로 입력되는 것 이다. 입력되는 줄을 1부터 길이-1까지 2칸씩 진행하여 {시작점: [[도착지, 거리], [도착지1, 거리1]]}과 같은 형태로 저장하였다. 트리를 이동하는 연산은 위 문제와 동일하게 풀었다. 자세한 풀이는 위 문제의 주석에 설명해 놓았다.

BOJ 15657

백트래킹 문제. n개의 자연수들을 같은 수를 여러 번 골라도 되며, 비내림차순으로 정렬된 길이가 m인 수열들을 출력하는 문제. 입력되는 자연수들을 sorted를 사용하여 정렬 후 배열의 마지막 값과 비교하여 배열에 추가하는 연산을 재귀적으로 활용하여 풀었다.

BOJ 1158

1번부터 n번까지의 사람들이 원을 이루며 앉아있을 때 순서대로 k번째 사람들을 제거한다. 제거된 사람의 순서를 출력하는 '요세푸스 순열' 문제. 1부터 n까지의 리스트와 정답이 들어갈 빈 리스트, 몇번째 요소를 pop할지를 관리할 정수형 변수를 이용했다. 정답 리스트의 길이가 n이 아닐 때까지 반복, 'i = (i + (k-1)) % n까지 들어있는 리스트의 길이'를 계산하여 pop한 값을 빈리스트에 넣어 출력하여 풀었다.

BOJ 1916

도시 n개, 버스 노선 m개를 입력 받은 후, m개의 노선들을 '출발지 도착지 비용'과 같이 입력받은 후 '출발지 도착지'를 입력받아 출발지에서 도착지까지 가는 최소비용을 출력하는 문제. 다익스트라 문제로써 그래프에 [{도착지1: 비용1}, {도착지2: 비용2, 도착지3: 비용3}]과 같이 저장하여 인덱스를 출발지로 사용하였다. 그 후 힙연산, 각 노드마다 최소 비용을 저장하는 리스트를 이용하여 풀었으나 백준상에서 메모리 초과 결과를 받게 되었다. 그래프의 아이템들을 이용하는 반복문전에 저장돼 있는 값과 비교하는 부분을 넣어 메모리 초과를 해결하여 풀었다. 재채점 결과 메모리초과가 되어 동일한 방법으로 문법만 편해진 방법으로 작성하여 풀었더니 CA 결과를 다시 받았다. 4달전에 비해서 많이 성장했다고 느꼈다.

BOJ 9251

두 문자열을 입력받은 후 최장 공통 부분 수열의 길이를 출력하는 문제. 다이내믹 프로그래밍 방법을 이용하여 풀었다. 현재 문자가 동일 시에 현재 문자가 포함되지 않은 최장 공통 부분 수열의 길이 + 1, 포함되지 않을 시 현재 문자가 포함하지 않은 y문자, x문자의 값 중 큰 것을 배정, 배열의 마지막 값을 출력하여 풀었다.

BOJ 11047

n가지 종류의 동전으로 금액 k를 맞출 때 동전의 최소 개수를 출력하는 그리디 알고리즘 문제. n가지 동전은 오름차순으로 입력되기 때문에 reversed를 이용하여 높은 금액부터 나머지와 몫을 계산하는 연산자를 이용하여 풀었다.

BOJ 3020

석순과 종유석이 번갈아 있는 길이가 n, 높이가 h인 터널이 있다. 이때 1~h 높이의 구간으로 지나갈 때 만나는 석순 혹은 종유석의 개수 중 최소와 동일한 개수를 갖는 구간의 수를 출력하는 문제. 첫풀이는 석순 혹은 종유석의 길이를 입력할 때 마다 이차원배열의 [길이][높이]에 [길이-1][높이]의 값을 이용하여 연산하여 풀었으나 메모리 초과 결과를 받게 되었다. 두번째 풀이는 누적합을 이용한 연산으로 높이의 종유석, 석순의 개수를 누적합으로 계산 후 각 높이마다 석수 + 종유석의 값을 계산하여 풀었다.

BOJ 2851

10개의 수열이 입력되며 순서대로 합을 계산할 수 있다. 이 때 처음부터 합할 때 100과 제일 가까운 수를 출력하는 문제. 매 입력마다 절댓값을 이용하여 저번 합과 현재 입력된 값 + 저번 합을 100과의 차이를 이용하여 비교해 저장 후 출력하여 풀었다.

BOJ 12851

현재 위치 n과 이동해야 할 목적지 k가 주어질 때, 1초 후에 n+1, n-1, n*2로 이동할 수 있다. 이 때 k까지 가는 최소 시간을 출력하고 동일한 시간으로 갈 수 있는 방법의 수까지 출력하는 문제. 최소 시간은 간단히 풀었으나 방법까지 구하는 데 시간이 상당히 소요되었다. 첫 풀이는 시간을 기준으로 힙연산을 통해 풀었으나 시간초과 결과를 받게 되었다. 두번째 풀이는 bfs 연산을 하였으며 방문확인으로 0으로 이루어진 리스트를 사용했다. 목적지에 처음 방문 했을 때 방문 리스트에 현재 소모된 시간을 저장하였으며, 첫 방문이 아니며 시간이 똑같을 때는 횟수를 저장하는 정수형 변수 ans의 값을 추가해 주었다. 그리고 큐에 추가하는 연산을 실행할 때, 첫 방문 혹은 방문지에 저장된 시간이 다음에 저장될 시간보다 클 때 추가하였다. 목적지에 저장된 값 그리고 다음 연산될 시간이 다음 값에 저장된 값보다 클 때를 예외처리 하여 풀었다. 자세한 풀이는 주석에 설명해 놓았다.

BOJ 1504

정점의 개수 n, 간선의 개수 e를 입력받은 후 e의 개수만큼 "출발지 도착지 가중치"를 입력받는다. 그 후 정점의 두개 v1, v2를 입력받은 후 정점 1부터 n까지 v1, v2를 반드시 통과한 최단거리를 출력하는 문제. 첫 접근은 deque의 appendleft를 이용하여 다음 방문지가 v1 혹은 v2일 때 우선순위를 높이는 방식이였으나 실패하게 되었다. 접근을 바꾸어 시작, v1, v2에서 출발하는 최단거리 리스트를 저장하고 s > v1 > v2 > n과 s > v2 > v1 > n을 계산 및 비교하여 출력하여 풀었다. 간선을 저장할 때 유무를 찾아 추가하는 방식에서 런타임 에러가 일어나, 수정하여 풀었다.

BOJ 16953

a는 a * 2, a의 왼쪽에 1붙이기의 연산이 가능할 때 b가 되는 연산의 최솟값을 출력하는 문제. bfs를 이용하여 풀었으며 q에 추가할 때 b와 크기를 비교하였으며 반복문이 종료시까지 return이 안됐을 때 -1을 return하여 풀었다.

BOJ 15663

n개의 수를 m개의 수열로 만들어서 출력하되 n개의 수 중에 중복된 수가 있으며, 중복된 수열은 출력하지 않는 조건이 있는 백트래킹 문제. 깊이를 비교하여 출력하며 반복문의 현재 값과 다음 값이 같지 않을 때를 확인하여 풀었다.

BOJ 1339

n개의 알파벳으로 이루어진 문장을 입력받는다. 각 알파벳을 숫자로 바꾼 후 합하였을 때 최대값이 무엇인지 출력하는 문제. 첫 풀이는 문자열을 거꾸로 배열에 삽입한 후 자리수가 클 수록 알파벳에 해당되는 수가 커야하는 것을 이용하여 딕셔너리에 저장 여부를 확인하여 값을 할당 후 배열에 값 수정을 하였다. 그 후 배열을 뒤집어 int형으로 형변환하여 더한 값을 출력하여 풀었다. 하지만 자리수 이외에 빈도수 또한 중요도에 영향을 미치기 때문에 틀렸습니다 결과를 받게 되었다. 두번째 풀이는 길이 26의 배열을 만든 후 문자열의 자릿수 만큼 해달 배열의 값을 더해주어 중요도를 저장, 내림차순으로 정렬한 배열에 9부터 중요도를 곱하여 더한 값을 출력하여 풀었다.

BOJ 15666

n개의 수 중에 m개의 수를 비내림차순으로 만든 수열을 출력하는 백트래킹 문제. 같은 수가 여러번 입력되며 동일한 수열은 출력하면 안되는 조건이 있기에 제일 최근 리스트에 추가한 수를 비교, 전 재귀에서 사용한 값과 비교하여 풀었다.

BOJ 1865

도로는 방향이 없는 양의 가중치를 갖는 간선이며 웜홀은 방향이 있는 음의 가중치를 갖는 간선일 때, 다시 시작점으로 왔을 때 음의 값을 갖을 수 있는지, 즉 negative cycle이 존재하는 지 출력하는 문제. 첫풀이는 기존에 사용하던 다익스트라 방법을 이용하여 현재 정점이 출발 정점이며 값이 음수일 때 return, 정점의 수만큼 함수를 실행하여 풀었으나 시간초과 결과를 받게 되었다. 두번째 풀이는 정점의 수 _ (정점의 수 _ 모든 간선)을 수행하며 반복되는 정점이 마지막 정점이며 값이 갱신될 때를 확인하여 풀었다.

BOJ 11657

n, m 각각 정점, 간선의 수를 입력받은 후에 m만큼 s, e, w, 시작점, 도착점, 가중치를 입력받으며 가중치는 음수가 입력될 수도 있다. 시작점은 1이며 다른 정점까지 도착하는 최소 가중치를 출력하되, 네거티브 사이클이 있을 때는 -1을, 도착하지 못하는 정점은 -1을 출력하는 문제. 첫풀이는 벨만포드 알고리즘을 이용하여 모든 간선을 수행한 거리 값을 저장한 후 다시 모든 간선을 수행할 때 값의 차이가 보일 때 네거티브 사이클이 있다 판명하도록 풀었으나 틀렸습니다 결과를 받게되어 BOJ 1865와 같이 3중 반복문을 수행하여 풀었다. i가 마지막 정점인 것만 확인 시에 1과 이어져있지 않은 정점이지만 네거티브 사이클이 있는 예외 경우가 존재하여 최대 간선의 수와 가중치의 최대 값을 곱한 값보다 작으며 계속해서 줄어들 경우만 예외처리하여 풀었다.

BOJ 2579

다이내믹 프로그래밍 문제. n개의 수열이 주어지고 인덱스 +1, +2 값을 더할 수 있으나 연속하여 3개의 인덱스 값을 더할 수 없을 때 마지막 인덱스 값을 포함한 최대 값을 출력하는 문제. 합한 값을 저장할 dp, 인덱스의 값을 저장할 l, 리스트 2개를 사용했다. dp 0, 1, 2의 값은 수동적으로 작성 후 3부터 n까지 반복문을 이용하였다. i번째 값은 i-2의 합한 값 (+2), i-3의 합한 값 + i-1(+2+1)의 인덱스 값 중 더욱 큰 것을 비교하여 풀었다.

BOJ 2557

nodejs를 이용하여 푼 첫번째 문제. console.log를 이용하여 출력하여 풀었다.

BOJ 1000

두 수를 입력받은 후 더한 값을 출력하는 문제. fs.readFileSync를 이용하여 백준 테스트 파일들을 읽는 형식으로 풀었다.

BOJ 1918

일반적으로 사용하는 중위 표기식을 입력받은 후. 해당 식을 후위 표기식으로 만든 후 출력하는 문제. 입력된 문자열을 괄호로 감싸 반복문을 수행하고 반복 수행중인 값이 isupper을 이용하여 대문자일 때 출력. '('일 때 스택에 추가. ')'일 때 스택을 pop한 값이 '('일 때까지 출력한다. 그리고 연산자일 때 스택의 마지막 값이 '('가 아니며 스택의 마지막 값을 딕셔너리에 저장된 우선순위로 비교하여 현재 연산자보다 우선순위가 높은 연산자들을 먼저 출력 후 해당 연산자를 스택에 append하여 풀었다.

BOJ 2206

y, x 크기의 0과 1로 이루어진 행렬을 입력받는다. 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽일 때, 벽을 한 번만 부술 수 있는 조건을 이용하여 좌표 (0, 0)에서 (y, x)까지 최단 거리를 출력하는 문제. 첫 번째 풀이는 벽을 부셨는 지 판단하는 변수를 이용하여 함수를 재귀적으로 호출하여 풀었으나 메모리 초과 결과를 받게 되었다. 두번째 풀이는 deque를 이용한 bfs를 이용하여 풀었다. 거리 및 방문을 확인하는 2차원 배열을 이용하여 풀었으나 한 번 부신 후 돌아가는 길이 존재할 때 풀어지지 않았다. 이를 해결하기 위해 방문 및 거리를 확인하는 배열을 3차원으로 만든 후 [is_break][y][x]의 형태로 사용, 대입 시 한번 부쉈을 때의 다음 좌표 = 안부쉈을 때의 좌표 + 1의 형태로 작성하여 풀었다.

BOJ 2193

2진수 중에 처음이 1로 시작하며 1과 1이 붙어있지 않은 수를 이친수라 할 때, n자리수에 이친수가 몇 개가 있는 지 출력하는 문제. 첫번째 풀이는 반복문을 이용하여 i-1 자리수가 0일 때 1로 수정하여 집합 자료형에 추가하는 방식으로 하였으나 수가 커질 때는 연산의 수가 많아져 이 방법은 포기하게 되었다. 고민 중 이친수의 수가 피보나치 수와 같다는 것을 깨닫고 피보나치 수를 반환하는 함수를 만들어 풀었다.

BOJ 1159

n개의 문자열을 입력받고 문자열의 첫번째 글자가 5개 이상 동일할 때 해당 문자를 사전순으로 정렬하여 출력하는 문제. 딕셔너리와 집합 자료형을 이용하여 풀었다.

BOJ 10102

길이 n의 문자열은 A와 B로 이루어져 있으며 문자열을 이루고 있는 더 많은 알파벳을 출력하는 문제. str.count를 이용하여 풀었다.

BOJ 5656

숫자와 함께 비교 연산자로 이루어진 식을 입력받은 후 결과를 출력하는 문제. 문자열을 실행하는 eval을 이용하여 풀었다.

BOJ 10844

자리수 n이 주어질 �때, 모든 자리수의 차이가 1인 수를 계단 수라고 한다. 모든 자리수 개수를 1000000000으로 나눈 수를 출력하는 다이내믹 프로그래밍 문제. n이 1일 때, 각 수로 끝나는 경우는 1부터 9까지 모두 1이다. n이 2일 때, 각 수로 끝나는 경우는 0과 9를 제외하고 n-1의 자릿수 -1과 +1이다. 이를 점화식으로 사용하여 0과 9를 예외처리한 후 dp[y-1][x-1] + dp[y-1][x+1]을 사용하여 풀었다.

BOJ 14501

n일 동안 t일이 걸리는 보수 p가 주어지는 일을 받는다. 한 번에 한가지 일 밖에 할 수 없을 때 n일 동안 얻을 수 있는 보수의 최대치를 출력하는 문제. 보수와 시간을 각각 다른 리스트 p, t에 저장하였다. 그 후 n+1의 길이만큼 dp를 만든 후 n부터 0까지 점화식을 사용하여 풀었다. 점화식은 index + t[index]가 n보다 클 시 dp[index + 1], 아닐 시 max(dp[index + 1], p[index] + dp[index + t[index])이다.

BOJ 9461

1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ... 와 같은 형태인 파도반 수열을 테스트케이스만큼 n번째 파도반 수열의 값을 출력하는 문제. [1, 1, 1, 2, 2]의 list를 저장한 후 n의 최대값인 100만큼 점화식 l(i-5) + l(i-1)을 이용하여 list를 확장한 후 입력되는 n마다 해당 값을 출력하여 풀었다.

BOJ 11727

2xn 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제. 점화식 dp[i-1] + (dp[i-2]*2)를 사용하여 풀었다.

BOJ 2156

n개의 수들이 입력되고 연속으로 3개의 수를 합칠 수 없는 조건이 있을 때, 수들을 합친 최대의 수를 출력하는 문제. 합한 값을 저장하는 dp, 입력되는 수를 저장하는 l을 이용하여 아래 점화식을 도출해 풀었다.

max(l[i] + l[i-1] + dp[i-3], l[i] + dp[i-2], dp[i-1])

BOJ 1978

n개의 수를 입력받은 후, 소수가 몇개인지 출력하는 문제. 에라토스테네스의 체를 이용하여 입력된 수 중 가장 큰 수까지 소수 리스트를 만든 후 입력된 수들을 기준으로 반복을 수행해 수를 세는 방식으로 풀었다.

BOJ 2581

n 이상 m 이하의 수 중에 소수의 합과 제일 작은 소수를 출력하며 소수가 없을 시 -1을 출력하는 문제. 에라토스테네스의 체를 이용하여 m 이하의 소수 리스트를 만든 후 n부터 m까지를 기준으로 반복문을 돌아 연산하여 풀었다.

BOJ 4963

x, y 크기의 0과 1로 이루어진 그래프를 입력 받는다. 1은 상하좌우와 대각선으로 근접해있을 시 같은 '섬'이라 판단할 때 섬의 수를 출력하는 문제. y, x 크기의 2차원배열을 만들어 방문 확인을 하며 2중 반복문을 수행하며 그래프의 값이 1이며 방문한 적이 없을 때 dfs 연산을 이용해 방문 확인을 한 후 섬의 수를 저장하는 변수의 값을 추가해 풀었다.

BOJ 1929

정수 n, m을 입력받은 후 n 이상, m 이하의 수들 중에 소수인 것을 출력하는 문제. m까지 소수인 수를 True로 저장하는 리스트를 에라토스테네스의 체 방법을 사용하여 저장 후 n부터 m까지 반복을 수행하여 풀었다.

BOJ 7568

n명의 몸무게, 키를 입력받은 후 덩치의 등수를 출력하는 문제. A는 몸무게가 B보다 크고, B는 키가 A보다 크거나 반대의 경우에는 등수가 똑같은 조건이 있다. 모든 사람에 대하여 비교를하여 몸무게와 키 둘 다 큰 경우에 1부터 1씩 더 하여 저장한 값을 출력하여 풀었다.

BOJ 11052

n장의 카드를 사야할 때, 1장부터 n장까지 카드가 들어있는 카드팩의 가격이 주어진다. 이 때 n장의 카드를 사는 최대한 비싼 가격을 출력하는 문제. 첫 풀이는 1부터 10까지 반복을 수행하여 가격이 저장된 리스트 l을 이용해 ((n // i) * l[i]) + l[n % i]을 이용하여 제일 큰 값을 출력했지만 풀이에 작성된 반례로 인해 틀리게 되었다. 이후 다이내믹 프로그래밍을 이용하여 2부터 n까지 반복을 수행하며 1부터 i를 2로 나눈 값까지 반복을 수행하며 max(l[i], dp[i], dp[j] + dp[i-j])의 점화식을 사용하여 모든 장 수의 최대 값을 이용하여 풀었다.

BOJ 1934

테스트케이스만큼 두 수를 입력받은 후 두 수의 최소공배수를 출력하는 문제. a, b = b, a % b인 유클리드 호제법을 이용해 최대공약수를 구한 후 x * y를 위 방법을 통해 구한 최대공약수로 나눈 값을 출력하여 풀었다.

BOJ 11403

방향 없는 그래프가 i번째 줄에 입력된 0과 1로 구분지어 갈 수 있는 정점을 판달할 때 각 정점별로 갈 수 있는 정점은 1, 없는 정점은 0으로 구분지어 출력하는 문제. dfs 연산을 통해 방문확인 리스트를 반환하는 함수를 이용하여 풀었다.

BOJ 14888

n개의 수열과 n-1개로 이루어진 사칙연산자의 수를 입력받는다. 입력받은 사칙연산자를 이용하여 모든 경우의 수로 계산을 하였을 때 최대값과 최소값을 출력하는 문제. 사칙연산자로 이루어진 리스트를 만든 후 해당 사칙연산자를 이용해 eval 함수를 이용하여 계산, 방문 확인 리스트를 사용하여 백트래킹하였지만 시간초과 결과를 받게 되었다. 두번째 풀이는 각 연산자들의 수를 기준으로 백트래킹시 재귀적으로 호출하는 함수의 매개변수의 값을 빼주어 해당 연산을 해주는 식으로 풀었다.

BOJ 2468

1 ~ 100 크기의 정수로 이루어진 n x n 크기의 2차원 배열을 입력받는다. 강수량이 n일 때 n 이하의 지역이 침수된다. 침수되지 않은 상하좌우 기준으로 붙어있는 지역을 한 개의 안전지역이라고 한다. 이 때 임의의 강수량으로 만들어진 안전지역 중 최대 수를 출력하는 문제. 높이의 최대치인 100까지 반복을 수행하며 방문확인 리스트와 높이를 비교하여 dfs 연산을 통해 방문확인하며 안전지역의 수를 세도록 작성하였으며 모든 지역이 잠길 때 반복문을 끝내도록 풀었다.

BOJ 6603

n개의 수열을 입력받은 후 그 중 6개를 고를 때 순서가 상관없는 모든 경우의 수를 출력하는 문제. 백트래킹 방법을 이용하여 풀었으며, 방문확인을 해제할 때 자신보다 큰 수들의 방문 확인을 해제하여 풀었다.

BOJ 4948

베르트랑 공준이란 임의의 자연수 n은 n보다 크며 2n과 같거나 작은 수중에 적어도 하나의 소수가 존재한다는 내용이다. 0이 입력되기 까지 정수를 입력받은 후 각 수들보다 크며 2n보다 같으며 작은 소수들의 수를 출력하는 문제. 입력받은 수들을 리스트에 저장하며 제일 큰 수를 저장한다. 그 후 에라토스테네스의 체 방법을 이용하여 제일 큰 수 * 2한 값까지의 소수를 확인 후 리스트에 든 값을 이용하여 슬라이싱 후 count하여 풀었다.

CF 4A

코드포스에서 푼 첫 문제. 정수가 주어진 후 짝수로 나눌 수 있는 지 여부를 출력하는 문제. 문제가 영어인 탓에 입력과 출력을 보고 문제를 유출해 내는 방식으로 푸는 것 같다.

CF 71A

문자열을 입력받은 후 길이가 10 이상일 시 첫 글자와 마지막 글자 사이에 길이를 출력하는 문제. len을 이용하여 간단히 풀었다.

BOJ 11404

n개의 정점과 m개의 간선이 있으며 간선은 가중치를 갖고 있다. 모든 정점에서 다른 정점으로 갈 때 최소 비용을 출력하는 문제. 모든 정점을 기준으로 3중 반복문을 수행하여 비교하는 플로이드 와샬 방법을 이용하여 풀었다. i부터 j까지 가는 비용과 i에서 k, k에서 j까지 가는 비용을 더한 것을 비교하는 방식으로 풀었다. 다익스트라와 플로이드 와샬은 시작점으로부터 다른 정점의 거리를 비교할 때 다익스트라, 모든 정점의 거리를 비교할 때는 플로이드 와샬을 사용한다고 한다.

BOJ 2458

n개의 정점이 있으며 m개의 방향이 있는 간선이 있다. 이 때 모든 정점들과 연결된 정점의 수를 출력하는 문제. 첫번째 풀이는 결과를 저장하는 리스트와 간선을 저장하는 리스트를 이용하여 플로이드 와샬 방법을 이용하여 간선 i,k 와 k,j의 값이 True일 때 결과를 저장하는 리스트를 쌍방향으로 True로 값을 바꿔준 후 리스트의 모든 값이 True인 리스트를 count하여 풀었으나 시간초과 결과와 틀렸습니다 결과를 받게 되었다. 두번째 풀이는 리스트 한개를 이용했으며 플로이드 와샬 방법을 이용하여 ik, kj를 비교 후 ij의 값만 True로 수정해 주었다. 그 후 True인 간선은 i와 j의 값을 추가하여 값을 n과 비교하여 count하여 풀었다.

BOJ 1475

6과 9를 같이 쓸 수 있을 때 방번호를 꾸밀 때 필요한 0부터 9까지 들은 세트의 수를 출력하는 문제. 입력되는 수를 기준으로 반복하여 개수를 저장할 때, 9와 6을 동시에 저장하며 반복이 끝난 후 2로 나눈 값을 올림하여 저장한다. 그 후 리스트에 저장된 값 중 제일 큰 값을 출력하여 풀었다.

BOJ 10773

n개의 수를 입력받는다. n이 0일 때 제일 최근에 입력받은 수를 지운다고 할 때 입력되는 수들의 총합을 구하는 문제. 리스트의 append와 pop을 이용하여 스택 자료구조의 모습을 간단히 구현하여 풀었다.

BOJ 1786

문자열 t 안에 문자열 p가 몇개 들어있는 지, 시작하는 인덱스는 어디인 지 출력하는 문제. 단순히 모든 문자열을 비교할 시 O(len(t)*len(p))가 되어 길이가 길어질 시 기하급수적으로 커지게 된다. 이를 해소하고자 KMP 방식을 공부 및 적용하여 풀었는데, p에 대한 LPS(최장길이 접미사 and 접두사)를 저장하여 문자열 비교간에 LPS를 이용하여 p에 대한 인덱스 값을 수정하여 비교를 줄이는 방식이며 시간복잡도는 O(len(t)+len(p))이다. 자세한 설명은 주석을 참고.

BOJ 1305

길이가 n인 전광판에 광고 문구가 반복되어 나타나 있다고 한다. 이 때 광고 문구의 최소 길이를 출력하는 문제. KMP 알고리즘을 공부하며 배웠던 LPS를 이용하였다. 주어진 문자열을 이용하여 LPS 배열을 만든 후 n - lps[n-1]을 계산하여 출력하여 풀었다.

BOJ 7575

수열의 수 n과 확인할 수열의 길이 k를 입력받은 후, 각 수열의 길이, 수열을 입력받는다. k 길이만큼의 반복되는 부분 수열과 해당 부분 수열을 거꾸로한 것이 모든 수열에 존재 시 YES를, 아닐 시 NO를 출력하는 문제. 제일 짧은 수열을 기준으로 k 길이만큼 슬라이싱 후 KMP 알고리즘을 통해 수열에 확인하는 지 확인하여 풀었다. 자세한 설명은 주석을 참고.

BOJ 1701

문자열 s가 주어진 후 2번 이상 들어가는 부분문자열의 최대 길이를 출력하는 문제. 첫번째 풀이는 처음부터 s의 길이 -1부터 2까지 문자열을 슬라이싱하여 LPS를 계산 후 KMP 알고리즘을 이용하여 2번 이상 존재할 시 return 및 break를 이용하여 해당 결과를 출력하여 풀었다. 시간제한이 0.5초이며 처음부터 시작하기 때문에 시간초과 및 틀렸습니다 결과를 받았다. 문제의 2번 이상 존재하는 경우를 통해 LPS만을 이용하여 계산하면 될 것 같아 0부터 s의 길이만큼 index를 이동하여 슬라이싱한 값을 이용하여 LPS 중 최대값을 저장 및 갱신하여 풀었다.

BOJ 4354

문자열 s가 주어진 후 어떤 문자열 a에 대하여 s = a^n으로 나타낼 때 가장 큰 n을 출력하는 문제. LPS를 이용하여 풀었으며 예제를 보는 중 식을 도출해 내어 풀게 되었다. s의 길이를 ls라 할 때 ls // ls - lps[-1]을 계산하여 풀었다. 하지만 lps의 마지막 값이 높으나 나누어 떨어지지 않는 예외가 있어 나누어 떨어지지 않을 때는 1을 출력하는 조건을 추가하여 풀었다.

BOJ 16916

문자열 s와 p를 입력받은 후 s안에 p가 있을 시 1을, 없을 시 0을 출력하는 문제. KMP 알고리즘을 이용하여 풀었으며 한 번 찾은 후 연산을 종료하도록 하였다.

BOJ 11057

오르막 수는 수의 자리가 오름차순을 이루는 수를 말하며 인접한 수가 같아도 오름차순으로 친다. 이 때 수의 길이 n이 주어질 때 오르막 수의 개수를 구하는 문제. [n+1][10]의 크기로 이루어진 배열을 만든 후 [1]의 값을 모두 1로 초기화한다. 그 후 up은 j보다 같으며 큰 수로 반복을 하게 작성 후 dp[i][j] += dp[i-1][up]의 점화식을 사용하여 풀었다.

BOJ 2293

n가지 종류의 동전으로 k원을 나타내는 경우의 수를 구하는 문제. [k+1]의 리스트를 만든 후 딱 떨어지는 경우를 위해 [0]을 1로 초기화한다. 그 후 1원부터 k원까지 반복을 수행하며 입력받은 cost - coin이 0보다 크거나 같을 때 dp[cost] += dp[cost-coin]을 하여 경우의 수를 계속 더하도록 풀었다.

BOJ 5639

노드의 데이터보다 작은 노드를 왼쪽에, 큰 노드를 오른쪽에 배치한 이진 검색 트리를 전위 순회한 결과룰 입력받은 후, 후위 순회한 결과를 출력하는 문제. 입력의 끝이 정해져 있지 않음으로 stdin.readlines를 이용하여 입력을 받았으며 클래스를 이용하여 노드, 이전검색트리를 만들어 이진 검색트리에 위치시킨 후 후위순회를 하여 결과를 출력하여 풀었으나 시간초과 결과를 받게 되었다. 그 후 해당 게시물을 참고하여 리스트의 인덱스를 이용하여 후위순회하는 방법을 참고하여 풀었다.

BOJ 2263

트리의 정점의 수와 중위 순회, 후위 순휘를 입력받은 후 해당 트리를 전위 순회하여 출력한 결과를 출력하는 문제. 후위 순회의 마지막을 기준으로 해당 노드를 출력 후, 중위 순회한 결과에서 해당 노드의 위치를 기준으로 왼쪽에 있는 노드를 후위 순회한 것 뒤에 위치한 후 해당 연산을 반복하면 전위 순회한 결과과 되는 것을 깨달은 후 새로운 리스트를 만들어서 재귀적으로 호출하여 풀었으나 메모리 초과 결과를 받게 되었다. 새로운 리스트를 계속해서 만들었기 때문이다. 두번째 풀이는 중위 순회, 후위 순회 각각 시작점과 끝점을 함수의 매개변수로 사용하여 재귀적으로 호출하였다. 후위 순회의 끝점을 출력한 후 후위 시작점 + 해당 노드의 중위 순회 결과의 위치 - 중위 순회 시작점을 계산 및 이용하여 해당 노드의 후위 순회 결과의 좌측, 우측을 나누는데 사용하였다.

BOJ 1068

n개의 노드로 이루어진 트리를 각 노드의 부모들의 번호를 입력받으며 주어진다. 그 후 지울 노드 번호를 입력받으며 해당 트리의 리프 노드의 수를 출력하는 문제. 첫 풀이는 지워지지 않은 노드들을 저장하는 배열을 이용하여 확인하여 수를 세는 방식으로 하였으나, 지운 노드를 유일한 자식으로 가지고 있는 노드의 반례를 풀지 못했으며 dfs 연산을 두 번하는 과정이 필요없을 것 같아 다시 풀게 되었다. 두번째 풀이는 dfs을 하며 노드의 자식이 없을 때 리프 노드라고 판단, 자식 노드를 큐에 추가할 때 삭제할 노드가 있으며 해당 노드의 길이가 1일 때도 리프 노드로 판단하는 부분을 넣어 풀었다. 수차례 괴롭히던 런타임 에러는 그래프를 먼저 생성하는 방식으로 해결하였다.

BOJ 2583

y, x의 크기를 갖는 배열에 k개의 직사각형이 위치한다. 도형의 위치는 왼쪽 아래 좌표, 오른쪽 위 좌표를 입력받으며 도형이 위치하지 않는 구역의 수와 구역의 크기를 출력하는 문제. 동일한 크기의 boolean 배열을 이용하여 확인을 하여 dfs 연산을 이용하여 풀었다.

BOJ 1904

00과 1의 모양을 한 타일이 있다. 이 때 자릿수 n이 주어질 때 나타낼 수 있는 모습의 가짓수를 15746으로 나눈 나머지를 출력하는 문제. dp[i] = dp[i-1] + dp[i-2]의 점화식을 도출하여 풀었다. 결과값에 나머지 연산을 한 값을 출력하는 방식으로 풀 시 메모리초과 결과를 받기 때문에 매 연산마다 나머지 연산을 하여 풀었다.

BOJ 11055

가장 큰 부분 수열 문제. 수열이 주어졌을 때 오름차 부분 수열의 최대합을 출력하는 문제. 첫 풀이는 탑다운 형식으로 최대 값을 저장하는 형식으로 풀었으나 2개 이상 띄워져 있는 부분 수열에는 적용하지 않는 문제가 있어 이중 반복문을 이용하여 풀었다. 0부터 i까지 반복문을 수행하며 수열의 i보다 j가 작을 때 dp[i]에 dp[i], dp[j] + l[i]의 값 중 큰 것을 할당하여 풀었다.

BOJ 11722

n의 크기를 갖는 수열을 입력받은 후 해당 수열에서 가장 긴 감소하는 부분 수열의 길이를 출력하는 문제. 0부터 n까지 반복을 수행하며 0부터 i까지 반복한다. i의 값보다 j의 값이 클 때 dp[i] = max(dp[i], dp[j]+1)의 점화식을 사용하여 풀었다.

BOJ 7562

체스 보드의 크기를 입력받은 후 나이트 말의 시작 좌표와 도착 좌표를 입력받는다. 최소 몇 번 말을 움직여야 도착 좌표까지 이동할 수 있는 지 출력하는 문제. 첫 풀이는 queue에 카운트를 넣으며, 2차원 배열은 방문 확인을 위해 사용하여 풀으며 두번째 풀이는 2차원 배열에 움직인 횟수를 저장하여 풀었다. 여러 방법으로 계속해서 풀었으나 틀렸습니다 결과를 받게되었는데 말이 갈 수 있는 방향을 저장해 놓은 배열이 잘못돼 있었다.

BOJ 12015

�n의 길이를 갖는 수열을 입력받은 후, 해당 수열의 증가하는 부분 수열의 최대 길이를 출력하는 문제. 첫번째 풀이는 O(n^2)의 시간복잡도를 갖는 dp를 이용하여 풀었다. 하지만 시간초과 결과를 받게 되었는데 해당 문제는 n이 최대 백만인 경우까지 있기 때문이다. 두번째 풀이는 O(nlogn)의 시간복잡도를 갖는 이분탐색을 이용하여 풀었다. n까지 반복을 수행하며 n의 크기를 갖는 vt 배열의 마지막 값과 비교하여 클 때 길이를 늘린 후 추가, 작을 시 현재 크기만큼 탐색을 통해 같은 값이 있을 때는 연산을 안하며 큰 값이 나왔을 때 해당 인덱스의 값을 바꿔준다. 탐색이 끝난 후까지 함수가 종료 안됐을 시 첫번째 값과 비교하여 값을 할당하여 풀었다. / 시간초과로 재채점되어 내장 라이브러리 bisect, sys.stdin.readline을 이용하여 다시 풀었다.

BOJ 2644

여러 사람들의 부모 자식 관계가 주어질 때, ans_x와 ans_y의 관계가 몇 촌인지 출력하는 문제. ans_x부터 dfs 연산을 이용하여 queue에 촌 수를 저장하여 풀었다.

BOJ 1699

정수 n이 주어질 때, 이 수를 제곱수의 합으로 나타낼 때, 제일 작은 제곱수의 수를 출력하는 문제. 다이내믹 프로그래밍 문제로 1부터 n까지 반복, 1부터 j*j가 i보다 작을 때 까지 반복한다. dp[i], dp[i-(j*j)]+1 중 작은 것을 배열데 대입하도록 점화식을 구성하여 풀었다.

BOJ 2217

n개의 밧줄이 견딜 수 있는 무게가 주어진다. 밧줄은 여러줄 사용하여 무게 w를 밧줄의 수 k만큼 w/k의 중량으로 나누어 들 수 있을 때, 밧줄을 이용하여 들 수 있는 최대 무게를 구하는 문제. 입력되는 모든 밧줄을 오름차순으로 정렬 후 해당 밧줄의 무게 * (n-i)를 계산하여 최대값을 출력하여 풀었다.

BOJ 11585

환형 문자열에서 특정 문자열을 찾아 나올 수 있는 확률을 기약 분수 형태로 출력하는 문제. 두 문자열을 입력받은 후 한 문자열을 2배로 한 후, 마지막 문자를 제거한 문자열에서 다른 문자열을 KMP 알고리즘을 이용하여 찾도록 풀었다. 마지막 문자를 제거하는 이유는 입력되는 문자열이 동일 시 추가적으로 한 개가 더 늘기 때문이다. 기약분수화는 fractions의 Fraction을 이용하였으며 모든 경우에서 찾을 수 있을 때 1로 나오는 것을 예외처리하여 풀었다.

BOJ 10266

360000의 크기를 갖는 시계에 n개의 시계바늘이 있다. 동일한 시계 바늘을 갖고 있는 시계의 시계 바늘 각도가 주어질 때, 시계를 돌렸을 때 같은 시각을 나타낼 수 있는 지 여부를 출력하는 문제. 360000의 길이를 0으로 이루어진 배열 두개를 만든 후 각 시계마다 입력되는 각도를 1로 변경하였다. 한 시계의 배열을 2배로 한 것에 KMP 알고리즘을 이용하여 다른 시계 배열을 찾았으며 찾을 시와 못찾았을 시를 나누어 출력하여 풀었다.

BOJ 1259

입력되는 수들이 팰린드롬 형식인지 여부를 출력하는 문제. 문자열의 길이를 이용하여 반복문을 수행하여 풀었다.

BOJ 1261

(0, 0)부터 (y, x) 좌표까지 이동할 때 막힌 곳을 부신 후 지나갈 수 있다고 한다. 이 때 최소한의 개수로 부수며 갈 수 있는 경우의 부순 수를 출력하는 문제. 다익스트라 알고리즘을 사용하여 풀었으며, 이에 필요한 힙 자료구조, 방문확인 배열을 이용하여 풀었다.

BOJ 1238

n명의 사람, 단방향으로 출발지, 도착지, 가중치를 갖는 m개의 노선, 최종 도착지 x가 주어진다. 이 때 모든 사람들이 x에 도착하여 다시 도시 n으로 가는 최단시간 중 최대 값을 출력하는 문제. 다익스트라 알고리즘을 이용하여 접근했으며 첫 풀이는 n에서 x까지, x에서 n까지 이동하는 최소비용들을 더하여 풀었으나 메모리초과 결과를 받게 되었다. 두번째 풀이는 x부터 다른 도시들까지 이동하는 모든 최단 길이를 저장 후 노선을 반대로 저장한 것을 이용해 다른 도시들부터 x까지 가는 모든 최단 길이 두개를 더해 더한 값 중 최대 값을 출력하여 풀었다.

BOJ 17219

n개의 공백으로 나누어진 문자열을 입력받은 후 m개의 문자열로 앞서 입력받은 문자열에서 찾아 뒤의 문자열을 출력하는 문제. 딕셔너리 자료형을 이용하여 저장, 출력하여 풀었다.

BOJ 9019

0000부터 9999까지의 범위에 두 수를 입력받는다. 자릿수를 왼쪽으로 이동시키는 연산은 L, 오른쪽으로 이동시키는 연산은 R, 두배로 만드는 것을 D, 1을 빼는 연산을 S라고 한다. 왼쪽에 있는 수를 오른쪽에 있는 수의 모습으로 바꾸는 최소 경우에 연산 과정을 출력하는 문제. BFS 연산을 이용하여 풀었으며 각 연산을 함수로 만들어 사용했다. 정답과 비교는 문자열로 하였으며 방문확인은 최대수까지의 배열을 만들어 비교했다. 리스트형의 인덱스를 이용해 L, R 연산을 했을 시 시간초과 결과를 얻게되어 연산하여 사용했다.

BOJ 11004

입력되는 수열을 올림차순으로 정렬하여 k번째 수를 출력하는 문제. sorted 메소를 이용하여 정렬 후 인덱스를 출력하여 풀었다.

BOJ 1874

스택에 수를 push 할 때 1부터 오름차순으로 할 때 주어지는 수열을 push와 pop을 이용하여 만들 수 있는 지 여부와 있을 때 연산의 과정을 출력하는 문제. 수열에 입력되는 수와 스택의 마지막 값과 비교하여 마지막 값보다 클 시 스택에 들어왔던 제일 큰 수부터 입력된 수까지 연산을, 마지막 값보다 작을 시는 마지막 값과 같은 지를 확인하여 만들 수 있는 여부를 확인하여 풀었다.

BOJ 2960

에라토스테네스의 체 방식으로 k번째로 소수가 아닌 것을 확인한 수를 출력하는 문제. 확인한 수를 저장하는 변수를 사용하여 풀었다.

BOJ 9020

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 문제. 입력되는 수들 중 제일 큰 수를 기준으로 에라토스테네스 방식을 이용하여 소수인 수가 True로 저장돼 있는 리스트를 이용하여 n//2+1까지 n-i, i 둘 다 소수일 때를 저장하여 풀었다.

BOJ 6588

위 문제와 동일한 골드바흐 파티션을 출력하는 문제. 다른 점은 n2 - n1이 제일 큰 조합을 출력하는 것과 골드바흐 파티션이 존재하지 않는 예외를 처리하는 것이다. 골드바흐 파티션을 찾는 즉시 반환하는 함수를 만들어 사용하였으며 반복문이 끝날 시 존재하지 않을 때 출력할 문장을 반환하여 풀었다.

BOJ 1182

n개의 정수로 이루어진 수열의 부분수열 중 합이 s인 경우의 수를 출력하는 문제. 백트래킹 방식을 이용하여 풀었으며 i+1부터 n까지 방문확인을 해제하여 순서가 다르지만 값은 같은 경우를 방지하였으며 방문한 리스트가 비어있지 않으며 합한 값이 s와 같을 때 CBR를 이용하여 값을 추가하여 풀었다.

BOJ 10819

n개의 정수로 이루어진 수열이 입력된다. 이 때 수열의 자리를 바꾸어 |l[0] - l[1]| + |l[1] - l[2]| + ... 의 식을 계산했을 시 나올 수 있는 최댓값을 출력하는 문제. 백트래킹 방법을 이용하여 모든 경우의 수를 배열에 저장 후, 배열의 길이가 n과 같아질 시 계산 후 값을 저장, 백트래킹이 끝난 후에 max값을 출력하여 풀었다.

BOJ 11048

y, x 크기의 정수로 이루어진 이차원 배열이 주어진다. (0, 0)에서 (y, x)까지 대각선 아래, 오른쪽, 아래쪽 방향으로 이동할 수 있을 때 (y, x)까지 모든 정수를 더한 최대 값을 출력하는 문제. 첫번째 풀이는 bfs 연산을 이용하여 풀었으나 시간초과 결과를 받게 되었다. 두번째 풀이는 dp로 풀었으며, y+1, x+1 크기의 배열을 만들어 graph[i-1][j-1] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])의 점화식을 이용하여 풀었다.

BOJ 1541

정수, '+', '-'로만 이루어진 수식을 입력받은 후, 해당 수식에 괄호를 사용하여 연산한 값이 최소가 되도록 출력하는 문제. '-'로 split한 값들을 eval하여 다른 배열에 append한 후, 해당 배열을 '-'.join하여 eval한 값을 출력하여 풀었다. 주어지는 정수가 '05' 같은 경우가 있어 map을 이용하여 int로 바꾼 후 다시 str형으로 바꿔 join하도록 풀었다.

BOJ 1389

n명과 m개의 관계를 입력받은 후. 모든 사람을 기준으로 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산한 총합을 계산하여 그 값, 케빈 베이컨의 수가 가장 적은 사람을 출력하는 문제. n+1, n+1의 크기의 이차원 배열을 INF 값으로 만든 후 입력되는 관계를 쌍방향으로 1로 저장, 플로이드 와샬 방법을 사용하여 graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])의 점화식을 사용하여 풀었다.

BOJ 1018

y만큼 x 크기의 "W", "B"로 이루어진 문자열들을 입력받는다. 그 후 해당 문자열들을 8, 8 크기로 체스판처럼 만들 때 수정해야할 칸의 최솟값을 출력하는 문제. 0부터 y-7, x-7까지 반복문을 수행하며 시작점과 끝점을 함수의 매개변수로 사용하였다. 함수는 시작점부터 끝점까지 반복문을 수행하며 (i + j) % 2의 수식을 이용하여 임의의 "W", "B"를 판단하였으며 두가지 경우에 대하여 문자열이 다를 시 정수형 변수를 증가하여 해당 값을 계산하여 풀었다.

BOJ 2042

n개의 수가 주어진 후 수열의 값을 변경, 해당 수열의 구간 합을 출력하는 문제. 세그먼트 트리 방식을 이용하여 풀었으며 입력되는 수들을 배열에 저장, 새로운 배열을 세그먼트 트리화하였다. init, sum, change 함수 모두 재귀적으로 호출하여 사용하였으며 중간 값 나누기 연산을 변수에 할당하여 작지만 연산을 줄여 풀었다. 자세한 풀이는 문제의 주석을 참고

BOJ 11505

n개의 수가 주어진 후 수열의 값을 변경, 해당 수열의 구간 곱을 출력하는 문제. 위 문제와 동일한 세그먼트 트리 방식을 이용하여 풀었으며 곱한 값을 저장해야하는 만큼 재귀적으로 호출하여 값을 저장할 때 곱하기 연산을 사용하였으며 트리에 저장시에도 정해진 나누기 연산을 미리 수행하여 오버플로우 발생 및 연산을 빠르게 하였다. 또한 값을 변경 시에 리프노드일 시 tree의 값을 바꿔야하는 값으로 바꿔 주었으며 재귀 호출 후에 왼쪽, 오른쪽 자식 노드의 값을 곱한 값을 할당하여 풀었다.

BOJ 2357

n개의 수가 주어진 후 정수 s, e가 주어진다. 입력된 수들의 인덱스 s부터 e까지 최소, 최대 값을 출력하는 문제. 첫 번째 접근은 리스트 슬라이싱을 이용하여 풀었으나 당연하게도 시간초과 결과를 받게 되었다. 두 번째 접근은 최소, 최대값을 저장하는 두개의 세그먼트 트리를 이용했다. 반환되는 값에 min과 max 함수를 사용하여 풀었다.

BOJ 10868

n개의 수가 주어진 후 정수 s, e가 주어진다. 입력된 수들의 인덱스 s부터 e까지 최솟값을 출력하는 문제. 위 문제와 같은 세그먼트 트리 방식을 이용하여 풀었으며 재귀적으로 반환 하는 값의 연산을 min 함수를 이용하여 풀었다.

BOJ 6549

직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형을 히스토그램이라 칭한다. 히스토그램의 길이, 각 직사각형들의 높이를 입력받은 후 해당 히스토그램에서 가장 큰 직사각형의 넓이를 출력하는 문제. 스택을 활용하여 풀었으며 입력되는 것을 1번 인덱스부터 끝까지 자른 배열을 함수에 전달한 후 첫 연산과 마지막 사각형을 확인하기 위해 맨 앞, 뒤에 0을 추가하였다. 그 후 확인했던 사각형의 인덱스가 들어갈 배열, 정답을 위한 변수를 생성하였다. 1부터 마지막 사각형을 위해 n+1까지 반복문을 수행하였으며 현재 확인 중인 사각형보다 이전 사각형의 높이가 클 시, 확인한 사각형의 인덱스의 마지막 값을 pop하였다. 해당 값 x 현재 시점 사이에 사각형의 수와 정답을 위한 변수 중 큰 것을 재저장하여 반복문이 끝날 시 반환하여 풀었다. 자세한 풀이는 주석을 참고

BOJ 1725

히스토그램의 각 직사각형의 높이를 입력받은 후 가장 큰 직사각형의 넓이를 출력하는 문제. 위 문제와 TC 존재 여부만 다르다. 그렇기 때문에 동일한 스택을 사용하는 방법을 이용하여 풀었다. 자세한 풀이는 위 문제의 주석을 참고

BOJ 11060

n개의 정수로 이루어진 수열을 입력받는다. i번째 인덱스의 값을 A라고 했을 때 i ~ i+A까지 이동할 수 있다고 한다. 인덱스 0부터 시작해서 n까지 가는 최소 이동횟수를 출력하며 인덱스 n까지 갈 수 없을 때는 -1을 출력하는 문제. n+1의 수로 만들어진 새로운 배열을 생성하며 0부터 i까지 반복을 수행한다. 그 안에 i부터 i + l[i]까지 반복을 하며 dp[j]에 저장된 값과 현재 dp[i] + 1 값과 비교하여 작은 수를 저장한다. 반복문이 종료될 시 마지막에 저장된 값이 n + 1 (절대 나올 수 없는 수이기 때문에)일 시 -1을, 아닐 시 마지막에 저장된 값을 출력하여 풀었다.

BOJ 2133

3xN의 크기를 갖는 배열에 2x1, 1x2 크기의 타일로 채우는 경우의 수를 출력하는 문제. 해당 문제는 홀수 일 때는 경우의 수가 0이 되며 짝수만 경우의 수를 갖는다. 2와 4의 경우의 수를 판단 시 각 3, 11이 되게 되는데 이를 통해 dp[n] = dp[n-2] + 2의 경우의 수를 갖는 다는 것을 알게 되었다. 더 큰 짝수들은 더해지는 값들이 2와 더불어 -4의 경우의 수와 x2를 해준 값을 더해야 함으로 dp[0]의 값을 1로 설정 후 반복문을 0부터 i-4의 값까지 x2하여 더해주어 풀었다.

BOJ 5676

수열을 입력받은 후 해당 인덱스의 값을 변경, 구간곱을 계산하여 해당 구간곱의 값이 양수, 음수, 0인 경우에 따라 +, -, 0을 출력하는 두가지 입력이 존재하는 문제. 모든 풀이는 세그먼트 트리를 이용하여 풀었다. 첫 풀이는 입력 및 저장되는 값을 그대로 계산하여 출력을 요구할 때 0과 비교하여 풀었으나 오버플로우로 유발됐다고 예상되는 시간초과 결과를 얻게 되었다. 두번째 풀이는 입력되는 수를 0과 비교하여 1, 0, -1로 반환하는 함수를 이용하여 풀었다.

BOJ 9625

문자열에서 버튼을 누를 시 A는 B로, B는 AB로 만든다고 한다. A의 문자열에서 버튼을 N번 눌렀을 때 A, B의 수를 출력하는 문제. 점화식 dp[i] = [dp[i-1][1], dp[i-1][0] + dp[i-1][1]]을 이용하여 풀었다.

BOJ 9655

n개의 돌이 있을 때 1개 혹은 3개를 가져가, 맨 마지막에 돌을 가져가는 사람이 이기는 게임이 있다. 상근이와 찬영이가 상근이부터 시작하여 게임을 진행할 시 n개의 돌일 때 누가 승리하는 지 출력하는 문제. 각 숫자들이 주어졌을 때 승자를 써보니 짝수와 홀수일 때 승자가 정해져있어 간단하게 풀었다.

BOJ 14916

n원을 5원, 2원으로 나누어줄 때 동전의 수를 최소로 돌려줬을 때, 동전의 수를 출력하는 문제. 그리디 방식을 이용하여 n을 5로 나눈 값부터 0까지 반복문을 수행하며 해당 값의 나머지가 2로 나누어질 때 동전의 수를 출력한 후 프로그램을 종료, 반복문 후에도 종료가 안됐을 시 -1을 출력하여 풀었다.

BOJ 19947

h원과 투자기간 y가 주어진 후, 5% 1년, 20% 3년, 35% 5년의 이윤과 기간이 있는 투자 상품이 있다. 매번 이율은 소수점 이하를 버림해서 받으며 투자 방식은 매년 바꿀 수 있을 때, 가장 많은 이득을 얻었을 때의 총 자산을 소수점을 모두 버리고 정수로 출력하는 문제. 첫 풀이는 함수를 재귀적으로 사용하여 전역 변수와 값을 비교하여 풀었다. 두번째 풀이는 전역변수 사용이 아닌 재귀함수의 반환 값을 이용하여 비교, 출력하여 풀었다.

BOJ 14495

f(n) = f(n-1) + f(n-3)의 점화식을 갖는 피보나치 비스무리한 수열의 n번째 수를 출력하는 문제. 주어진 점화식을 이용하여 간단히 풀었다.

BOJ 17212

1, 2, 5, 7원의 동전을 이용하여 n원을 동전의 최소 개수로 만들었을 때 동전의 수를 출력하는 문제. 0 ~ 7원까지의 최소 수를 저장한 후 8부터 n원까지 반복을 수행하여 min(dp[i-7], dp[i-5], dp[i-2], dp[i-1]) + 1 점화식을 사용하여 저장 후 출력하여 풀었다.

BOJ 4485

n, n 크기의 정수로 이루어진 이차원 배열 graph를 입력받는다. 0, 0부터 n-1, n-1까지 해당 좌표의 정수를 합한 값이 최소가 되게 이동할 때, 해당 최소 값을 출력하는 문제. INF로 이루어진 같은 크기의 배열 dist를 만든 후 0, 0부터 현재 값 + graph에 저장된 다음 값을 더한 값이 dist에 저장된 값보다 작을 시 dist값 설정, 힙에 추가하도록 다익스트라 방법을 이용하여 풀었다.

BOJ 15990

정수 n을 같은 숫자가 연속해서 나오면 안된다는 규칙을 지키며 1, 2, 3의 더하기로 나타낼 때, 방법의 수를 출력하는 문제. i번째 수는 i-1번째 공식에서 1로 시작하지 않는 방법에 1을 더하며, i-2번째 공식에서 2로 시작하지 않는 방법에 2를 더하며, i-3번째 공식에서 3으로 시작하지 않는 방법에 3을 더하는 식으로 2차원 배열을 만들어 풀었다.

BOJ 15988

정수 n을 1, 2, 3의 더하기로 나타내는 방법의 수를 출력하는 문제. i번째 수는 i-1번째 공식에 각각 1을 더하면 되며 i-2번째 공식에 각각 2를, i-3번째 공식에는 3을 더하면 되기 때문에 dp[i-3:i]의 수를 더한 값을 저장 및 출력하여 풀었다.

BOJ 1106

광고의 비용과 광고로 인해 늘어나는 고객의 수가 n개 주어진다고 한다. 적어도 c명의 고객의 수를 늘리기 위해서 투자해야되는 최소한의 비용을 출력하는 문제. 첫 번째 풀이는 dp[비용]에 최대한 구할 수 있는 사람의 수를 저장한 후 최초로 c가 넘는 값을 출력하여 풀었다. 이 방법은 최대 비용 1000 * 100까지 비교를 수행해야 하므로 두 번째 풀이는 dp[고객의 수]에 최소한의 비용울 저장하여 풀었다. 가격과 고객의 수를 입력받은 후, 고객의 수부터 최대 고객의 수인 1100까지 반복을 수행하였다. 해당 인자 j를 이용하여 dp[j] = min(dp[j], dp[j-customer] + cost)의 점화식을 사용하여 풀었다.

BOJ 1715

n이 2 이상일 때 n-2, n-1을 재귀적으로 호출하며, n이 1 이하일 때 n을 반환하는 함수가 있다. n이 주어졌을 때 해당 함수가 몇 번 호출되는 지 출력하는 문제. 배열의 0, 1 인덱스에 1로 값을 초기화한 후 2부터 dp[i] = 1 + dp[i-2] + dp[i-1]의 점화식을 사용하여 풀었다.

BOJ 1633

30 ~ 1000개의 두 정수를 입력받는다. 중복되지 않으며 한 줄에 한 개의 수만 선택가능할 때, 앞 수 15개, 뒷 수 15개를 합친 최대 값을 출력하는 문제. 첫 풀이는 함수를 재귀적으로 활용하여 dp[정수의 길이][16][16]의 크기를 갖는 배열에 값을 할당, 비교하여 풀었으나 문제의 풀이가 길어져 두 번째 풀이는 3중 반복문을 이용하여 할당, 비교하여 풀었다. 다이내믹 프로그래밍 문제를 더 공부해야겠다.

BOJ 1275

n개의 정수로 이루어진 수열을 입력받은 후, 구간합을 출력한 후, 인덱스 값을 바꾸는 연산을 수행해야하는 문제. 세그먼트 트리를 이용하여 풀었다. 아직은 이해도가 부족하다 생각된다.

BOJ 8394

n명의 사람이 한 줄로 앉아있을 때, 자리를 벗어나지 않고 악수를 하는 방법의 수를 출력하는 문제. 안하는 경우를 포함해서 n-1, n-2명일 때의 경우를 더하면 n명일 때의 경우의 수를 구할 수 있다. 첫 번째 풀이는 입력받는 수 + 1까지 배열을 만들어 배열의 값을 참조하도록 풀었으며 마지막 자리의 수만 출력하면 되므로 10으로 나눈 나머지 값들을 저장하였다. 두 번째 풀이는 변수 i와 j를 이용하여 i, j = j, (i + j) % 10의 점화식을 사용하여 풀었다.

BOJ 2670

n개의 실수를 입력받아 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분의 곱을 출력하는 문제. 첫 번째 풀이는 브루트포스 방식으로 2중 반복문을 이용하여 모든 값을 곱하여 비교하였지만 시간초과 결과를 받게 되었다. 두 번째 풀이는 리스트의 인덱스에 인덱스 -1 값과 비교하여 더욱 큰 값을 저장하는 다이내믹 프로그래밍 방식을 이용하여 풀었다.

BOJ 1535

n개의 값과 무게를 입력받은 후 가방의 크기가 99일 때 최대 값을 출력하는 문제. 이중 반복문을 이용하여 담을 수 없을 때 같은 무게, 저번 물건의 값을 할당, 담을 수 있을 때 같은 무게, 저번 물건의 값과 현재 물건의 값 + 반복중인 무게 - 현재 물건의 무게의 저번 물건의 값 중 큰 것을 할당하여 배열의 마지막 값을 출력하여 풀었다. n이 1이며 해당 무게가 99를 넘는 경우를 예외처리하지 못하여 여러번 틀린 문제.

BOJ 14728

n개의 물건, 배낭의 크기 t를 입력받은 후 n개의 무게와 값이 주어지는 냅색 문제. 위 문제와 동일한 방식으로 풀었다.

BOJ 7579

n개의 물건, 배낭의 크기 m를 입력받은 후 n개의 무게와 값이 주어지는 기존 냅색 문제와 동일하지만, 기족 m 이하의 최대값을 출력하는 것이 아닌, m 이상이 되는 최소한의 값을 출력하는 문제. m은 최대 10,000,000의 크기를 갖기 때문에 모두 탐색을 하는 것은 불가능하여 입력되는 모든 무게들을 합한 값까지 반복을 수행하였으며 기존 냅색 문제와 동일하게 담을 수 있을 때 최대한의 값을 담았으며, 담은 값이 m보다 클 시 j를 비교, 저장하여 풀었다.

BOJ 4781

한가지 물건을 여러 개 고를 수 있는 냅색 문제. TC만큼 물건의 종류 n, 가방의 크기 m이 주어진다. 이 때 m은 소수로, 소수점 둘째자리까지 주어진다. 다음 n개의 줄에는 각 물건의 값, 무게가 주어진다. 무게도 마찬가지로 소수이다. 기본 냅색 문제는 dp[i-1][j], value + dp[i-1][j-weight] 위 두가지를 비교하면 되지만 이번 문제는 한가지 물건을 여러 개 고를 수도 있기 때문에 dp[i][j-weight] 또한 비교하여야 한다. 입력되는 무게가 소수점 둘째자리까지이기 때문에 100을 곱하여 int를 이용하여 형변환하여 풀었으나 시간초과 결과를 받게 되었는데, 이는 round로 수정하여 풀었다. 실수형을 형변환할 때 round가 더욱 빠른가보다.

BOJ 16172

숫자와 알파벳 대, 소문자로 이루어진 s에서 숫자를 지운 후 문자열 k가 있을 시 1, 없을 시 0을 출력하는 문제. s에서 k가 여러 개 있는 것을 확인하는 문제였으면 KMP 알고리즘을 사용하여 풀었을테지만 단순히 연속된 문자열이 있는 지 판단하는 문제라 첫 번째 풀이는 isdigit을 이용하여 숫자를 제외한 문자열을 만든 후 in 메소드를 사용하여 풀었다. 두 번째 풀이는 isdigit으로 확인이 아닌 0부터 9까지의 문자열을 기준으로 replace하여 풀었다. replace가 더욱 느릴 거 같아서 isdigit을 이용하여 풀었으나 아니였다. 역시 내장라이브러리가 짱인가보다.

BOJ 2665

0과 1로 이루어진 n, n 크기의 2차원 배열을 입력받는다. 0, 0부터 n, n까지 상하좌우로 이동할 때 0은 이동하지 못하는 곳이라고 한다. 이 때 0을 1로 바꾸어 이동할 수 있는데, 0을 1로 바꾸는 동작을 최소화하여 n, n까지 도착했을 때 해당 값을 출력하는 문제. 힙 자료구조, INF를 사용하는 다익스트라 방법을 이용하여 풀었다. 저장된 값이 현재 값보다 클 때 힙에 넣도록 하였으며 0과 1을 판단하여 cnt의 크기를 연산하여 풀었다.

BOJ 11779

n개의 도시, m개의 버스가 있다. 버스는 출발, 도착, 비용을 갖는다. 시작 도시와 도착 도시가 주어질 때, 최소 비용으로 이동했을 시 총 비용, 경로에 포함돼 있는 도시의 수, 경로를 방문하는 도시를 순서대로 출력하는 문제. 힙 자료구조를 이용한 다익스트라 방법을 이용하여 최소 비용을 구함과 동시에 방문지를 저장할 배열을 이용하여 초기화, 지금까지 방문했던 곳 추가, 다음 도시 추가 연산을 통해 풀었다.

BOJ 2798

기존 3중 반복문을 이용하여 단순 최대 값을 출력하는 방법이 아닌, 입력되는 수들을 내림차순으로 정렬 후에 m보다 같거나 클 시 set 자료형에 추가하고 break한다. 그 후에 제일 큰 값을 출력하여 풀었다. 이 방법은 set 자료형을 이용하여 중복되는 수들의 연산을 제거, 오름차순으로 정렬 후 break를 통해 추가한 수보다 작은 수들을 비교하지 않는 방법으로 연산의 수를 줄였다.

BOJ 1854

제일 빠른 경로만을 찾던 다익스트라 문제들과는 달리 k번째로 빠른 경로를 찾는 문제. 첫 번째 시도는 n개의 heap을 이용하여 정렬하며 해당 배열의 크기가 k보다 작을 때만 q에 삽입하는 형식으로 풀었으나 틀렸습니다 결과를 받게 되었다. 내가 생각하는 반례로는 다른 지점들이 k 이상이 되어야 k번째 방문 이력이 생기는 경우이다. 두 번째 풀이는 k개의 INF로 이루어진 배열이 n+1개인 2차원 배열을 이용하였다. k-1번째 수와 비교하여 비용이 작을 때 q에 삽입한 후, k-1번째 수에 삽입, 해당 배열을 정렬하여 풀었다. heap을 이용하면 더욱 빠르게 풀 수 있을 것 같으나 INF로 초기화하는 과정때문에 오히려 연산이 늘어날 것만도 같다.

BOJ 10999

기존 구간합을 구하며, 특정 인덱스의 수를 바꾸는 세그먼트 트리문제에서 구간의 인덱스를 바꾸는 방식으로 바꾼 문제. 첫 접근은 단순히 업데이트 함수를 여러번 호출하면 될 것 같았으나 당연하게도 다른 방법이 존재하였다. lazy propagation이란 방법인데, 할 일을 나중으로 미루는 방법... 이다. 해당 글을 참고하여 풀었으나 아직도 어렵기만 하다. 다른 부분은 기존 세그먼트 트리 문제와 동일하며 query와 update_range 함수 호출 시 update_lazy를 호출하여 tree의 크기와 같은 lazy배열을 이용하여 나중에 더할 값을 저장하는 연산을 수행한다. 세그먼트 트리는 감을 잡기 시작한 것 같으나 lazy propagation은 아직 멀은 것 같다.

BOJ 1976

n개의 도시 중에서 m개의 도시를 방문할려고 한다. 이 때 중복된 도시도 포함될 수 있고 같은 도시에서 도시로 이동할 수도 있다. 각 도시들간을 이동할 수 있는 지 여부를 입력받은 후, m개의 도시 순서를 입력받아 해당 순서를 이동할 수 있는 지 여부를 출력하는 문제. 첫 번째 풀이는 재귀를 이용한 DFS 형태로 풀었다. 하지만 정체모를 반례로 인해 90퍼센트쯤에서 틀렸습니다. 결과를 받았다. 두 번째 풀이는 플로이드 와샬 방법으로 3중 반복문을 통해 각 도시들간 이동 여부를 저장 후 도시 순서에 따라 확인하여 풀었다. 유니온 파인드 방법을 이용하여 풀 수 있다는데 공부해야겠다.

BOJ 1890

n x n 크기의 배열이 있다. 각 인덱스에는 아래, 오른쪽 방향으로 몇 칸갈 수 있는지 정수가 있다. 0, 0부터 n, n까지 가는 경로의 개수를 출력하는 문제. 첫번째 풀이는 queue를 이용한 DFS로 풀었으나 메모리초과 결과를 받게 되었다. 배열의 크기가 넘지 않았을 경우에는 재방문도 가능하게 구현을 하여 100 크기에 전부 1이 저장돼 있을 때 메모리초과 결과를 일으키는 것 같다. 두 번째 풀이는 n의 크기만큼 이중반복문을 수행하는 다이내믹 프로그래밍 방법을 이용하여 풀었다. 마지막 값은 저장돼 있는 값이 0이기 때문에 값이 중복되어 저장되기 때문에 마지막 값일 시 break하여 마지막 dp의 값을 출력하여 풀었다.

BOJ 1987

알파벳으로 이루어진 2차원 배열을 입력받는다. 상하좌우로 움직일 수 있으나 방문했던 알파벳은 방문할 수 없는 조건을 가질 때, 최대한 방문할 수 있는 알파벳의 수를 출력하는 문제. 첫 번째 풀이는 아스키코드를 기준으로 방문확인 배열을 만들어서 dfs 연산을 수행하여 풀었으나. 다른 노드가 방문했던 노드까지 방문했다고 확인을 하여 틀렸습니다 결과를 받게 되었다. 이를 수정하고자 q에 방문했던 알파벳들로 이루어진 문자열을 넣어 방문확인을 했으나 시간, 메모리 초과결과를 얻게 되었다. 세 번째 풀이는 첫 번째 풀이를 바탕으로 백트래킹을 사용하여 방문확인 후 재귀적으로 호출, 방문확인 해제하여 풀었다.

BOJ 1260

기존에는 dfs와 bfs 연산을 나누며, 방문한 노드들을 저장한 배열에서 확인하는 연산 방법에 확인하는 방법으로 풀었다. 이번 풀이는 한 함수에서 dfs와 bfs 연산을 구분하여 연산하며 방문확인 배열을 만들어 방문확인에 소요되는 연산을 줄였다.

BOJ 2294

n개의 동전이 입력되며 합이 k원이 되도록 할 때 동전의 최소 개수를 출력하는 문제. 최댓값인 10001로 k+1 크기의 배열을 이용하여 다이내믹 프로그래밍 방법을 이용하여 풀었다. dp[j] = min(dp[j], dp[j-coin]+1)의 점화식을 이용하였으며 coin은 입력되는 동전의 크기이다.

BOJ 1309

가로 크기 2, 세로 크기 n의 우리가 있을 때, 사자를 넣으려 한다. 사자는 가로, 세로 모두 붙어 있게 배치할 수 없으며 사자가 없을 때도 경우의 수로 계산한다. 이 때 n이 주어진 후 사자를 배치하는 경우의 수가 몇가지인 지 출력하는 문제. n이 1일 때 맨 위의 좌측에 있는 경우 1, 우측에 있는 경우 1, 없는 경우 1을 초기값 설정을 한다. 그 후 2부터 n까지 좌측에 있는 경우의 수는 i-1의 우측 + 없는 경우의 수, 우측에 있는 경우의 수는 i-1의 좌측 + 없는 경우의 수, 없는 경우의 수는 좌측, 우측, 없는 경우의 수를 더하여 풀었다. dp는 더 많이 풀어봐야될 것 같다.

BOJ 10282

a 컴퓨터가 b 컴퓨터를 의존할 시, b 컴퓨터가 해킹당하면 s초 후 a 컴퓨터가 감염된다고 한다. 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진 후 각각의 의존성이 주어질 때 총 감염되는 컴퓨터 수와 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력하는 문제. INF와 heap 연산을 이용하는 기본적인 다익스트라 방법을 이용하여 풀었다. 첫 접근은 다익스트라 연산중에 감염 컴퓨터 수와 마지막 컴퓨터가 감염되는 시간을 구할려 했으나 잘되지 않아 다익스트라 연산이 종료된 후 각각 컴퓨터들이 감염 경과 시간이 저장돼 있는 배열을 이용하여 풀었다.

BOJ 2606

그래프 탐색을 이용한 바이러스 문제를 다시 풀어보았다. 기존 방법인 현재 노드의 방문확인 후 연결된 노드들을 extend하는 방법을 유지하며 그래프의 선언 및 추가 부분을 깔끔하게 바꾼 방법으로 풀었으며 다른 방법은 요즘 주로 사용하는 자식 노드들을 기준으로 반복을 돌며 자식노드들의 방문 확인 후 q에 추가하는 방법이다. 두 방법 중 extend하는 방법이 시간이 백준 상 4ms 차이로 빠른데, 내장 함수 사용에서 나오는 차이갔다. 하지만 extend는 확장성이 떨어지기 때문에 간단한 문제에서만 쓰일 것 같은 내 예상이다.

BOJ 1719

n개의 노드, m개의 쌍방향 간선이 있을 때 최단거리로 다른 모든 노드들을 방문할 때 먼저 들리는 노드의 번호를 모든 노드에 대해서 출력하는 문제. 3중 반복문을 사용하는 플로이드 와샬 방법을 이용하여 풀었다. ik + kj 값으로 거리가 갱신될 시 첫번째로 방문하는 노드를 저장하는 배열의 값 ik를 ij에 저장하여 풀었다. 두 번째 풀이는 숏코딩으로 풀었다.

ORDER 001

Prototype 객체를 학년, 전공, 동아리 기준으로 정렬하는 요구사항. slice를 이용하여 값만이 똑같은 객체를 만든 후 해당 배열을 기준으로 버블 정렬하였다. 기준 마다 comparator를 만들어 인덱스 값마다 값 변화 여부를 반환하였다. 동아리는 알파벳 순이 아닌 정렬 순서가 정해져 있어 Object 자료형을 이용하여 해당 순서에 대한 정수를 부여하여 정렬 여부를 반환하였다.

BOJ 1660

1, 4, 10, 20, 35의 순으로 커지는 동전이 있을 시 n원을 나타내는 최소한의 동전의 수를 출력하는 문제. n보다 작은 동전들을 구한 후 최대값으로 dp 배열을 선언 후 dp 배열의 동전 가격 인덱스를 1로 초기화하였다. 그 후 동전의 수와 동전부터 n까지 이중 반복문을 수행하며 dp[j] = min(dp[j], dp[j - coins[i]] + 1)의 점화식을 이용하여 풀었다. dp는 계속 풀어도 적응이 안되는 것만 같다.

BOJ 1965

상자의 크기가 주어졌을 때 앞의 상자는 뒤에 있는 상자보다 작을 때 들어갈 수 있다고 한다. n개의 상자의 크기가 주어질 때 한 번에 넣을 수 있는 최대 상자 개수를 출력하는 문제. 가장 긴 증가하는 수열 문제와 같이 수가 증가하는 부분이 제일 큰 것을 출력하는 문제. 첫 풀이는 입력되는 마지막 상자부터 첫 상자까지 반복을 수행하며 크기를 비교하여 dp[j] = max(dp[i]+1, dp[j])의 점화식을 이용하여 풀었다. 두 번째 풀이는 처음부터 마지막까지 반복하며 dp[i] = max(dp[i], dp[j]+1)의 점화식을 이용하여 풀었다.

BOJ 19622

n개의 회의 시작 시간, 종료 시간, 회의 인원이 주어진다. 임의의 회의 k는 k-1과 k+1과 시간이 겹치며 다른 회의와는 겹치지 않는 조건이 있다. 이 조건을 이용하여 점화식 l[i] = max(l[i-2], l[l-3]) + l[i]을 유추하여 풀었다. n이 2 이하일 때 max(l)을 출력 후 프로그램을 종료하여 예외처리하였다.

BOJ 4072

음수가 존재하는 연속되는 가장 큰 구간합을 출력하는 문제. 쉬워보여 접근했다 혼쭐났다. 첫번째 풀이는 2중 반복문을 이용하는 DP 풀이로 시간초과 결과를 받게 되었으며 모두 음수일 경우 때문에 시간초과가 나는가 하여 확인 후 예외처리하였지만 결과는 똑같았다. 두 번째 풀이는 세그먼트 트리를 이용하여 모든 구간합 중 큰 것을 출력하여 풀려했으나 init 시에는 각 자식 노드들의 합만이 저장되는 것을 간과하여 중도포기하였다. 세 번째 풀이는 카데인 알고리즘이라는 방식이라는 데 검색 후 결과는 네 번째 풀이가 더욱 카데인 알고리즘의 모습을 띄고 있는 것 같다. 일단 세 번째 풀이는 각 구간의 합을 비교, 전부 음수일 시 가장 큰 수 하나만을 출력하는 평태이며, 네 번째 풀이는 반복문 한가지만을 이용하여 DP를 사용한 풀이이다. 간단히 DP를 이용하여 풀 수 있었는데 아직도 많이 부족하다.

BOJ 2749

1,000,000,000,000,000,000보다 작거나 같은 n이 주어질 때, n 번째 피보나치 수를 출력하는 문제. 첫 번째 풀이는 단순 DP 방법을 이용하여 풀었으나 당연하게도 메모리 초과 결과를 받게 되었다. 피보나치 수를 나눈 수는 주기를 갖는 특징, 피사노 주기를 계산하여 해당 값을 이용하여 피보나치 수를 계산, 해당 값을 출력하여 풀었다.

BOJ 1260 - nodeJS

DFS와 BFS 방문 순서를 출력하는 문제를 JS를 이용하여 풀어봤다. 알고리즘의 구성은 입력 부분을 제외하고는 모두 파이썬으로 푼 코드와 동일하지만 틀렸습니다 결과를 받았다... 도저히 어떤 부분이 틀렸는 지 모르겠다. JS는 BOJ가 아닌 프로그래머스를 참고하여 풀어야하나 싶다.

BOJ 1717

n개의 노드가 있을 때 각 노드들이 연결되어 있는 지 여부를 출력 및 합연산을 하는 유니온 파인드 문제. 기존 유니온 파인드로 풀 수 있는 문제들을 플로이드 와샬, DFSBFS 등의 방법으로 풀었으나 유니온 파인드 방법도 알아두면 좋을 것 같아 공부해보았다. 유니온 파인드는 주어진 노드 또는 집합을 합하는 Union과 노드의 루트 노드가 무엇인 지 반환하는 Find로 나뉜다. 자세한 사항은 주석을 참고. 해당 문제는 간단한 유니온 파인드의 구현으로 풀었다.

BOJ 4195

n개의 두 문자열이 공백으로 나눠져 입력된다. 해당 두 문자열은 서로 연결된 상태이며 매 입력마다 해당 관계의 연결된 모든 노드의 수를 입력하는 문제. 첫번째 풀이는 단순 DFS 탐색을 통해 풀었으나 예상했던 것 같이 시간초과결과를 받게 되었다. 입력되는 방문확인을 배열로 하며 in 메소드를 이용하여 확인한 것과 매 입력마다 DFS 연산을 수행하는 점이 작성하면서도 시간초과가 확실할 것으로 예상했다. 두 번째 풀이는 유니온 파인드 방법을 이용하여 풀었다. 부모 노드를 저장하는 딕셔너리, 해당 노드의 연결된 사람을 저장하는 딕셔너리 두개를 이용하여 union시 루트 노드의 값을 더해준 후 입력되는 문자열의 루트 노드의 수를 출력하여 풀었다.

BOJ 1850

두 수 n, m을 입력받은 후 각 수만큼 1로 이루어진 수의 최대공약수를 출력하는 문제. 첫 풀이는 1로 만든 수를 이용하여 유클리드 호제 방법을 이용하여 풀었으나 메모리초과 결과를 받게 되었다. 1로 바꾸지 않은 최대공약수의 규칙을 보니 해당 수를 1로 바꾸면 정답이 되는 것을 찾아 풀었다.

BOJ 1976

n개의 도시마다 다른 도시들로 갈 수 있는지 입력받은 후, m개의 도시 루트를 입력받는다. 해당 루트대로 이동 할 수 있으면 YES, 아닐 시 NO를 출력하는 문제. 첫 번째 풀이는 플로이드 와샬 방법을 이용하여 완전 탐색하여 풀었다. 이번 풀이는 유니온 파인드 방법을 이용하여 풀었으며 입력되는 루트의 부모 루트가 모두 동일 시 YES를, 아닐 시 NO를 출력하여 풀었다.

BOJ 10775

G개의 게이트에 P개의 비행기가 순서대로 도착할 예정이다. 각 비행기는 1번부터 입력되는 gi번까지 도킹할 수 있을 때 최대한 많은 비행기가 도킹한 수를 출력하는 문제. 첫 번째 풀이는 그리디 방법을 이용하여 입력되는 gi부터 0까지 반복문을 이용하여 풀었으나 당연하게도 시간초과 결과를 받게 되었다. 입력되는 G와 P의 최대 수가 10의 5승이기 떄문. 두 번째 풀이는 유니온 파인드 방법을 이용하여 gi마다 루트 노드를 찾으며 해당 노드와 -1한 노드를 union한다. 위 연산을 반복하여 gi의 루트 노드가 0일 때 반복문을 종료하여 풀었다. 유니온 파인드를 이런 방법으로도 응용할 수 있는 지 알게 되었다.

BOJ 1744

n개의 수가 입력될 때, 그 수열의 합을 구하려고 한다. 하지만 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶을 때 위치와 상관없이 묶을 수 있으며 묶은 두 수는 서로 곱한 후에 더한다. 수열의 모든 수는 단 한번만 묶거나, 묶지 않아야할 때 그 합의 최대치를 출력하는 문제. 입력되는 수들을 1 이상의 정수들과 0과 음수들을 저장하는 두 배열에 나눠 저장한다. 정수들은 내림차순으로 정렬하여 큰 수들 먼저 두개씩 묶어 곱한 값을 더하며 이 때 두 수 중 1이 있을 때는 더하는 연산을 하여 저장하였다. 0과 정수들은 내림차순으로 정렬하여 작은 수들을 먼저 묶어 주어 연산된 값을 출력하여 풀었다.

BOJ 14502

Y, X 크기의 연구실에 바이러스가 퍼졌다. 바이러스는 상하좌우로 퍼질 수 있으며 벽을 넘지 못한다. 3개의 벽을 세울 수 있을 때 바이러스가 퍼질 수 없는 영역의 최대 크기를 출력하는 문제. 바이러스는 2, 벽은 1, 빈 공간은 0으로 입력된다. 백트래킹 방식을 이용하여 재귀적으로 모든 경우에 벽을 세운 후 세운 벽이 3개가 될 시 바이러스가 퍼지는 함수를 이용하여 새로운 배열에 바이러스가 퍼진 상태로 만든다. 해당 배열을 기준으로 안전영역의 크기를 global로 값을 비교하여 풀었다. 브루트포스, 그래프 탐색, 백트래킹이 합쳐진 형태로 풀었다.

BOJ 14938

n개의 도시, m의 수색 범위, r개의 길이 있다. 각 도시에 ni개의 아이템이 있을 때 수색 범위가 넘지 않는 선에서 아이템을 찾을 수 있는 최대 수를 출력하는 문제. 첫 풀이는 입력받는 길들을 인접 리스트 형식으로, 존재하지 않는 길은 INF로 입력을 받은 후 플로이드 와샬 방법을 이용하여 수색범위가 넘지 않았을 때 추가하는 방법으로 풀었으나 틀렸습니다 결과를 받게 되었다. 아마 추가적인 연산이 있지 않았을 까 의심된다. 두 번째 풀이는 인접 행렬을 이용한 다익스트라를 이용하여 풀었으며 수색 범위가 넘지 않았을 때 힙에 추가, 방문 확인 배열을 이용해 방문하지 않았던 도시들의 아이템만 연산하였다. 다익스트라 연산을 n번하여 찾은 최대값을 출력하여 풀었다.

BOJ 12852

정수 n을 입력받은 후 해당 정수가 3으로 나누어 떨어지면 3으로 나누며, 2로 나누어 떨어지면 2로 나누기, 1을 빼기 3개의 연산이 가능할 때 이를 적절히 사용해 1로 만들 때 연산을 사용하는 횟수의 최솟값과 방법에 포함되어 있는 수를 출력하는 문제. 기본 1로 만들기에서 방법에 포함되어 있는 수를 추가한 문제. 첫 번째 풀이는 힙을 이용하여 그래프 탐색과 같은 방법으로 연산하며 1일 때 필요한 값을 반환하도록 풀었으나 시간초과 결과를 받게 되었다. 두 번째 풀이는 i가 1로 만들어질 때 필요한 값을 저장하는 배열을 이용하여 다이내믹 프로그래밍 방법을 이용하여 풀었다. 값이 갱신될 때 방법에 포함되어 있는 수를 저장하는 2차원 배열에 값을 추가하도록 풀었다.

BOJ 9084

TC만큼 n개의 동전을 입력받고 m원을 해당 동전으로 몇가지 경우의 수로 나타낼 수 있는 지 출력하는 문제. n과 m+1까지를 이용하여 반복문을 수행하며 1원부터 m원까지의 경우의 수를 계산하였다. 현재 동전 i가 현재 가격 j를 이용하여 dp[j] += dp[j-coins[i]]의 점화식을 이용하여 풀었다.

BOJ 1914

세 개의 판에 n개의 원판이 있는 하노이 탑 문제. 옮긴 횟수를 출력한 후, n이 20 이하일 때만 이동하는 경로를 출력하는 문제. 2의 n승 - 1이 하노이 탑의 옮긴 횟수임에 먼저 출력한다. 그 후 1번 판에 있는 원판의 수, 출발할 곳, 안쓰는 곳, 도착할 곳을 매개 변수로 재귀적으로 호출하여 풀었다. 하노이탑 문제는 아직 이해도가 부족한 것 같다.

BOJ 11729

세 개의 장대가 있는 하노이 탑이며 n개의 첫 번째 장대에 있을 때 옮긴 횟수와 옮긴 위치를 출력하는 문제. 2의 n승 -1의 옮긴 횟수를 출력하며 재귀적으로 첫 번째 장대에 있는 원판의 수, 출발하는 장대, 안쓰는 장대, 도착하는 장대를 매개변수로 사용하여 풀었다.

BOJ 1520

Y, X 크기의 정수로 이루어진 2차원 배열이 입력된다. 0, 0 위치에서 Y-1, X-1까지 해당 자리의 정수가 낮은 곳으로만 이동할 때, Y-1, X-1에 도착하는 경우의 수가 몇가지인 지 출력하는 문제. 첫 번째 풀이는 단순 다이내믹 프로그래밍 방법을 이용하여 풀었으나 먼저 계산된 곳이 있을 시 연산이 안되는 부분이 있어 각 방향마다 연산을 더 하도록 하지 않는 이상 안될 것 같아 방향을 틀었다. 두 번째 풀이는 -1로 선언된 배열을 만든 후 해당 배열을 이용하여 방문확인과 함께 이동방향의 값을 더하는 것을 재귀적으로 연산하여 풀었다.

BOJ 13424

N개의 방, M개의 길이 있으며 각 길은 두 방의 번호, 길이를 입력받는 양방향 길이다. K명의 사람이 다른 방에 있을 때 이동 거리의 총하빙 최소가 되는 방을 출력하는 문제. 인접행렬을 이용하여 초기화는 INF로, 입력 후에는 길이를 저장하였다. 모든 입력이 완료될 시 플로이드 와샬 방법을 이용하여 모든 노드에 대해서 최소 길이를 저장 후, K명의 이동 거리를 총합하는 배열을 관리하여 풀었다.

BOJ 10216

최대 5000의 값을 갖는 좌표 y, x와 반경 거리를 나타내는 r이 입력된다. n개의 좌표가 입력될 때 연결된 것을 계산하여 몇 개의 구역이 있는 지 출력하는 문제. 첫 번째 풀이는 5000의 크기를 갖는 2차원 배열을 이용하여 dfs를 사용해 풀었으나 메모리초과와 시간초과 결과를 받게 되었다. 입력되는 점과 방문확인을 위한 배열을 한 개로 사용하여도 같은 결과를 받았다. 두 번째 풀이는 유니온 파인드 방식을 이용하여 풀었다. 행렬, 리스트를 사용하지 않으며 n개의 배열을 만들어 x의 차이, y의 차이를 각각 곱한 값을 더한 값과 두 좌표의 r을 곱한 값을 비교하여 r을 곱한 값이 클 시 연결돼 있음을 판단하여 합집합 연산을 하여 풀었다.

BOJ 5585

n원의 물건을 살 때 1000원을 냈다고 한다. 이 때 500, 100, 50, 10, 5, 1원으로 거스름돈의 개수가 최소가 될 떄의 개수를 출력하는 문제. 간단한 그리디 방법을 이용하여 풀었다.

BOJ 18352

n개의 �도시에 단방향이며 거리가 1인 m개의 도로가 있다. x 도시부터 출발하여 최단거리가 k인 도시들을 출력하는 문제. 힙과 INF를 이용하는 다익스트라 방법을 이용하여 풀었으며 입력되는 도로들을 인접리스트 형식으로 사용하였다. x로부터 모든 도시들의 이동 거리를 배열에 저장 후 filter을 사용하여 거리가 k인 도시들을 저장 후 출력하여 풀었다.

BOJ 2225

0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 구하는 문제. 수의 순서만 다를 때도 다른 경우로 새며 한 개의 수를 여러 번 쓸 수도 있다. k가 1일 때는 모든 경우가 1이며, 2일 때는 i+1의 값들이 정답이다. 경우의 수를 나열해보니 1, 3 = (1, 2 + 1, 1)과 같은 dp[i] = dp[i] + dp[i-1]의 점화식이 도출되어 k+1과 n+1까지의 이중 반복문을 이용하여 풀었다.

BOJ 2268

세그먼트 트리를 이용해 sum과 modify를 구현하는 문제. sum을 구현할 때 i가 j보다 큰 경우가 있어 WA를 많이 받았다.

BOJ 2491

n개의 수가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나 작아지는 수열 중 가장 길이가 긴 것을 찾아, 그 길이를 출력하는 문제. 커지는 것과 작아지는 것을 관리하는 두 배열을 만든 후 반복문을 이용하여 조건에 충족했을 때 dp[i] = dp[i-1] + 1의 점화식을 이용하여 풀었다.

BOJ 1788

피보나치 수를 음수일 경우까지 확장한 문제. n <= 1일 때고 f(n) = f(n-1) + f(n-2)가 성립되도록 확장한다. n이 주어진 후 해당 피보나치수가 양수일 때 1, 음수일 때 -1, 0일 때 0을 출력한 후, 해당 피보나치수의 절댓값을 출력하는 문제. 절댓값을 출력하는 부분에서 음수와 양수의 값이 다르지 않다는 것을 유추하게 되었다. 첫 접근은 -1보다 작은 수들을 -1로 출력한 후 최대 크기만큼 연산 후 절댓값 n의 피보나치 수를 출력하여 풀었으나, n이 홀수일 때는 양수가 나오게 되어 WA 결과를 받게되었다. 조건문에 해당 조건을 추가한 후 나머지 연산은 그대로 이용하여 풀었다.

BOJ 1939

n개의 섬에 양방향 m개의 다리가 있다. 이 때 해당 다리가 옮길 수 있는 최대 무게가 주어진다. 출발 섬과 도착 섬이 주어질 때 옮길 수 있는 최대 무게를 출력하는 문제. 분리집합 방식으로 풀었다. 입력받는 다리들을 Max heap형태로 저장 후, 모든 입력이 끝나면 각 다리의 두 섬을 union 연산한다. 그 후 정답을 찾을 두 섬의 parent 노드를 find 연산을 이용하여 비교하여 같을 시 현재 반복중인 다리의 길이를 출력하여 풀었다.

BOJ 10026

RGB로 구분되는 n 크기의 이차원 배열을 입력받는다. 그 후 일반인이 느끼는 구역과 적록색약이 느끼는 구역을 출력하는 문제. 입력받는 이차원 배열을 일반인과 색약으로 구분하여 저장하고 각각 방문확인 배열을 만들어 dfs 연산을 이용하여 풀었다.

BOJ 13699

다음의 점화식에 의해 정의된 수열이 있다. t(0)=1, t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 정수 n을 입력받은 후 t(n)을 출력하는 문제. 최대 크기인 35까지 i로 반복문을, i까지 j로 반복문을 수행하며 dp[i] += dp[j] * dp[i-j-1]의 점화식을 이용하여 풀었다.

프로그래머스 2x타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있다. 이 때 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채울 때 해당 경우의 수를 출력하는 문제. 첫 번째 풀이는 배열에 n일 떄의 값을 메모이제이션하여 활용하여 마지막 두 값을 더해주며 풀었다. 두 번쨰 풀이는 마지막 두 값만을 이용하는 것을 이용하여 변수 두 개를 이용하여 풀었다.

프로그래머스 두개뽑아서더하기

정수로 이루어진 배열이 주어지고 해당 배열의 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 문제 인덱스가 겹치지 않도록 이중 반복을 수행하며 set 자료형에 더하여 반복문 종료시 해당 set을 정렬한 list로 반환하여 풀었다.

프로그래머스 크레인인형뽑기게임

n x n 크기의 이차원 배열을 입력받는다. 해당 배열에는 다양한 인형들의 번호와 빈칸인 0으로 이루어져있다. 인형을 뽑는 인덱스로 이루어진 moves가 주어지며, 해당 순서대로 인형을 뽑아 바구니에 넣는다. 바구니에 넣은 인형의 종류가 같은 게 붙어있을 시 두 인형은 터져 없어진다. 터져 없어진 인형의 수를 출력하는 문제. 반복문을 이용하여 각 열의 인형들을 넣기 전에 마지막 요소와 비교하여 연산하였다. 터진 횟수 * 2를 반환하여 풀었다.

프로그래머스 멀쩡한사각형

가로 길이가 W, 세로 길이가 H인 직사각형이 았다. 종이는 1, 1 크기의 격자 형태로 선이 그어져 있다. 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았을 때, 온전한 사각형의 수를 구하는 문제. 최대공약수를 이용해야하는 것은 알았지만 어떤 방식으로 이용해야되는 지 감을 잡기 어려웠다. 검색을 통해 (w * h) - (w + h - gcd(w, h))가 공식인 것을 알게 됐다. 첫 번째 풀이는 유클리드 호제 방법을 이용하여 최대공약수를 구하는 것을 작성하여 풀었으며 두 번째 풀이는 내장 라이브러리의 gcd를 이용하여 풀었다.

프로그래머스 가장큰수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 구하는 문제. 첫 번째 풀이는 백트래킹 방법을 이용하여 모든 경우의 수를 한 배열에 저장하여 해당 수 중 제일 큰 수를 출력하도록 풀었으나, 입력될 수 있는 수가 최대 100,000개임으로 시간초과 결과를 받게 되었다. 그리디 방법을 이용할려 했으나, 문자열을 기준으로 정렬시에 30과 3의 정렬에서 차질이 생겨 고민 중, 정렬 기준을 문자열화 한 것의 3을 곱한 풀이를 보았다. 303030과 333을 정렬하여 333이 더욱 높게 판단되게 하여 풀었다.

BOJ 17396

노드의 수와 간선의 수 n, m을 입력받는다. 그 후 노드를 지나칠 수 있는지에 대한 여부와 양방향 간선들을 입력받아 0번째 노드부터 n-1번째 노드에 도착하는 최소 시간을 출력하는 문제. 간선은 인접리스트 방식으로 저정하였으며, 지나칠 수 있는 지 여부에 따라 저장을 관리하였다. 그 후 힙을 이용한 다익스트라 방식을 사용해 풀었다. 바로 다음 간선들을 이용하여 추가하여 풀 시 시간초과 결과를 받기 때문에, 간선을 이용하기 전 현재 저장값보다 클 시 continue하여 풀었다. 덕분에 진짜 다익스트라 방식을 안 것만 같다.

프로그래머스 124나라의숫자

정수 n을 124만을 이용하여 표현하는 문제. 문자열 124의 인덱스를 이용하여 배열에 추가하는 방식을 이용하였으며, 해당 숫자는 n-1한 값의 3으로 나눈 나머지를 할당하여 풀었다. 쉬운 문제였으나 다소 시행착오를 겪었다. 낮은 난이도도 자주 풀어봐야겠다.

프로그래머스 k번째수

정수로 이루어진 배열 array와 3개의 정수가 들어가 있는 배열들로 구성된 배열 commands를 입력받는다. 그 후 각 commands 마다 array s부터 e까지 수들 중 오름차순으로 정렬하여 k번째 수를 배열에 담아 해당 배열을 반환하면되는 문제. for in 문과 리스트 슬라이싱, sorted 메소드를 활용하여 간단히 풀었다.

BOJ 14438

특정 구간 제일 작은 수를 구하며 업데이트하는 세그먼트 트리 문제. 업데이트 시 범위를 벗어 날 시 INF를 반환하였었는데 해당 부분 때문에 WA를 받았었다. 업데이트 시 해당 인덱스와 바꿔야하는 값을 이용하여 start == end일 시 바꿔야되는 값으로 바꾸어 풀었다.

BOJ 10211

TC만큼 n개의 정수로 이루어진 배열을 입력받는다. 해당 배열 중 원소의 합이 제일 큰 부분 배열의 값을 출력하는 문제. 다이내믹 프로그래밍 방법을 이용하여 dp[i] = max(dp[i], dp[i] + dp[i-1])의 점화식을 이용하여 풀었다.

BOJ 2563

100, 100 크기의 종이에 10, 10 크기의 색종이를 붙인다고 한다. 붙은 색종이의 수 n과 각 색종이들이 아랫변에서의 거리, 왼쪽변에서의 거리가 주어질 때 색종이가 붙은 영역의 크기를 출력하는 문제. 100, 100 크기의 배열을 만들어 붙어있는 지 확인하여 풀었다.

BOJ 2228

N개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M개의 구간을 선택해서 구간에 속한 수들의 총 합이 최대가 되도록 할 때, 각 구간은 한 개 이상의 수가 있어야하며, 구간끼리 겹치거나 인접해 있어선 안되며, 정확히 M개의 구간이 있어야할 때 최대값을 출력하는 문제. 첫번 째 풀이는 인접하면 안되는 조건을 보지 못하여 단순 반복문을 이용한 다이내믹 프로그래밍 방벙을 이용하였다. 두 번째 풀이는 구역별로 최대값을 저장하는 이차원배열을 이용하는 방법을 작성하였다. 해당 게시물을 참고하여 작성하였으며, dp1에는 선택을 하지 않는 경우의 수 중 제일 큰 값을, dp2에는 선택을 하는 경우에서 제일 큰 값을 저장한다. 구간이 인접하지 않아야하는 조건때문에 dp2[i][j] = max(dp1[i-1][j-1] + l[i], dp2[i-1][j] + l[i])의 점화식을 사용하는 것 같은데, 정확한 풀이는 아직 모르곘다. 나중에 다시 풀어봐야겠다.

프로그래머스 가장큰정사각형찾기

0과 1로 이루어진 이차원 배열 board가 주어진 후, 해당 배열에서 가장 큰 정사각형의 넓이를 출력하는 문제. 좌표 1, 1부터 해당 값이 0이 아니며, 위, 왼쪽, 왼쪽 위 대각선의 값을 중 제일 작은 값 +1한 것을 저장한다. 그 중 제일 큰 값끼리 곱한 값을 반환하여 풀었다.

프로그래머스 H-index

어느 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면, h의 최대값이 과학자의 H-index라고 한다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열이 주어질 때 H-index를 구하는 문제. 그리디 방식을 이용하여 내림차순으로 정렬 후, 0부터 n-1까지 반복문을 수행하였다. 인덱스 i가 정렬된 i번째 값보다 클 시 i를 반환하여 풀었다. 배열의 값이 모두 동일할 시 반환이 되지 않아 마지막에 길이를 반환해 주었다.

프로그래머스 올바른괄호

괄호가 바르게 짝지어졌다는 것은 ( 문자로 열렸으면 반드시 짝지어서 )로 닫혀야 한다는 뜻이다. 괄호로만 이루어진 문자열이 주어졌을 때 올바른 괄호이면 True를, 아닐 때 False를 반환하는 문제. 문자열의 각 문자가 )일 때 -1, (일 때 1을 더하는 정수형 변수를 이용하여 해당 변수가 0과 같은 지를 반환하며 반복문 중에 해당 변수가 0이며 )일 시 False를 반환하여 풀었다.

BOJ 2493

n개의 높이의 탑이 주어진다. 각 탑의 신호는 왼쪽으로 향하며 높이가 작은 탑은 신호를 수신할 수 없다. 가장 먼저 수신하는 신호의 번호를 공백으로 나누어 출력하는 문제. 첫 번째, 두 번째 풀이는 이중 반복문과 함수를 재귀적으로 이용해, 모든 경우의 수를 확인하여 풀었으나 당연히 시간초과 결과를 받게 되었다. 세번째 풀이는 값과 인덱스를 저장하는 스택을 이용하여, 처음부터 마지막까지 값을 비교하는데, 스택의 마지막 값이 현재 반복중인 값보다 클 시 해당 인덱스의 값을 인덱스 스택의 마지막 값에 할당한다. 값이 작거나 같을 시에는 스택의 값을 빼주어 비교할 연산을 줄여 풀었다.

프로그래머스 큰수만들기

문자열로 이루어진 정수가 주어진다. 해당 정수의 형태를 유지하여 k개의 숫자를 빼어 만들 수 있는 가장 큰 수를 출력하는 문제. 첫 번째 풀이는 백트래킹 방법을 이용하여 모든 경우의 수를 set 자료형에 저장하여, 제일 큰 값을 출력하여 풀었지만 시간초과 결과를 받게 되었다. 두 번째 풀이는 스택을 이용한 풀이로, 스택의 마지막 값들과 현재 반복중인 값을 비교하여 k를 감소, 스택에서 제외한 후 현재 반복중이였던 값을 스택에 추가한다. 앞에서부터 큰 수들이 들어감으로써 k가 0이 되지 않았을 시 감소한 k만큼 뒤에서 잘라주어 반환하여 풀었다.

BOJ 4796

연속되는 p일 동안 l일만 캠핑장을 이용할 수 있다고 한다. 이 때 휴가 v일 동안 최대 캠핑장을 며칠간 이용할 수 있는 지 출력하는 문제. v // p * l 값을 변수에 저장 후, 남은 휴가 중 캠핑장을 이용할 수 있는 수(휴가 일 수 - v // p에 p를 곱한 값)과 l을 비교하여 l이 더 클 시 남은 휴가 중 캠핑장을 이용할 수 있는 수를 아닐 시 l을 더해주어 풀었다.

BOJ 10974

n이 주어졌을 때, 1부터 n까지의 수로 이루어진 순열을 사전순으로 출력하는 문제. 정수를 저장하는 배열과 방문확인을 위한 배열을 이용한 백트래킹 방법을 이용하여 풀었다.

프로그래머스 기능개발

개발 진행도와 개발 속도, 두 배열을 입력받는다. 개발 진행도가 100 이상일 때 배포가 가능하며, 앞에 있는 것을 먼저 배포해야만 하며 뒤에 이미 개발 진행도가 100 이상인 것과 함께 배포가 된다. 각 배포마다 몇 개의 기닝이 배포되는 지를 반환하는 문제. 첫 번째 풀이는 for를 이용하여 각 기능들을, while을 이용해 days를 관리하여 풀었다. 두 번째 풀이는 입력받는 두 배열을 deque화한 후, while만을 이용하여 조건 충속시 popleft 되도록 풀었다.

BOJ 1043

사람의 수 n, 파티의 수 m이 주어진다. 그리고 진실을 아는 사람의 수와 번호가 주어지고. m개의 줄만큼 파티에 오는 사람의 수와 번호가 주어진다. 파티에서 진실을 아는 사람이 없으며, 진실을 아는 사람과 같이 파티를 한 사람이 없는 파티의 수를 출력하는 문제. 유니온 파인드 방식을 이용하여 풀었으며 모든 파티에 오는 사람들을 union하였다. 진실을 아는 사람을 저장하는 배열을 관리하여 union시 부모노드들의 값을 관리하여 풀었다.

프로그래머스 스킬트리

문자열로 이루어진 스킬 순서와 문자열로 이루어진 배열인 스킬 트리가 주어진다. 스킬 순서에 없는 스킬은 상관없으며 스킬 순서와 맞는 스킬 트리가 몇개인 지 출력하는 문제. 모든 스킬 트리를 반복으로 수행하며 입력받는 스킬 순서를 deque화 하였다. 스킬 순서에 존재하는 스킬이지만 스킬 순서를 popleft한 값과 동일하지 않을 시 break를, for else를 이용하여 for문의 반복이 끝까지 수행됐을 시 정수형 변수 값을 늘렸다. 모든 반복이 종료됐을 시 반환하여 풀었다.

BOJ 5972

n개의 지역, 양방향에 가중치가 있는 m개의 간선이 있을 때 1번 지역부터 n번 지역까지 이동할 떄 최소의 가중치를 출력하는 문제. INF와 heap 연산을 이용하는 다익스트라 방법을 이용하여 풀었다.

프로그래머스 프린터

프린터에 예약된 문서들의 중요도와 인덱스를 입력받는다. 해당 프린터는 제일 왼쪽의 문서의 중요도와 예약된 문서들의 중요도를 비교하여 더욱 높은 값이 있을 시 예약의 가장 오른쪽에 넣는다. 아닐 시 해당 문서를 출력한다. 주어진 인덱스의 문서가 몇 번째로 출력되는 지 반환하는 문제. 주어지는 중요도와 문서의 인덱스 값으로 이루어진 배열을 deque화 한 후, 위의 로직을 구현하여 popleft한 인덱스 값과 주어진 인덱스 값을 비교하여 풀었다.

BOJ 16562

n명의 친구와 m개의 친구 관계도, k원이 있을 때 모든 친구들을 살 수 있는 최소 금액을 출력하며 살 수 없을 시 문자열을 출력하는 문제. 유니온 파인드 방법을 이용하여 풀었다. union 연산 시에 입력받는 친구의 가격을 비교하여 값이 작은 친구를 부모로 저장하였다. 그 후 모든 친구들의 부모를 set 자료형에 담은 후 해당 친구들의 값을 더하여 비교 후 출력하여 풀었다.

BOJ 1915

n, m의 크기 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 출력하는 문제. 1, 1 좌표부터 n, m까지 반복문을 수행하며 해당 좌표의 값이 1일 시, 왼쪽, 위쪽, 대각선 왼쪽 위와 값을 비교하여 제일 작은 값 + 1을 저장하였다. 저장된 값 중 제일 큰 것을 서로 곱한 후 출력하여 풀었다.

BOJ 18223

V개의 정점, E개의 간선, 들려야할 정점 P가 주어진다. 1부터 V까지의 최단거리와 1부터 P를 들려 V에 도착하는 최단거리가 같을 시 "SAVE HIM"을, 다를 시 "GOOD BYE"를 출력하는 문제. 첫 번째 풀이는 플로이드 와샬 방법을 이용하여 모든 정점으로부터의 최단거리를 계산한 후, 1부터 V까지의 값과 1부터 P까지의 값 + P부터 V까지의 값을 비교하여 풀었으나 시간초과 결과를 받게 되었다. 두 번째 풀이는 INF와 heap을 사용하는 다익스트라를 구현하여 1부터의 최단거리들, P부터의 최단거리를 계산하여 위 공식을 대입해 풀었다.

프로그래머스 다리를지나는트럭

다리의 길이, 다리가 버틸 수 있는 무게, 트럭들의 무게가 주어진다. 트럭은 1초에 1만큼 움직일 때 몇 초가 지나야 모든 트럭이 다리를 지날 수 있는 지 출력하는 문제. 첫 번째 풀이는 다리의 길이만큼 0으로 이루어진 배열을 만든 후, 트럭들을 popleft한 값 - 다리의 마지막 값 + 현재 다리에 있는 총 값을 다리의 하중과 비교하여 추가적으로 트럭이 다리에 진입할 수 있을 때 appendleft를 이용하여 추가, 아닐 시 appendleft를 0으로 추가 후 마지막 값을 뺀 후, 마지막 값이 0이 아닐 시 다리를 지나간 트럭의 수를 계산하는 변수를 이용하여 비교하여 풀었다. 추가적으로 연산을 줄이기 위해 sum 함수가 아닌 현재 다리에 있는 총 값을 저장하는 변수를 만들어 사용하여 풀었다. 두 번째 풀이는 다른 사람의 풀이를 각색하여 풀었다. 다리의 길이 만큼 배열을 만든 후, 다리의 길이가 존재할 때까지 반복문을 수행한다. 가장 왼쪽에 있는 값을 뺀 후, 넘어가야하는 트럭이 존재할 때, 무게를 비교하여 다리에 값을 추가하여 풀었다. 마찬가지로 무게를 비교할 때 sum 함수가 아닌 변수를 선언하여 관리하였다.

프로그래머스 전화번호목록

문자열로 이루어진 배열이 주어진다. 한 번호가 다른 번호의 접두어인 경우 False를, 없을 시 True를 반환하는 문제. 첫 번째 접근은 startswith 메소드를 이용하여 풀려 했으나, 어떤 반례인 지 틀리는 경우가 존재하였다. 두 번째 풀이는 딕셔너리 자료형을 이용하여 저장 후 모든 문자열에 대해서 빈 문자열에 한 단어 씩 추가, 해당 문자열을 딕셔너리 자료형에 있는 지 비교하여 풀었다.

BOJ 9507

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]의 수열의 i번 째를 출력하는 문제. 최대 입력 예제인 68까지 수열을 만든 후 입력되는 테스트케이스를 출력하여 풀었다.

BOJ 4803

그래프의 정점의 수, 간선의 수가 주어진다. 그 후 간선을 잇는 두 정점이 주어진다. 해당 그래프에서 사이클이 없는 트리의 개수를 구하는 문제. 두 풀이 모두 유니온 파인드 방법을 이용하여 풀었다. 첫 번째 풀이는 유니온 시 두 부모 노드가 같을 시 해당 부모 노드의 값을 모두 0으로 바꿔주어 트리인 것을 처리할려했다. 그대로 제출했더니 RecursionError를, setrecursionlimit를 설정하여 제출시 메모리초과 결과를 받았다. 질문을 통해 알게 된 사실인데 0이 속한 그룹의 루트가 0이라는 보장이 없기 때문에 루프가 생기는 문제가 있었다. 사이클인 트리와 연결되는 다른 노드.. 가 있을 때 정도라고 이해했다. 두 번째 풀이는 해당 부모노드의 값이 사이클인 지 저장하는 배열을 이용하여 풀었다. 유니온 시 더욱 작은 값을 부모 노드에 저장하고, 큰 노드의 값이 사이클이면 작은 노드의 값도 사이클로 할당하였다. 또한 간선이 잇는 노드를 입력받을 시 두 노드의 부모 노드가 같을 시 사이클로 저장하였다. 출력시 사이클이지 않은 값을 세어 주었으며, 사이클이 아닐 시 해당 노드를 사이클로 다시 판명하여 중복되는 것을 막았다.

BOJ 3055

S, D, "*", ".", X로 이루어진 y, x 크기의 그래프가 주어진다. S와 D는 출발점과 도착점이고 "."은 빈 공간, X는 벽, "*"은 물이다. 물은 1초마다 상하좌우로 퍼지며 물이 퍼진 곳과 곧 퍼질 곳 (같은 초)에는 이동할 수 없다. S에서 D까지 가장 빨리 도착했을 때의 시간을 출력하는 문제. 그래프와 같은 크기의 물이 퍼지는 시간을 저장하며 기본 값을 XY값인 배열을 만들어 사용하였다. dfs 연산을 통해 물의 최단 이동시간을 저장하였다. 동일한 조건의 배열과 동일한 조건에 물이 퍼지는 시간보다 작을 때의 조건을 추가하여 S에서 이동하는 거리를 dfs 연산을 통해 저장하였다. 그 후 S에서 이동한 거리 중 D의 값이 XY일 때는 도착할 수 없음을, 아닐 시 해당 값을 출력하여 풀었다.

프로그래머스 N으로표현

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 반환하는 문제. 최솟값이 8보다 클 시 -1을 반환하기 때문에 1부터 7까지의 경우의 수만을 확인하였다. set 자료형을 이용하여 1부터 8까지 n이 이어붙어져 있는 수들로 이루어진 배열을 만들었다. 그 후 i에 대해서 1부터 7까지, j에 대해서 0부터 i까지 반복을 수행한다. i가 4일 시, 1로 만들 수 있는 수 + 3으로 만들 수 있는 수, 2 + 2, 3 + 1의 규칙을 이용하여 각 sets에 들어있는 요소들을 사칙연산한 후, 해당 sets에 들어있을 시 i를 반환, 반복 종료 시 -1을 반환하여 풀었다. 해당 게시물을 참고하였다.

프로그래머스 정수삼각형

정수로 이루어진 삼각형의 정보가 담긴 배열이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 반환하는 문제. 백준에서 비슷한 유형을 풀어보아 쉽게 풀었다. 첫 번째 접근은 백준에서 푼 것과 유사하게 삼각형을 직사각형 모양의 빈 곳은 0으로 이루어진 배열이 되도록 만들려고 했으나, 생각을 해보니 굳이 만들 필요가 없을 것 같아 주어진 배열을 이용하여 풀었다. y에 대해서 1부터 높이까지 반복을, x에 대해서 y+1까지 반복을 하였다. 높이에 따라 삼각형에 있는 정수의 수가 다르기 때문이다. x가 0이거나 y의 값과 같을 때 고려할 수가 하나이기 때문에 에외처리 하였으며, 다른 경우는 t[y][x] = max(t[y-1][x-1], t[y-1][x]) + t[y][x]의 점화식을 이용하였다. 배열의 마지막 값 중 제일 큰 것을 반환하여 풀었다

BOJ 1946

지원자의 서류, 면접 성적을 입력받는다. 다른 모든 지원자와 비교했을 때 두 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 이 때 뽑을 수 있는 신입사원의 최대 인원수를 출력하는 문제. 첫 번째 풀이는 첫 번째 성적을 통해 정렬 후, 두 번째 성적과 비교하여 순위가 높은 지원자일 때 재설정, 낮은 지원자일 때 정수형 변수의 크기를 늘려 탈락자의 수를 세어 풀었다. 두 번째 풀이는 첫 번째 성적의 순위를 인자로 배열에 넣어 정렬하는 과정을 없애도록 풀었다.

BOJ 2252

n명의 학생들을 키 순서대로 줄을 세울 때, 두 학생의 키를 비교하여 세울려고 한다. 일부 학생들의 키를 비교한 결과가 주어졌을 때 해당 결과를 출력하는 문제. 위상정렬을 이용하여 풀었다. 위상정렬이란 방향성을 가지는 그래프인 유향 그래프이자 사이클이 없는 그래프에서 사용할 수 있다. 진입차수 그리고 스택나 큐를 이용하여 구현할 수 있는데 해당 문제에서는 큐를 이용하여 구현하였다. 입력되는 비교 결과를 이용해 인접 리스트 형태의 그래프를 구현, 진입차수를 저장하였다. 진입차수가 0인 (제익 작은) 학생을 기준으로 q를 형성, popleft한 후 해당 학생보다 큰 학생들의 진입차수를 감소, 진입차수가 0이 되었을 때 q에 추가하여 풀었다.

BOJ 17845

공부할 수 있는 시간, 공부할 수 있는 과목의 수가 주어진다. 그 이후에 과목별로 과목의 중요도, 필요한 공부시간이 주어질 때 최대가 되는 중요도를 출력하는 문제. 배낭 형식의 문제로, k에 대해서 모든 과목을, time에 대해서 모든 시간을 반복하였다. 담을 수 없을 때 저번 반복에서 계산한 동일 시간의 최대치를, 담을 수 있을 때 저번 반복에서 계산한 동일 시간의 최대치와, 현재 중요도 + 저번 물건의 반복 값에서의 시간 - 현재 과목의 시간을 뺀 최대값을 더하여 풀었다.

BOJ 1766

숫자가 작을 수록 쉬운 N개의 문제와, 먼저 풀면 쉽게 풀 수 있는 관계 M개가 주어진다. 이 때 모든 문제를 풀어야 하며, 먼저 푸는 것이 좋은 문제가 있는 것은 반드시 먼저 푸는 것이 좋은 문제를 먼저 풀어야하며, 가능하면 쉬운 문제부터 풀어야되는 조건을 지켜 N개의 문제를 풀 순서를 출력하는 문제. 위상정렬 방법을 이용하여 풀었으며, 첫 번째 접근은 deque의 appendleft를 이용하여 선행 문제를 풀었을 때 후행 문제를 바로 풀도록 하였으나 WA를 받게 되었다. 그 후 heap 연산을 이용하여 heappop, heappush를 사용해 풀었다.

프로그래머스 단어변환

두 개의 단어 begin, target과 단어의 집합 words가 있다. 한 번에 한 개의 알파벳만 바꿀 수 있으며, words에 있는 단어로만 변환할 수 있는 조건이 있을 때, 최소 몇 단계의 과정을 거쳐 begin을 traget으로 변환할 수 있는지 반환하는 문제. 모든 단어에 대해서 값을 비교하여 한개만 다른 것들을 모아 놓은 인접리스트 그래프를 만들었다. 그 후 단계를 저장하는 dist 역시 딕셔너리 자료형을 이용했으며 해당 값을 비교하여 bfs 연산을 통해 값을 반환, 초기 설정된 값과 동일하거나 딕셔너리에 존재하지 않을 시 0을 반환하여 풀었다.

BOJ 1516

n개의 건물을 짓는다. 이 때 어떤 건물은 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 이 때 각 건물마다 짓는데 걸리는 최소시간을 출력하는 문제. deque를 사용한 위상정렬 방법을 이용해 풀었다. 진입차수를 줄이는 과정해서 현재 선수 건물과 현재 건물의 값을 더한 것과 저번 선수 건물과 더한 값 혹은 자신의 값을 비교해 큰 것을 할당하는 점화식 answer[next] = max(answer[next], answer[now] + times[next])을 사용하여 풀었다

BOJ 2565

두 개의 전봇대에 N개의 전깃줄이 있다. 각 전깃줄마다 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제. 첫번째 전봇대에 붙은 위치를 기준으로 정렬 후, 가장 긴 증가하는 부분 수열을 구하였다. 그리고 그 수를 n에 뺀 값을 출력하여 풀었다. 정렬하였기 때문에 증가하는 부분 수열이 겹치지 않는 전깃줄의 수이기 때문이다.

프로그래머스 주식가격

초 단위로 기록된 주식가격이 담긴 배열이 주어진다. 가격이 떨어지지 않은 기간은 몇 초인지를 반환하는 문제. deque를 이용해 popleft하여 남은 값들과 비교하여 풀었다.

프로그래머스 완주하지못한선수

마라톤에 참여한 사람의 이름, 완주한 사람의 이름으로 이루어진 두 배열이 주어질 때 완주하지 못한 사람을 반환하는 문제. 동명이인이 있는 경우가 있어 딕셔너리 자료형을 이용해 value 값을 정수형 변수로 저장, 동일 시 증가하였다. 완주자에 대해서 값을 1씩 뺀 후, 값이 1 이상인 key 값을 반환하여 풀었다. 다른 사람의 풀이를 참고하여 정답이 한명인 경우인 것을 이용, 두 배열을 정렬하여 다를 시 반환하는 방법으로도 풀었다.

프로그래머스 여행경로

주어진 항공권을 모두 이용하여 여행경로를 짤려고한다. 항공권 정보가 담긴 2차원 배열이 주어질 때, 방문하는 공항 경로를 배열에 담아 반환하는 문제. 첫 번째 풀이는 알파벳 순서대로 방문해야되는 조건을 이용해 heap 연산을 사용하여 풀었다. 결과는 테스트 케이스 4개중 두개를 맞췄으며, 반례는 출발지와 도착지가 같은 항공권이 여러개 있을 때 였다. 두 번째 풀이는 스택을 stack을 이용한 dfs로 풀었다. 스택의 가장 위 값을 기준으로 그래프에 존재하며, 남은 항공권이 있을 시, 스택에 추가. 아닐 시 방문정보를 저장하는 배열에 스택의 가장 위 값을 pop한 후, 뒤집어서 반환하여 풀었다.

프로그래머스 위장

옷의 정보를 담은 2차원 배열이 주어진다. 해당 배열은 옷의 이름, 종류로 이루어져 있다. 최소 한 개의 의상을 선택하는 서로 다른 옷의 조합의 수를 반환하는 문제. 같은 이름을 갖는 의상이 존재하지 않기 때문에 옷의 종류별로 딕셔너리를 이용하여 수를 세어 주었다. 그 후 옷 종류마다 +1 한 값을 계속 곱해주어 조합의 수를 찾은 후, 하나도 안입은 경우를 하나 뺀 값을 반환하여 풀었다.

프로그래머스 소수찾기

한자리 숫자가 적힌 종이 조각이 흩어져있다. 흩어진 종지 조각을 붙여 소수를 몇 개 만들 수 있는 지 반환하는 문제. 주어지는 종이 조각, 즉 문자열을 기준으로 백트래킹 방법을 이용해 모든 경우의 수들을 set 자료형을 이용해 중복없이 확인하였다. 그 중 제일 큰 수를 이용하여 에라토스테네스 체 방법을 이용해 해당 수 까지의 소수는 False로 저장되는 배열을 만들었다. set에 들어있는 수들이 소수일 때 정수형 변수 값을 늘려 풀었다.

프로그래머스 조이스틱

맨 처음 A로만 이루어진 문자열이 있다. 해당 문자열을 주어진 문자열로 바꿀 때, 다음 알파벳, 이전 알파벳, 커서 왼쪽으로 이동, 오른쪽으로 이동의 명령이 가능할 때 명령의 최솟값을 출력하는 문제. 첫 풀이는 모든 문자에 대해서 앞으로 이동했을 때와 뒤로 이동했을 때의 값을 비교해서 가장 작은 값을 할당하였다. 그 후에 왼쪽으로 한칸씩 이동하며 남은 칸의 수가 A로만 이루어져 있는 지를 확인해서 이동하는 값, 오른쪽으로 한칸씩 이동하며 이동한 값 중 작은 값을 더해 풀었다. 이렇게 풀었을 때 프로그래머스 상에서 마지막 반례만 틀렸습니다 결과가 나오게 되는데 "BBAAAAB"와 같은 왼쪽으로 가고 오른쪽으로 다시가야되는 경우가 반례인 것 같다. 다른 사람의 풀이를 참고해서 왼쪽, 오른쪽의 값이 0일 때까지 값을 더해서 더욱 작은 값으로 이동하여 위 반례를 해결하였다.

BOJ 20040

문제를 해석할 시 n개의 정점, m개의 간선이 있다. 해당 트리가 사이클이 되는 간선의 순서를 출력하는 문제. 분리집합을 이용하여 풀었다. 각 정점의 부모를 저장하는 배열을 n크기로 만들어 매 간선마다 부모 노드를 확인한 후, 부모 노드가 같을 시 해당 간선의 순서를 출력, 아닐 시 union하여 풀었다.

BOJ 13308

N개의 도시가 있고 양방향의 M개의 도로가 있다. 그리고 모든 도시들은 1리터의 기름당 가격을 갖는 주유소를 보유하고 있다. 도로의 길이 1만큼 1리터의 기름을 쓸 때, 최소 비용으로 1번 도시부터 N번 도시까지 이동할 때의 비용을 출력하는 문제. 첫 번째 풀이는 힙을 이용한 다익스트라 방식으로 다음 주유소가 현재 주유소보다 비쌀 때 다음 주유소의 가격을 현재 주유소 값으로 변환(미리 주유)하며. 방문했던 곳의 비용을 계산하여 방문을 하도록 연산을 하였더니, 싼 주유소를 방문해 왕창 주유하고 다시 돌아가는 경우가 반례였다. 두 번째 풀이는 최소 비용을 저장하는 배열을 2차원으로, [주유소 가격][도시들]로 구성하였다. 또한 힙에 지금까지 방문했던 주유소 가격중 제일 싼 곳을 저장하여 해당 주유소 가격의 배열과 비교하여 풀었다.

BOJ 1300

n, n 크기의 A 배열이 있다. A[i][j] = ixj 일 때, 해당 값을 일차원 배열에 넣었을 때 주어지는 수 k번 째 수를 구하는 문제. K번째 수는 K를 넘을 수 없기 때문에 1부터 k까지 이분탐색을 하여 풀었다. mid보다 작거나 같은 숫자들을 전부 찾아 수를 더해줌으로써 해당 수의 위치를 알 수 있다. 이분탐색의 방식은 알겠으나 어떤 문제를 어떻게 이분탐색을 적용시켜야되는 지가 너무 어렵다.

프로그래머스 등굣길

m, n 크기의 2차원 배열이 있다. 가장 왼쪽 위의 좌표를 1, 1로 나타내며 방문할 수 없는 물웅덩이가 있는 곳의 좌표들이 주어질 때 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 반환하는 문제. dp 방법으로 풀었으며 1, 1 좌표를 1로 만든 후, 물웅덩이는 배열에 -1로 저장한다. 그 후 반복문을 수행하며 시작 좌표일 때, 배열의 값이 -1일 때 0으로 바꾸고 컨티뉴하며 dp[y][x] = (dp[y-1][x] + dp[y][x-1]) % 1000000007다음 점화식을 수행하여 풀었다.

프로그래머스 더맵게

모든 음식의 스코빌 지수가 주어지고, 모든 음식의 스코빌 지수가 k 이상이 되게 하고 싶다. 이 때 가장 맵지 않은 음식 + 두 번째로 맵지 않은 음식 * 2를 하여 섞을 수 있을 때 몇 번 섞어야 모든 음식이 k 스코빌 이상인 지 반환하는 문제. heap 연산을 이용해 제일 첫 번째 요소와 k를 비교해서 반환하여 풀었다.

프로그래머스 가장먼노드

n개의 노드가 있는 그래프가 있다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 반환하는 문제. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다. INF와 heap을 이용하는 다익스트라 방법을 이용하여 풀었다. 인접리스트 방식으로 그래프를 저장한 후 다익스트라 연산을 통해 최단 거리를 저장, 최단 거리 중 최장 길이를 갖는 노드들을 센 후 반환하여 풀었다.

프로그래머스 입국심사

n명이 입국심사를 기다리고 있다. 입국 심사관이 한 사람을 심사하는 데 걸리는 시간이 주어질 때, 모든 인원이 심사를 받는 데 걸리는 최소 시간을 반환하는 문제. 1부터 가장 심사가 오래걸리는 사람 * 심사관의 수 + 1까지 이분탐색을 하였다. 이분탐색을 하며 mid와 모든 심사관들을 기준으로 몇 명을 심사할 수 있는 지 정한 후, n명 이상 심사를 할 수 있을 때 answer 변수를 mid 값으로 설정 후, end의 값을 mid - 1로 설정 후 재탐색하였다. n명을 심사할 수 없는 겨우 start 값을 mid + 1하여 재탐색하도록 풀었다.

프로그래머스 카펫

문제의 그림과 같은 격자 모양 카펫이 있을 때, 갈색과 노란색의 수를 통해 전체 카펫의 크기를 반환하는 문제. 가로 크기에 대해서 갈색과 노란색을 합한 수부터 3까지 반복을 한다. 전체수에 가로 크기를 나눈 값이 세로가 되며, 주어진 노란색 타일의 수와 (x-2)*(y-2)값을 비교하여 맞을 시 [x, y]를 반환하여 풀었다.

프로그래머스 쿼드압축후개수세기

0과 1로 이루어진 2의 n승 크기의 2차원 배열이 있다. 이 때 쿼드 트리와 같은 방식으로 압축할 때, 0과 1의 수를 반환하는 문제. 시작 y, x 좌표와 크기를 갖는 함수를 재귀적으로 사용하여 풀었다. 크기가 1일 때는 해당 좌표의 값에 따라 추가, 아닐 시 첫 번째 값과 해당 크기의 모든 요소와 비교하여 모두 같을 시 값에 따라 CBR 형식으로 값을 바꿈, 하나라도 다를 시 사이즈를 반으로 줄여 재귀적으로 탐색하여 풀었다.

BOJ 12738

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제. 기존 dp 방법을 이용하여 구하는 것이 아닌, 이분탐색을 사용하여 풀었다. 모든 수에 대해서 dp 배열의 마지막 값과 비교하여 클 시 추가하고 아닐 시 이분탐색을 이용해 가장 인접한 수와 바꿔주어 풀었다.

BOJ 17352

N개의 섬이 있고 모든 섬들을 잇는 n-1개의 다리가 있다. 어느날 다리 하나가 무너졌을 때, 모든 섬들을 이을 수 있는 다리의 시작 섬과 끝 섬을 출력하는 문제. 정답은 여러개이며 그 중 하나만 출력해도 된다. 유니온 파인드 방법으로 풀었으며 입력되는 다리들을 기준으로 union하였다. 그 후 첫 번째 섬의 부모 노드와 2부터 N번째 섬의 부모 노드를 비교해 다를 때 1과 해당 섬의 번호를 출력한 후 종료하여 풀었다.

BOJ 14003

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)를 구하는 문제. 해당 LIS의 길이와 수열을 공백으로 나누어 출력하는 문제. 이분탐색을 이용하여 LIS의 길이를 저장했으며 배열에 각 인덱스의 LIS를 저장하여 해당 값을 비교, 감소하여 수열의 구성요소를 판별하여 풀었다. 자세한 풀이는 주석 참고

BOJ 7578

기계의 식별번호로 이루어진 두 열을 입력받는다. 해당 식별번호로 케이블을 연결할 때 서로 교차하는 케이블 쌍의 개수를 출력하는 문제. 첫 번쨰 생각은 정렬 후에 LIS를 구할까 했으나, 최대 500,000개의 기계가 입력되며 시간 제한이 1초라 불가할 것으로 판단하였다. 세그먼트 트리를 이용하여 해당 인덱스밖의 연결 객체를 합하여 풀었다. 두 번째 기계열을 딕셔너리 자료형으로 key는 식별번호, value를 인덱스 번호로 저장하였으며, l1의 식별번호에 대하여 반복문을 수행하며 query, update 연산을 하여 풀었다. 자세한 풀이는 해당 게시물 참조

BOJ 1759

l개의 문자중에서, c개의 문자열로 이루어진 암호를 만드는 문제. 해당 문자열은 알파벳이 오름차순이 되어야하며, 1개 이상의 모음, 2개 이상의 자음으로 이루어져 있어야하는 조건이 있다. 백트래킹 방식을 이용하여 모든 알파벳이 중복되지 않으며 오름차순으로 담길 수 있도록 하였다. 길이가 c가 될 시 모음과 자음의 수를 세는 함수를 만들어 통과할 시 출력하도록 풀었다.

BOJ 1092

항구에 각 옮길 수 있는 최대 무게가 있는 N개의 크레인, 각 무게가 있는 M개의 화물이 있다. 이 때 최소 시간으로 모든 박스를 옮겼을 때의 시간을 출력하는 문제. 첫 번째 풀이는 크레인 중 제일 작은 값과 리스트를 슬라이싱하여 비교하였으나, 작은 것부터 계산할 시에 3 6 8, 1 2 3 4 5 6 7 8 9와 같은 반례에 통과하지 못하였다. 두 번째 풀이는 옮길 수 있는 화물 중 제일 무거운 것부터 del 메소드를 이용하여 풀었다. 간단하지만 생각보다 긴 시간을 소비하였다.

BOJ 4949

영문 알파벳, 공백, 소괄호, 대괄호, 온점으로 이루어진 문자열을 입력받는다. 해당 문자열이 소괄호, 대괄호에 대해서 균형을 이루고 있으면 "yes"를, 아닐 시 "no"를 출력하는 문제. 스택을 이용하여 풀었으며 괄호를 여는 문자일 시 스택에 추가, 닫는 문자일 시 스택의 마지막 값과 비교하여 pop하거나 break하여 풀었다. 소괄호 대괄호를 비교하는 데 딕셔너리 자료형을 이용하였으며 반복문이 종료시에도 스택에 괄호가 남아있는 경우도 예외처리하여 풀었다.

BOJ 11054

n개의 정수로 이루어진 수열 s를 입력받는다. 그 후 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 문제. 가장 긴 증가하는 부분 수열의 길이를 저장한 배열과 가장 긴 감소하는 부분 수열의 길이를 저장한 배열을 비교하여 풀었다.

BOJ 2243

몇 번째로 맛있는 사탕을 pop, 사탕을 상자에서 넣고 뺌을 구현하는 문제. 세그먼트 트리를 이용하여 개수를 업데이트, 몇 번째 맛인 지를 확인하는 쿼리를 이용하여 상자를 조작할 때는 업데이트를 이용하여, 몇 번째 사탕을 꺼낼 때는 인덱스를 참고하여 출력하고, -1 diff로 업데이트하여 풀었다.

BOJ 1005

N개의 건물과 건설 순서 규칙 K가 주어진다. 이때 건물 번호 X가 건설 완료되는 최소시간을 출력하는 문제. deque와 위상 정렬을 사용하여 풀었다. 진압차수를 줄인 후 반복중인 건물의 최소 시간을 저장하는 answers 배열에 answers[next] = max(answers[next], answers[now] + answers[next])의 점화식을 이용하여 풀었다.

BOJ 11066

N개의 파일이 있을 때 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용 중 최소 총합을 계산하는 문제. 크누스(knuth) 알고리즘을 이용하여 풀었다곤 하지만 아직 정확하게 이해하지 못했다. 누적합을 계산하여 연산에 이용, dp[2][4]는 dp[2][3] + sizes[4], dp[3][4] + sizes[2] 중 작은 것을 할당하는 점화식이 이용돼었다. 아직 너무 부족하다.

BOJ 14284

정점 N개, 두 노드, 가중치를 갖는 무방향 간선 M개가 있을 때, S부터 E까지 도달하는 최소 가중치를 출력하는 전형적인 다익스트라 문제. heap을 사용한 다익스트라를 이용하여 풀었다.

BOJ 1806

길이가 N인 수열이 주어진다. 수열에서 연속된 부분합 중 그 합이 S 이상이 되는 것 중, 가장 짧은 길이를 출력하는 문제. 최대 길이를 INF로 저장한 후, 왼쪽과 오른쪽 인덱스 값을 이용하여 부분합을 계산, 비교하여 인덱스 값을 조정하는 두 포인터 방법을 이용하였다. 최소 길이가 반복문이 종료 시에도 INF일 시, 모두 더하여도 S 이상이 되지 않은 것이여서 0을 출력, 아닐 시 해당 값을 출력하여 풀었다. 자세한 풀이는 주석 참조

BOJ 11375

N명의 있고 M개의 해야할 일이 있으며 직원은 1번부터 N번까지, 일은 1번부터 M번까지 번호가 매겨 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는 지 구하는 문제. 이분매칭 문제이다. 해당 게시물을 통해 공부했으며, 작성 난이도는 어렵지 않았지만 깊은 이해까지는 시간이 걸릴 것 같다. 언제나 처럼 반복숙달 해야겠다.

BOJ 2188

N마리의 소, M개의 축사가 있는 이분매칭 문제, 11375번 문제와 동일한 구성이여서 반복숙달겸 풀었다.

BOJ 4101

0 0이 입력될 때까지 두 수를 비교한 결과를 출력하는 문제, 카카오 인턴 코딩 테스트전에 간단히 풀어보았는데 약 이주동안 안풀었다고 어렵게 느껴진다.

BOJ 4153

3가지 정수를 입력받은 후 해당 길이로 이루어진 삼각형일 때, 직각 삼각형인 지 출력하는 문제. 세 수를 제곱한 값과 비교하여 풀었다.

BOJ 11444

최대 10경 번째 피보나치 수를 구하는 문제. 첫 번째 풀이는 두 개의 변수에 값을 할당하는 방식으로 풀었으나 당연하게도 시간초과 결과를 받게 되었다. 검색하여 알아본 결과 매우 매우 큰 수의 피보나치를 빠르게 구하는 방법은 행렬의 거듭제곱을 사용한다고 한다. 위 링크의 게시물을 참고하여 풀었으나 아직 많이 부족하다.