코딩 테스트 문제풀이

문제링크이번 문제는 64길이의 막대기를 나눠가면서 조건에 해당하는 막대기 길이까지 반복하는 문제이다. 기능 순서는 문제에서 제공하는 방법 그대로 적용하였고, Stack구조와 전체 합을 따로 생각하여 문제를 해결하였다.

이번 문제는 BFS와 DFS구현에 관한 문제이다. 이번 문제를 통해 BFS와 DFS를 구현하는 방식에 대해 알 수 있었다. BFS를 구할때 근접한 노드부터 진행해야하기 때문에, 타겟 노드가 A이고 근접한 노드들이 B일 때, A를 visited에 추가하고 B를 queue

이번 문제는 BFS의 전형적인 문제로 미로가 주워지고 맵이 주워졌을 때 시작점에서 도착지까지 최단 거리를 구하는 문제이다. 먼저 이러한 문제를 만났을 때, BFS와 DFS 모두 사용할 수 있지만 효율적으로 전체 노드를 탐지하지 않아도 되고 최단 거리를 구해야 함으로 B

이번 문제는 간단하게 BFS 혹은 DFS를 적용하는 문제이다. 시작 노드는 정해져 있고 이 노드와 연결된 다른 노드들의 수를 count하기만 되고 BFS를 사용하여 무슨 노드를 방문했는지 아래의 코드와 같이 찍고 방문한 노드들의 개수를 리턴해주면 되는데 시작 노드는 c

이번 문제는 주어진 토마토들의 위치 정보인 table에서 원소값이 1인 원소가 상하좌우의 근접값이 -1이 아니면 하나씩 퍼져나가는 형식으로 진행되어 결국에 전체가 다 퍼질려면 얼마나 걸리는지 확인하는 문제이다.우선 데이터를 입력받을 때, 원소값이 1인 원소들의 위치값(

이번 문제는 기본의 BFS 알고리즘을 사용하여 미로를 탈출 시 최단거리를 구하는 문제에 더불어서 다른 이동방법이 추가하여 구현하는 문제이다.먼저 기존의 BFS 알고리즘과 마찬가지로 need_visited 리스트에 시작 노드를 삽입하고 기본적으로 어떻게 움직일 건지 정의

이번 문제는 기존의 BFS 알고리즘을 사용하고 최단 경로를 도달하는 과정에서 벽을 한 개 까지 부수는 기능을 추가한 최단거리를 추출하는 문제이다. 기존의 BFS알고리즘과 마찬가지로 어떤 노드를 기준으로 동서남북으로 갈 수있는 곳으로 옮기고 최단경로를 구하는데, 벽을 한

문제 링크해당 문제를 처음 봤을 때, 어떠한 수가 주어졌을 때 3가지의 계산방식을 통해 1로 도달할 수 있는 최소 계산횟수를 구하는 문제라고 판단했다.그래서, BFS 매커니즘을 통해 아래와 같이 해결하고자 하였다.하지만, 시간초과가 발생하였다. 해당 문제를 위와 같은

백준 문제링크해당 문제는 다이나믹 프로그래밍 알고리즘을 사용하여 푸는 문제이다.해당 문제의 기능 요구사항은 아래와 같다.계단은 한 계단 혹은 두 계단씩 오를수 있다.연속된 3개의 계단을 밟으면 안된다.마지막 도착 계단은 꼭 밟아야 된다.문제풀이 첫번째 시도에서 2번 요

문제 링크왼쪽, 오른쪽 번갈아가면서 작대기를 던지는 데 던질 때 먼저 닿는 미네랄은 부서짐미네랄이 부서지면서 바닥과 연결된 미네랄과 연결이 끊길 경우 중력의 영향을 받아서 떨어짐단, 떨어질 때 형태가 변하지 않음해당 문제에서 내가 봤을 때 가장 중요한 포인트는 중력의

문제 출처nxn 체스판에 n개의 퀸이 있을 때 서로 잡지 못하는 포지션의 개수는?해당 문제는 유명한 퀸문제이다.이 문제를 풀기 위해 백트래킹을 이해해야한다.알고리즘 참고 링크백트래킹은 간단히 얘기해서 어떠한 해를 고를 경우 해당 해가 틀렸을 때 뒤로 돌아가서 다시 맞는

문제 링크해당 문제는 1부터 N까지의 수열의 중간중간에 연산(+,-,공백)을 넣게되었을 때 결과가 0이 되는 수식의 결과를 찾는 문제이다.처음 봤을 때, 다양한 방법으로 풀수있음을 느꼈다. 수열이 정해져 있고 중간에 어떠한 연산자가 들어가냐에 따라 달라지기 때문에 DF

문제 링크해당 문제는 리스트 형태의 스카이라인이 주어졌을 때 건물이 최소 몇개인지 물어보는 문제이다. 문제에서 제공하는 예제를 아래의 배경에 보이고자 한다.위와 같은 배경에 아래와 같이 스카이 라인이 그려진다.주황색 칸에 직사각형 빌딩을 최소로 채우기 위해 아래의 그림

문제 링크해당 문제는 양 끝이 연결된 컨베이어 벨트에 연속된 스시 접시 k개를 잡을 때 종류가 최대인 값을 구하는 문제이다.문제를 처음 봤을 때 sliding window 알고리즘을 통해 풀수있음을 알 수 있었다.이러한 방식으로 리스트 슬라이싱을 통해 sliding w

문제 링크해당 문제는 어떠한 수열을 제공받았을 때 1부터 M까지 정렬된 수로 전환하려면 최소 몇번 움직여야하는지 물어보는 문제이다.해당 문제에서 최소로 움직여야하기 때문에, 어떠한 값이 제자리로 위치하는지 보다는 수열에서 증가하는 수들의 집합들 중 큰 집합을 고정해두고

문제 링크해당 문제는 어떠한 수열에서 원소가 다른 원소 2개의 합인 것이 몇개 있는지 물어보는 문제이다.해당 문제를 풀기 위해 아래의 코드와 같이 문제를 풀었다.위의 코드를 간략하게 정리하자면 주어진 수열을 정렬한 다음 다른 원소 2개의 합도 2차 반복문으로 풀었다.

문제 링크해당 문제는 어떠한 배열판에서 알파벳을 (0,0)부터 시작해서 동서남북으로 가되 전에 선택한 알파벳이 중복이 안되도록 건널때 최대로 이동할 수 있는 알파벳 수를 물어보는 문제이다.우선 문제를 처음 봤을 때 DFS로 풀면 될 것 같았다.그럼으로 아래의 코드처럼

문제 링크(https://www.acmicpc.net/problem/2110\\)해당 문제는 수직선상의 좌표에서 각 좌표에 몇개의 공유기를 설치했을 때, 인접한 공유기 사이의 최대 거리를 구하는 문제이다.먼저, 아래와 같이 러프하게 풀었다.당연하게도 시간초과가

문제 링크해당 문제는 전체 문자열 중 특정 문자열이 들어갔을 경우 없애는 작업을 반복했을 때, 더이상 없어지지 않는 문자열이 무엇임을 알아내는 문제이다.해당 문제를 풀기 위해 아래의 코드와 같이 러프하게 풀어봤다.당연하게도 시간초과가 발생하였다. 어떤 부분이 시간초과가

문제 링크해당 문제는 주어진 수열에서 수가 중복되지 않는 연속된 수들의 조합의 개수를 물어보는 문제이다.해당 문제를 풀 때, 아래의 방법과 같이 러프하게 풀어봤다.해당 코드는 당연히 시간초과가 발생하였다. 그 이유는 아래와 같다.N이 최대 100000이기 때문에 O(n

문제 링크해당 문제는 주어진 단어들의 접두사 중 가장 큰 접두사를 갖고 있는 단어 2개를 출력하는 문제이다.해당 문제를 봤을 때, 아래와 같이 간단하게 풀어봤다.하지만 이 코드는 여러가지 문제점이 아래와 같았다.O(n^2)임으로 시간 초과정렬을 했을 때, 문제에서는 최

문제 링크해당 문제는 제공되는 좌표에 LxL를 최대로 담아냈을 때 그 밖의 별똥별 좌표의 개수를 물어보는 문제이다.문제를 봤을 때, 1 ≤ N, M ≤ 500,000이기 때문에 전체 탐색시 N과 M을 기준으로 돌리면 100% 시간초과가 발생할 것이다.그럼으로 우리는 K

문제 링크해당 문제는 어떠한 수열을 줬을 때, 연속된 수를 골랐을 때 합이 S 이상인 조합들 중 최소 원소를 고른 조합의 원소 개수를 물어보는 문제이다.우선 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)이기 때문에 섣불리

문제 링크해당 문제는 분리 집합에 대해 모르면 풀기 어려운 문제이고, 분리 집합이 생각났다면 풀기 쉬운 문제이다.우선, 분리 집합에 대해서는 아래의 저번 포스팅에서 자세하게 작성했으니 모른다면 보고 오길 바란다.분리 집합 이론 및 코드우선 친구의 친구는 친구임으로 같은

문제 링크해당 무넺는 어떠한 보드에 부메랑을 4가지 모양으로 둘 수 있을 때, 합이 최대가 되는 값을 구하는 문제이다.해당 문제를 풀기 전에, 단순무식하게 브루트포스를 사용하지 않고 백트래킹을 활용해서 중간에 조건이 성립되지 않을 경우는 멈추고 답을 찾아간다면 문제를

문제 링크해당 문제는 어떤 문제를 풀었을 때 각 문제마다 데드라인이 존재하고 각 문제를 풀 때 1씩 시간이 든다면 최대로 컵라면 수는 몇인가를 묻는 문제이다.먼저, 최대 컵라면을 만들 수 있는 경우의 수를 계산하기 위해 DFS 혹은 BFS로 문제를 풀 수 있는지 확인해

문제 링크해당 문제는 어떠한 맵이 주어졌을 때 어떤 노드에서 노드로 갈 때 노드의 값이 작아지는 방향으로만 움직일 수 있을 때 왼쪽 상단에서 출발해서 오른쪽 하단에 도착할 수 있는 경우의 수를 구하는 문제이다.우선 딱 봐도 DFS를 사용하는 것이 눈에 보여 아래와 같이

동전1 링크 동전2 링크 문제 소개 해당 문제들은 어떤 동전들이 있을 때 조합을 통해 주어진 조건에 부합하게 답을 내는 문제이다. 동전 1 문제 분석 해당 문제에서는 어떤 동전들이 있으면 그 동전들의 합들의 경우의 수를 구해야한다. 구현하기 위해 아래와 같이

해당 문제는 격자판에서 적이 있을 때 최하단에 궁수를 배치하고 공격 -> 적 한칸 아래 이동하는 순서로 진행할 경우 처치 가능한 수를 물어보는 문제이다.문제를 해결하기 위해 아래의 기능 요구사항을 정리하였다.3명의 궁수 배치배치된 각 궁수들의 타겟 위치적 이동1번은 판

해당 문제는 3가지 종류의 그래프가 주어지고 하나의 정점을 생성하여 연결한 결과에서 임의로 생성한 정점의 번호와 3가지 종류의 개수를 카운트하는 문제이다.일단 해당 문제를 푸는 과정에서 골치가 아픈 부분은 아래와 같았다.임의의 정점 찾기그래프 종류에 따른 카운팅차례차례