투투

programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 접근 끝말잇기를 하면서 탈락하는 조건을 그대로 구현을 하였다. 이 문제에서는 탈락한 사람과 탈락한 ..

programmers.co.kr/learn/courses/30/lessons/49993# 코딩테스트 연습 - 스킬트리 programmers.co.kr 접근 처음에 중복된 스킬은 주어지지 않는다는 것을 스킬 트리가 담겨있는 리스트 내에 중복된 스킬 트리가 없다는 것을 이해를 했다. 하지만 하나의 스킬 트리 내에 중복된 스킬이 없는 것이었다. 그래서 단순히 skill의 앞에서부터 비교하여 조건에 부합하는 스킬트리가 있는지 판단하였다. 구현 먼저 skill_trees를 탐색하면서 각각의 skill_tree를 검사한다. 스킬의 순서가 담겨있는 skill을 리스트형으로 변환하고 skill_tree를 탐색하면서 skill의 앞과 같은지 확인한다. 다르다면 break가 될 것이며 같다면 앞의 원소가 제거되어 다음 비..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 접근 1번부터 N번까지 큐에 넣고 큐가 빌 때까지 다음을 반복한..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 M..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 처음에는 단순하게 리스트에 N개의 수를 넣고 또 다른 리스트에 M개의 수를 넣어 for문으로 탐색하면서 in연산을 사용하였다. 하지만 리스트를 탐색하는 것은 O(N)의 시간복잡도가 발생하여 시간초과가 발생하였다. 이를 set이나 dict 자료형을 사용하면 O(1)의 시간복잡도를 갖기 때문에 효율적이라는 것을 알게되었다. 구현 N개의 수를 set 자료형으로 입..

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 접근 다른 사람들의 풀이를 참고하였다. 현재까지 이해한 것은 각각의 money로 만들 수 있는 1부터 n까지의 수를 누적해서 계산해나간다. 1은 1부터 n까지의 돈을 만드는 경우의 수가 1개이다. 2는 1을 만들 수없기 때문에 이전의 1에서 1을 만드는 경우의 수에서 가져온다. 그리고 2로 2를 만들 수 있는 경우의 수는 1+1과 2이다. 즉 1로 만든 수와 자기..

HTML의 form을 통해 사용자가 입력한 정보를 서버에 전달하여 조회, 생성, 수정, 삭제 등을 할 수 있다. 하지만 사용자가 입력한 정보를 "유효성 검사"를 실시하여 알맞은 데이터를 저장할 수 있도록 한다. 이 과정은 꽤 복잡할 수 있는데 Django에서는 Forms라는 클래스를 통해 이러한 복잡한 과정을 축소할 수 있다. (Django 공식 사이트와 MDN을 참고한다.) Form이란 태그 안에는 최소 한 개 이상의 을 포함하여 여러가지의 으로 이루어져있다. 의 type 속성을 통해 다양한 위젯을 표현할 수 있다. 사용자가 안에 어떠한 데이터를 입력하고 submit 버튼을 눌렀다면 의 action에 정의된 주소로 전달된다. action에는 데이터를 전달받은 곳의 URL 주소를 설정하며, 설정하지 않았..

programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 접근 최소한의 조작으로 입력된 문자열로 변경해야한다. 조작은 문자열 변경을 위해 위, 아래로의 조작과 바꿀 문자열의 위치로 이동하는 왼쪽, 오른쪽의 조작이 있다. 이를 최소로 하기위해서는 바꿔야하는 문자에서 A와 Z까지의 거리 중 최소를 구하고 현재 위치에서 왼쪽과 오른쪽으로 갈 때의 최소를 구하도록 한다. 구현 - 먼저 changed_name에 위, 아래..

문제 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제된다. 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소의 크기는 NxN이며 빈 칸, 벽, 바이러스로 이루어져 있다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 활성화된다. (0은 빈 칸, 1은 벽, 2는 바이러스) M개의 바이러스를 선택하여 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구한다. 입력 첫째 줄에 N(4이상 50이하)과 바이러스 개수 M(1이상 10이하)를 입력한다. 이어서 NxN의 연구소 맵을 입력한다. 출력 모든 빈 칸이 바이러스가 되는 최소시간을 구하고 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. ..

문제 NxM의 맵에서 1은 벽이기 때문에 이동할 수 없고 0은 이동할 수 있다. (1, 1)에서 출발하여 (N, M)까지 이동을 할 때 최소로 이동하는 거리를 구한다. 이때 벽으로인해 이동할 수 없다면 최대 한 번은 벽을 부수고 이동할 수 없다. 벽을 부수고 이동했을 때도 도착지에 가지 못한다면 -1을 출력한다. 입력 첫째 줄에 1이상 1000이하의 N과 M을 입력한다. 출력 첫째 줄에 최소거리를 출력한다. 접근 처음에는 맵을 탐색하다가 벽이 보였을 때 벽을 제거하고 BFS를 하도록 했지만 시간초과가 났다. 그래서 여러번 시도를 해보고 다른 사람들의 풀이를 참고하였다. BFS를 할 때 3차원 배열로 방문표시와 이동거리를 표시를 한다. 마지막 축은 크기가 2인데 0은 벽을 부수고 이동한거리, 1은 벽을 부..