KeepGoing! KeepGoing!

문제 설명 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다. 이전에 등장했던 단어는 사용할 수 없습니다. 한 글자인 단어는 인정되지 않습니다. 다음은 3명이 끝말잇기를 하는 상황을 나타냅니다. tank → kick → know → wheel → land → dream → mother → robot → tank 위 끝말잇기는 다음과 같이 진행됩니다. 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다. 2번 사람이 자신의 첫 번째 차례에 ..

문제 설명 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution..

문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return..

문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만,..

문제 n개의 수를 입력하는 배열 입력 그 배열에서 임의의 3개의 수를 더한 값이 소수인 경우가 몇번인지를 구하시오. 입력 5 1 2 7 6 4 //결과 4 내가 해결한 방식 일단 임의의 세개의 수를 더하는 로직을 구현 for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ for(int k = j+1; k < n; k++){ if(k != 0) { int tmp = nums[i] + nums[j] + nums[k]; if(validation(tmp)) cnt++; } } } 배열 내 세번씩 더하는 경우의 수는 삼중포문으로 위와 같이 로직을 구현해야 한다. 그런데 만약 k라는 값이 0이라면 세개의 값을 더하는 것이 아닌 두개의 값만을 구하는 것이기 때문에 조..

그리디 알고리즘 그리디 알고리즘은 일반적인 상황에서 최적의 해를 보장하지 않을 때가 많습니다. 따라서, 코딩테스트 문제를 보고 그리디 알고리즘을 사용했을 때 최적의 해가 나오는지 추론할 수 있는 능력이 필요합니다. (그리디 알고리즘이 일반적인 상황에서 최적의 해를 갖지 못하는 이유는 유튜브에서도 쉽게 찾아볼 수 있습니다. 그리디 알고리즘을 검색해서 찾아보시길 권해드립니다. 참고로 저는 동빈나 님과 코드없는 프로그래밍님을 참고했습니다.) 거스름 돈 문제 해결 아이디어 최적의 해를 빠르게 구하기 위해 "가장 큰 화폐 단위"부터 돈을 거슬러 주면 된다. 예시코드 n, money = map(int, input().split()) //n,money에 값을 입력하고 공백으로 구분 wallet = [] //빈 wal..

Dynamic Set을 구현하는 효과적인 방법중 하나 적절한 가정하에서 평균 탐색, 삽입, 삭제 시간 O(1) 작업 속도를 빠르게 만들 수 있다. Key value System을 이용해 자료를 정리 배열과 hashTable의 차이 배열의 작업속도는 O(n)으로 비효율적 순차적으로 검색하기 때문 HashTable의 작업속도는 O(1) Key값만 호출하면 value가 반환되므로 Hash Function 개발자가 생성한 값의 크기에 따라 hashfunction이 인덱스에 담는다. 만약 같은 크기의 값이 생성된다면 collision 즉, 해시 충돌이 일어나는데 같은 인덱스에 또 다른 인덱스를 생성한다. 즉, 같은 인덱스의 2개의 쌍을 저장하는것이다. 그러면 그 안에서 선형 검색이 이뤄진다.O(n) 결국 항상 상..