알고리즘

작년 10월 정도부터 본격적으로 github를 이용하여 알고리즘 문제 풀이를 시작했다.지금은 학교 사람들과 방학의 경우 1일 1솔, 학기 중엔 3일 1솔을 목표로 스터디하고 있다.혼자 풀게 되면, pass에만 집중하게 되는 것 같은데pull request 하는 과정에서

DFS로 풀었습니다. 최대 범위가 100이라 상당히 여유로운 문제였습니다.arr이라는 행, 열이 각각 (N+1)인 이차원 리스트를 만들었습니다.N이 아닌 N+1로 만든 건, 코드의 가독성을 위해서입니다.1번 컴퓨터가 0번 인덱스에 있는 것 보다는 1번 인덱스에 있는 게

개인적인 느낌으로, 지금까지 올라온 문제 중에 가장 어려웠습니다.문제에서 주어진 내용을 바탕으로 잘 구현하면 풀리지만, 그 과정이 쉽지가 않았습니다.저는 다리 위의 차량의 정보를 저장할 bridge와 다리에 진입하기 원하는 queue라는 이름의 두 개의 deque을 이

문제 특성상 양 방향에서 뽑아내는 경우가 생기기에, collections의 모듈에 있는 deque을 import 하여 풀었습니다.입출력 예시가 꽤 많이 주어져서 제출 전에 미리 테스트 해 볼 기회가 많은 친절한 문제였습니다.핵심 아이디어는 입력받은 문자열 S를 돌며,

제가 푼 방식으로 핵심 아이디어를 설명하겠습니다.주유소를 지나가며 리터 당 가격이 가장 저렴한 주유소 가격을 저장하고, (0번 인덱스의 주유소 리터당 가격으로 초기화 합니다.)현재 주유소 리터 당 가격과 비교하며,현재 주유소 리터 당 가격이 비싸면 -> 리터 당 가격이

핵심 아이디어는 '반대로 생각하기' 입니다. 즉, 여러 개의 동전들의 합을 조합하여 K원을 맞추지 말고,K원에서 가치가 큰 동전들로 나누기/나머지 연산 등을 통하여 0원을 만들어 나가는 게 핵심인 것 같습니다.입력받은 동전의 가치들을 내림차순 정렬을 통하여 가치가 큰

이전에 풀었던 그래프 문제보다 업그레이드 된 문제입니다.이전 문제가 단순히 하나의 노드에서 몇 개의 노드로 뻗어나가냐의 수준이었다면,이번에는 총 단지와 각각 단지마다 집의 수를 구해야 하는 문제였습니다.일단, 집이 있는 경우 1이고, 없는 경우가 0이므로 main 함수

num이라는 리스트를 만들고, 문자형 정수 '0' 부터 '9' 까지 담았습니다.N번 문장을 입력받으며, 해당 문자가 num에 속하면 (즉, 숫자형 문자가 있다면)total 이라는 변수에 int형으로 바꿔 값을 더해줬습니다.1순위로 길이, 2순위로 숫자의 합, 3순위로

거리의 합이 최소가 되기 위해선 중간 지점의 집에 안테나를 설치하면 됩니다.값이 여러 개인 경우 최소를 출력하라고 했으므로,값을 입력받은 뒤 오름차순으로 정렬 후 (길이 / 2 - 1)의 인덱스의 값을 출력하면 됩니다.

하한액(start)을 1, 상한액(end)을 arr의 최댓값으로 두었습니다.이진 탐색을 위해 sort 될 예정이니 arr-1이 최대가 됩니다.이진 탐색을 통하여 mid를 (start + end) / 2로 두고, 이진 탐색을 시작합니다.total이라는 변수에 arr의 각

이동 방향은 오른쪽, 아래, 오른쪽 아래로 총 3가지인데 상식적으로 한번에 오른쪽 아래로 가는 것 보다 오른쪽을 지난 후 아래 혹은 아래로 간 뒤 오른쪽으로 가는 것 처럼 중간 지점을 거쳐서 가는 것이 낫다는 것을 알 수 있습니다.즉, 현재 인덱스의 최댓값은 max(왼

평범한 DFS, BFS 문제와 다른 문제였습니다.BFS로 풀게 되면 최단거리는 찾을 수 있으나, 벽을 최소로 부수는 거리는 찾지 못하게 됩니다.왜냐하면 벽을 부순 횟수를 고려하지 않은 채, queue에 들어가는 순서대로 순회하기 때문입니다.이 문제를 해결하기 위하여 벽

0과 1만 예외처리 해주면 되는 문제였다.isPrime을 통하여 입력받는 인자의 제곱근까지 확인하며 나누어지는 경우 False를 반환하고, 끝까지 처리된 경우 True를 반환하면 된다.

replace를 이용하면 아주 쉽게 풀 수 있는 문제였다.사전 순으로 빠른 답을 출력해야 하므로, 'AAAA'로 먼저 바꿔준 뒤, 'BB'로 바꿔주면 된다.check라는 함수를 만들어서 문자열에 'X'가 있는 경우 false를 반환하고 그렇지 않은 경우 true를 반환

solved.ac 기준 실버 5인데, 생각보다 까다로웠다.bingo 라는 함수를 통하여 각각의 가로줄, 세로줄, 대각선에서 0이 연속으로 5개인 경우 total 변수를 1 증가시켜 준다.함수의 마지막 부분에서 total 변수가 3 이상인 경우 True를 반환한다.cha

브론즈 1로 체크되어 있긴 하지만 상당히 괜찮은 문제라고 생각한다.말 그대로 문자열을 세로로, 즉 같은 열(세로줄)의 문자열을 출력해주면 된다.문제를 풀다 보면 두 가지 어려움에 부딪히게 되는데, 첫째로는 문자열이 이어지지 않는 부분에 대한 예외 처리이다. 이 부분은

처음엔 BFS로 풀었고, 시간초과가 떴다. 그냥 BFS로 풀게 되면 매번 좌표를 입력받을 때 마다 똑같은 반복을 하는 것이 시간낭비같다는 생각을 하게 되었다.그래서 문득 스친 생각은, 그냥 2차원 dp 배열을 만들고 새로운 곳 방문 시마다 카운트 값을 기록해 놓으면 좋

범위에 0이 포함되어 있는데, 0개를 놓는 방법도 존재하므로 1로 카운트 해야 한다고 한다.또한, 파이썬 기준으로 eof 처리는 try-except문으로 except에서 break을 이용하면 된다.

이항 계수를 10007로 나눈 값을 출력하는 문제였다.파스칼의 삼각형이란 개념을 활용하여 문제를 풀었다.파스칼의 삼각형을 점화식으로 적으면 dpi = dpi-1 + dpi-1가 된다.K는 0부터 시작하므로, dp0를 1로 적어주면 되고,각 행의 첫 요소와 마지막 요소의