CodeDrive

문제:

풀이방법:

아이디에 따른 명령어와 이름을 해시 방식으로 저장을 해줌으로써 데이터를 관리하였다. 이름을 바꾸는 경우에는 맨마지막에 해당하는 이름으로 모두 반영이 되므로 Change가 나올 때마다 덮어주는 방식으로 진행하였다. 이 외에는 명령어에 따라서 알맞게 출력해주면 된다.

문제링크:

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

문제:

풀이방법:

이진수로 바꾸는 것이 가장 중요한 문제이다. 이진수로 바꾸는 것은 python의 bin을 사용하면 바꿀수 있다. 이 때 bin을 사용하면 앞에 이진수임을 나타내는 값이 붙어 있으므로 이를 떼어서 저장하는 것이 필요하다. 그리고 이를 한 변의 크기와 동일하게 만드는 것이 중요하다. 위 문제의 예시처럼 1은 1이지만 한변의 길이가 5이므로 00001로 맞춰준 것을 알 수 있다. 길이가 동일해야 해독할 수 있으므로 이 작업이 가장 중요하다. 길이를 같게 만들었다면 이제는 단순히 반복문을 사용해서 값을 비교하고 상황에 따라 "#"과 공백을 더해주면 된다.

문제링크:

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

문제:

풀이방법:

조건에 주어진 LRU(Least Recently Used)를 사용하면 풀 수 있는 문제이다. LRU 캐시 교체 알고리즘이란 가장 오래전에 사용한 캐시는 자주 사용하지 않는다고 판단하고 새로 들어오는 캐시에게 자리를 내어준다는 알고리즘이다. 즉, 가장 오래전에 사용된 캐시를 빼버리고 새로운 값을 넣어버리면 된다. python의 list 내장 함수를 사용하면 어렵지 않게 풀 수 있다. list는 새로운 값을 넣어버리면 list의 맨 끝에 값을 넣기 때문에 자동적으로 인덱스 0번째에 있는 값이 오래된 값이다. 따라서 캐시에 없는 값이 들어오면 0번째 값을 빼고 새로운 값을 넣으면 LRU를 만족할 것이다. 그리고 만약 이미 있는 값이 들어왔다고 하더라도 remove로 값을 제거하고 새로 값을 넣어주어야 한다. 그래야 이 값의 사용시간이 최신화되기 때문이다. 각 행위마다 5초(miss)와 1초(hit)를 더한다면 답을 얻을 수 있을 것이다.

문제링크:

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

문제:

풀이방법:

 입력으로 들어오는 값들을 다중집합으로 만들어야 한다. 소문자와 대문자의 구분이 필요 없으므로 소문자로 전부 바꾸고 두개씩 끊어가면서 특수문자가 있는지 파악하고 각 배열에 담는다. 

 summation이라는 두 배열의 길이의 합을 구하고 이를 교집합과 뺌으로써 합집합의 크기를 구할 것이다. summation은 공통된 원소를 두 개씩 가지고 있는 것이기 때문이다. 

 반복문을 사용해서 공통된 원소가 있을 때마다 intersect를 하나씩 증가시킨다.

이 두 변수로 자카드 유사도는 다음과 같이 구한다. int(intersect/(summation-intersect)*65536) 이 값을 구하면 답을 얻을 수 있다.

문제링크:

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

문제:

세로 R칸,가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸(1행 1열)에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20)둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이방법:

제일 많이 파고 들어가야 하는 문제이므로 DFS와 백트래킹을 사용하는 것이 적합하다. DFS를 사용해서 한 번 깊게 파고 난 뒤에 움직이지 못하는 경우가 된다면 다시 되돌아와서 다른 곳으로 깊게 파고 들어가도록 한다. 이때부터는 최대로 깊게 들어간 기록이 있으므로 이 기록을 넘길 때에만 값을 갱신하도록 하였다. 이렇게 모두 탐색을 마치고 더 이상 이동할 곳이 없다면 출력하도록 했다.

문제링크:

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

문제:

 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 두 정수 L, C가 주어진다. (3<=L<=C<=15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력:

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

풀이 방법:

 재귀적인 방법으로 암호를 만들고, 이 암호가 옳은 암호인지 판단하는 check라는 함수를 만들었다. 암호를 만들다가 길이가 L이 된다면 check로 옳은 암호인지 판단을 하고 맞다면 출력, 아니면 끝내도록 했다.

문제링크:

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

문제:

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Ski이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1,2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

•  스타트 팀: S12+S21 = 1+ 4 = 5
•  링크 팀: S34 + S43 = 2 + 5 = 7

1,3 번이 스타팀, 2,4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

•  스타트 팀: S13+S31 = 2+ 7 = 9
•  링크 팀: S24 + S42 = 6 + 4 = 10

 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1,4번이 스타트 팀, 2,3 번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6의 되어서 차이가 0이 되고 이 값이 최소이다.

입력:

첫째 줄에 N(4<=N<=20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

풀이 방법:

 N은 최대 20이므로 나올 수 있는 조합의 경우의 수는 20C10이다. 이 정도의 수를 반복하는 것은 충분히 가능하기 때문에 브루트포스로 풀어도 상관없을 것 같았다. 

 우선 python의 itertools를 사용해서 나올 수 있는 조합을 만들었다. 그리고 set을 사용해서 스타트팀과 링크 팀으로 구분을 했고, 스타트팀과 링크 팀을 이중 반복문을 통해서 시너지의 합을 구했다. 그리고 시너지간의 차를 배열에 담았다.위 작업을 모두 마치고 나서 배열의 min을 출력하도록 하였다.

문제 링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N()<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이 방법:

 여러 행위를 할 수 있는데 가장 빠른 방법을 찾는 문제는 대부분 BFS로 풀리는 경우가 많다. 따라서 이 문제도 X-1, X+1, 2X로 이동할 수 있는데 가장 빠른 시간을 찾기 때문에 BFS로 풀어야 한다.

 한 layer마다 Queue의 값에 따라 이동할 수 있는 위치를 새로 queue에 넣는다. 이 과정을 반복하다가 원하는 위치로 이동했다면(dist[k]의 값이 갱신 되었다면) queue를 종료하도록 해서 답을 출력하도록 했다.

문제 링크:

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

문제:

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?

입력:

첫째 줄에 차례대로 x,y,c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다.

출력:

두 빌딩사이에 너비가 되는 수치를 출력한다. 절대/상대 오차는 10^-3까지 허용한다.

풀이방법:

 이분 탐색을 기반으로 하지만 수학적인 내용이 더 많이 들어가는 문제인 것 같다. 문제의 기본 틀은 두 빌딩 사이의 거리를 d라고 했을 때, 이를 이분 탐색으로 값을 바꾸어 간다. 임의의 d에 따라서 사다리가 교차하는 높이 h가 달라질 것이다. 따라서 이분탐색을 통해서 그 중 c와 같아지는 d를 찾도록 한다.

 임의의 d에 따라서 h를 구하는 방법은 수학의 닮음을 사용하도록 해야 한다. 사다리가 교차하는 높이를 h라 하고 선을 다음과 같이 그리면 닮음 꼴인 직각 삼각형을 얻을 수 있다.

h라는 직선이 생김에 따라 d도 d1과 d2로 나뉘게 될 것이고, h1과 h2도 다음과 같이 정의를 할 수 있을 것이다.

그러면 빗변이 x인 삼각형과 y인 삼각형에 각각 다음과 같은 닮음비를 얻을 수 있다.

 우리가 최종적으로 원하는 변수는 h이기 때문에 h=( ~ ) 와 같은 형태로 변형시켜야 할 것이다. 그러기 위해서는 d1+d2 = d임을 알고 있기 때문에 이를 활용해서 변수를 줄이도록 하자.

그러기 위해서는 일단 닮음비를 정리해서 d1과 d2에 관한 식으로 만들었다. 그리고 난 뒤에 위 두 식을 더한다면 d1과 d2를 d로 바꿀 수 있게 될 것이다.

 이제 양변을 각각 d로 나눌 수 있을 것이다. d는 두 빌딩 사이의 거리이므로 0을 초과한 거리일 것이다. 따라서 양변을 나누는 것에 문제가 없다.

 그러면 위 그림의 제일 위의 식과 같이 얻을 수 있을 것이고 좌변을 h에 대해서 묶을 수 있게 될 것이다. 좌변을 h로 묶고 난 뒤에 남은 것들을 우변으로 넘겨준다면 이를 h에 대한 식으로 만들 수 있을 것 이다. 따라서 위 그림의 두번째와 세번째 식은 그 과정을 담고 있다.

 h1과 h2는 x, y, d로 이루어진 변수이기 때문에 정확한 값을 계산할 수 있다. (d는 이분 탐색으로 정해진 값이다.) 따라서 h의 값을 구할 수 있을 것이고 이를 c와 비교하면서 c에 근접하게 d를 이분탐색으로 찾을 수 있을 것이다.

그렇게 찾은 mid값을 소숫점 셋째 자리까지 반올림해서 출력하도록 한다.

문제링크:

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

문제:

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=2,000,000,000)과 M(1<=M<=10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력:

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

풀이 방법:

이분 탐색을 사용해서 풀어야 하는 문제이다. 항상 이러한 이분 탐색을 사용해서 푸는 문제들은 찍어서 최적의 값을 맞춰나간다 라는 느낌이 강하다. 따라서 이 문제도 역시 일정 값을 찍어서 근처로 구하고 그 값으로 부터 놀이기구의 번호를 찾도록 하였다.

문제링크:

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