CodeDrive

문제:

풀이방법:

 내가 말해야 하는 단어까지만 알면 되므로 0부터 n진수로 변환을 하면서 digits에 더하고 digits의 길이가 t*m보다 커지면 그만 변환하도록 하면 된다.

 digits를 다 구했다면 내가 말해야 하는 위치의 인덱스 값을 answer에 더해서 반환하도록 한다.

https://programmers.co.kr/learn/courses/30/lessons/17687

문제:

풀이방법:

우선 파일명을 HEAD, NUMBER, TAIL로 정리를 해야한다. 이를 위해서 isdigit이라는 숫자인지 확인하는 함수를 사용한다.

 처음 isdigit이 참이 되는 순간 이전까지의 글자가 HEAD가 되므로 isdigit이 참이 되는 순간 parser에 값을 추가하고 break를 걸어서 반복문을 나온다. 

 해당 위치부터 다시 반복문을 사용해서 이번에는 isdigit이 거짓이 되는 순간이 NUMBER의 끝이므로 parser에 값을 추가하고 break를 걸어서 반복문을 나온다.

 이제 남은 부분은 TAIL에 해당하므로 parser에 추가해주면 되지만 TAIL이 아무것도 없을 경우에는 위 NUMBER를 파악하는 과정에서 맨 마지막 숫자가 추가되지 못했을 것이다. 따라서 해당 인덱스에 isdigit을 사용해서 참이면 TAIL이 없는 경우, 거짓이면 TAIL이 있는 경우를 의미한다.

 이제 파일명을 HEAD, NUMBER, TAIL로 나눴으므로 sort의 key를 사용해서 정렬을 하도록 한다. 우선 HEAD를 기준으로 사전 순 정렬을 하고, 대소문자 구별을 하지 않는다. 그리고 HEAD가 동일하다면 NUMBER가 작은순으로 정렬을 하는데 스트링 상태가 아닌 int 상태로 변환해서 정렬을 해야 한다. 따라서 sort의 key는 (x[0].upper(), int(x[1])) 이 된다. 이처럼 해야지 원래 파일명을 보존하면서 정렬을 할 수 있다.

 정렬을 완료했으므로 이를 다시 붙여서 출력을 해야 한다. TAIL이 있는 경우에는 parser에 2번째 인덱스가 존재하지만 없다면 1까지만 존재한다. 따라서 이를 try~ except ~ 예외처리 구문을 사용해서 추가하도록 한다.

https://programmers.co.kr/learn/courses/30/lessons/17686

문제:

풀이방법:

LZW 압축 과정대로 코드를 작성하면 된다.

 우선 길이가 1인 모든 단어를 포함해서 사전을 구축해야 하므로 dictionary에 밑과 같이 구축한다. 그 뒤에 idx가 입력으로 들어온 문자열의 길이와 같아질 때까지 반복해서 확인하고 추가하는 작업을 한다.

 LZW 압축과정은 다음과 같이 작동된다.

1. KAKAO의 경우에 KAKAO와 인덱스 0 그리고 사전이 check로 입력된다.

2. 이를 뒤에서부터 비교를 한다. 즉 KAKAO가 사전에 있는가? -> KAKA가 사전에 있는가? -> .... 순으로 진행이 되고 K가 사전에 있는가에서 참이므로 break를 걸고 반복문 밖으로 나온다.

3. 그러면 KA는 사전에 없는 단어였으므로 사전에 추가하고 인덱스와 사전을 반환한다.

4. check에서 나온 인덱스와 check에 넣기 전에 사용한 인덱스를 사용해서 슬라이싱을 하고 이를 사전의 색인 번호를 answer에 추가한다.

5. idx를 i로 지정한다.

 idx가 msg와 동일할 떄까지 진행을 하면 압축과정이 끝나게 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17684

문제:

풀이방법:

 이 문제에서 처리해야 할 것은 크게 두 가지이다. 재생된 시간의 길이에 따라서 음이 달라지므로 시간 형식으로 되어 있는 자료형을 분 단위로 바꿔야 한다. 그리고 음계 중에 C#, D#, F#, G#과 같이 #이 붙어 있는 음계가 있는데 스트링 형식으로 되어 있기 때문에 이들도 하나의 인덱스를 차지하고 있으므로 처리하는 방법에 대해서 생각해야 한다.

 우선 분으로 바꾸기 위해서 :를 기준으로 분할을 한다. 시작하는 분과 끝나는 분을 비교해서 음악의 총 재생된 시간을 구하도록 한다.

 C#과 같이 #이 달려있는 음들은 하나의 인덱스로 처리를 하는 것이 편하므로 소문자로 변경하도록 한다. (C#->c , D# ->d , ....) 이 작업을 하고 위에서 구한 재생된 시간으로 실제 재생된 멜로디를 구할 수 있고, 이 안에 m이 있는지 판단하여서 answers 리스트에 담도록 한다. 

 이 때 조건이 일치하는 음악이 여러 개일 경우에는 재생된 시간이 제일 긴 음악, 먼저 입력된 음악 제목 순으로 정렬해야 하므로 (재생된 시간, 입력된 인덱스,음악제목)과 같이 answers에 넣도록 한다.

 일치하는 음악을 모두 담았다면 sort의 key를 이용해서 위 조건에 맞게 정렬을 하도록 한다. 재생된 시간은 길수록 앞으로 와야 하므로 음수를 붙여주고, 먼저 입력된 것이 앞으로 와야 하므로 이는 양수로 정렬하도록 한다. 이렇게 정렬을 하고 난 뒤에 answers에 가장 앞에 있는 값의 맨 마지막 값을 출력한다면 그것이 음악제목일 것이다. (만약 answers가 비어 있다면 "(None)"을 출력해야 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17683

문제:

풀이방법:

진행되는 단계를 보면 재귀적으로 수행한다고 했으므로 재귀로 구성하는 것이 맞다.

전체적인 진행은 make라는 함수에서 된다. 

1, 2는 split()이라는 함수에서 진행된다. 2는 균형잡힌 문자열으로만 분리하면 되므로 ( 면 +1을 ) 면- 1을 해서 균형잡힌 문자열으로 분리를 한다.

 이렇게 분리를 한 뒤에 u가 올바른 괄호 문자열인지 확인해야 한다.(3) 이 작업은 check라는 함수에서 진행된다. split과 비슷하게 작동을 하지만 count가 음수로 내려간다면 올바른 괄호 문자열이 아니기 때문에 이 경우에 False를 반환하고 나머지는 True를 반환하도록 한다. 그리고 이를 문자열에 붙이고 v에 대해서 1을 다시 진행하도록 make(v)를 수행한다.만약 u가 올바른 괄호 문자열이 아니라면 수행하라는 작업을 그대로 수행하면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/60058

문제:

풀이방법:

 처음에는 스택으로 구축할까 생각하다가 많이 복잡할 것 같아서 슬라이싱을 활용한 문자열 비교로 해결하기로 하였다. 

문자열의 길이가 1이면 항상 답은 1이라는 예외처리로 시작한다. 몇 개 단위로 자르는 것이 가장 짧은 방법인지 알지 못하므로 1부터 len(s)까지 분할 하도록 한다. i개의 단어로 자르면서 앞과 현재가 같다면 count를 하나올려주도록 한다. 만약 다르다면 count를 비교해보도록 한다. count가 1이라면 그냥 문자열에 더하고, 1이 아니라면 숫자를 같이 더해주도록 한다.

 이렇게 각 길이의 단위로 자른 문자열을 모두 담았다면 가장 작은 값을 반환하도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/60057

문제:

평면상에 n개의 점이 있다. 이 점들 중에 서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 n(1<=n<=100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

출력:

첫째 줄에 답을 출력한다.

풀이방법:

 x좌표가 일치하는 두 점들이나 y좌표가 일치하는 두 점들이 축과 평행을 이루기 때문에 정렬을 통해서 쉽게 찾을 수 있을 것 같았다. 하지만 문제 이해를 잘못해서 처음에 조금 헤매었고, 질문에 있는 글을 보면서 겨우 이해했다.

 '만약 입력에 서로 같은 두 점이 주어지면, 그 두점을 이용하여 직선을 만들 수 있다.' 라는 문구때문에 많이 헷갈렸다. 처음에는 (0,0)_1 (0,0)_2 (0,10) 이렇게 있으면 (0,0)_1, (0,0)_2을 (0,0)_1, (0,10)을 (0,0)_2, (0,10)을 연결할 수 있어서 3개라고 생각했지만 아니였다.

 문제에서 원하는 것은 위와 같은 경우에는 (0,0)_1 (0,0)_2의 두 점을 통해 x=0, y=0이라는 두 직선을 만들 수 있었고, (0,0)_1, (0,10)을 (0,0)_2, (0,10) 이것들은 x=0인 직선에 포함되는 것이므로 카운트를 하지 않는다는 것이였다. 그래서 답은 2가 되는 것이였다.

 그래서 x축과 평행하게 만들 수 있는 직선의 숫자값, y축과 평행하게 만들 수 있는 직선의 숫자값을 각각 담는 배열을 만들어서 그 길이를 더하도록 했다.

하지만 매우 비효율적으로 구성했기 때문에 시간초과가 발생하였고 PyPy3로 통과할 수 있었다.

문제링크:

https://www.acmicpc.net/problem/2358

지금까지 풀었던 문제들을 GIT에 정리하기 시작했다. 많은 양이라 한 번에 다 업로드 하지는 못하고 있지만 차근차근 하나씩 다 올릴 예정이다. 문제는 1000번 단위로 정리하고 있으며 업로드 되어 있는 목록은 다음과 같다.

[2019-11-12] 현재는 1000~2999번까지 업로드

• 1000~2000

  • 1002 터렛
  • 1003 피보나치 함수
  • 1009 분산처리
  • 1011 Fly me to the Alpha Centauri
  • 1015 수열 정렬
  • 1016 제곱 ㄴㄴ수
  • 1018 체스판 다시 칠하기
  • 1037 약수
  • 1049 기타줄
  • 1065 한수
  • 1075 나누기
  • 1076 저항
  • 1080 행렬
  • 1110 더하기 사이클
  • 1120 문자열
  • 1149 RGB거리
  • 1152 단어의 개수
  • 1157 단어 공부
  • 1159 농구 경기
  • 1181 단어 정렬
  • 1260 DFS와 BFS
  • 1309 동물원
  • 1325 효율적인 해킹
  • 1357 뒤집힌 덧셈
  • 1371 가장 많은 글자
  • 1373 2진수 8진수
  • 1389 케빈 베이컨의 6단계 법칙
  • 1406 에디터
  • 1436 영화감독 숌
  • 1475 방번호
  • 1476 날짜 계산
  • 1495 기타리스트
  • 1547 공
  • 1561 놀이공원
  • 1629 곱셈
  • 1654 랜선 자르기
  • 1655 가운데를 말해요
  • 1676 팩토리얼 0의 개수
  • 1697 숨바꼭질
  • 1699 제곱수의 합
  • 1712 손익분기점
  • 1744 수 묶기
  • 1759 암호 만들기
  • 1789 수들의 합
  • 1834 나머지와 몫이 같은 수
  • 1874 스택 수열
  • 1890 점프
  • 1904 01타일
  • 1912 연속합
  • 1920 수 찾기
  • 1927 최소힙
  • 1929 소수 구하기
  • 1931 회의실 배정
  • 1977 완전 제곱수
  • 1987 알파벳

• 2001~3000

  • 2004 조합 0의 개수
  • 2011 암호코드
  • 2022 사다리
  • 2075 N번째 큰 수
  • 2133 타일 채우기
  • 2156 포도주 시식
  • 2163 초콜릿 자르기
  • 2178 미로찾기
  • 2193 이친수
  • 2217 로프
  • 2225 합분해
  • 2231 분해합
  • 2292 벌집
  • 2309 일곱 난쟁이
  • 2312 수 복원하기
  • 2331 반복 수열
  • 2407 조합
  • 2504 괄호의 값
  • 2606 바이러스
  • 2667 단지번호 붙이기
  • 2775 부녀회장이 될테야
  • 2805 나무 자르기
  • 2839 설탕 배달
  • 2851 슈퍼 마리오
  • 2869 달팽이는 올라가고 싶다.
  • 2875 대회 or 인턴
  • 2941 크로아티아 알파벳
  • 2960 에라토스테네스의 체

• 3001~4000

  • 3036 링
  • 3053 택시 기하학

• 4001~5000

  • 4307 개미
  • 4344 평균은 넘겠지
  • 4948 베르트랑 공준
  • 4949 균형잡힌 세상

• 5001~6000

  • 5430 AC
  • 5567 결혼식

• 6001~7000

  • 6064 카잉 달력
  • 6591 이항 쇼다운

• 7001~8000

  • 7568 덩치
  • 7576 토마토
  • 7569 토마토

• 8001~9000

  • 8979 올림픽

• 9001~10000

  • 9012 괄호
  • 9095 1,2,3 더하기
  • 9461 파도반 수열
  • 9465 스티커
  • 9613 GCD 합
  • 9933 민균이의 비밀번호
  • 9935 문자열 폭발

• 10001~11000

  • 10250 ACM 호텔
  • 10253 헨리
  • 10451 순열 사이클
  • 10610 30
  • 10816 숫자 카드2
  • 10825 국영수
  • 10828 스택
  • 10844 쉬운 계단 수

• 11001~

  • 11047 동전0
  • 11050 이항계수1
  • 11051 이항계수2
  • 11053 가장 긴 증가하는 부분 수열
  • 11057 오르막 수
  • 11052 카드 구매하기
  • 11279 최대힙
  • 11286 절대값 힙
  • 11718 그래도 출력하기
  • 11816 조세퍼스 문제0
  • 14501 퇴사
  • 14889 스타트와 링크
  • 15649 N과 M
  • 17144 미세먼지 안녕!

https://github.com/kimkyeonghun/BOJ

문제:

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 잇따. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력:

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

풀이방법:

 기본적으로는 dfs를 사용해서 판다의 이동 경로를 알아야 하지만 문제에서 원하는 것은 판다가 최대한 살 수 있는 일수, 즉 최대로 이동 가능한 거리의 길이를 원하고 있다. 작은 크기의 경우에는 시작점을 달리 해서 최대 일수를 찾을 수 있지만 500 x 500의 경우에는 이 것을 다 탐색하기에는 많은 시간이 걸릴 것이다.

 따라서 이를 해결하기 위해서 다이나믹 프로그래밍에서 메모리제이션을 사용한다. 한 점에서 출발을 해서 움직이다가 이미 이전에 다른 곳에서 움직였던 기록이 남아있고 그것을 기록해뒀다면 더 이상 그 길로 이동할 필요없이 그 값을 참조해서 다시 돌아오면 된다. 따라서 dfs로 이동을 하지만 이전에 이 길을 지나간 기록이 있다면 그 값을 가져오고, 그렇지 않다면 더 들어가면서 값을 기록하도록 한다.

 또한 재귀적으로 함수를 구현했기 때문에 깊은 재귀로 인한 에러를 방지하기 위해서 sys.setrecursionlimit를 사용한다.

문제링크:

https://www.acmicpc.net/problem/1937

문제:

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받는 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2,4,6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있으면 연다. k번째 라운드에서는 번호가 k인 배수인 방이 열려 있으면 잠그고, 잠겨 있으면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

입력:

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5<=n<=100)이 주어진다.

출력:

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

풀이방법:

다이나믹 프로그래밍으로 풀어야 한다고 하는데 방의 개수가 100으로 작은편이기 때문에 완전탐색을 사용해서 풀었다.

0이면 열려 있고, 1이면 닫혀 있다고 했을 때, 해당하는 숫자 j의 배수마다 0이면 1로, 1이면 0으로 바꾸도록 했다. 이렇게 모두 탐색을 완료하면 0의 갯수에서 하나를 빼서 답을 구한다.

(다 풀고나니 1을 열려 있고, 0을 닫혀 있다 가정하고, 마지막에 sum을 하는 것이 더 깔끔할 것 같다.)

문제링크:

https://www.acmicpc.net/problem/6359