알고리즘 학습

1️⃣ 정답 코드 클래스, static main 구조로 작성해야 하는줄 알고 초반에 계속된 컴파일 오류에 오래 걸렸다. 백준처럼 풀코드로 작성하는 것이 아닌 알고리즘 부분만 작성해야 함을 알았다. HashMap 을 이용하여 key, value 형태로 저장되게 하였으

입력받은 문자열이 거꾸로 읽어도 같은 단어이면 팰린드롬이라 한다.사용자에게 받은 문자를 Input 변수에 저장한 뒤 substring 메소드를 활용하여 문자열의 앞과 뒤를 비교하도록 하였다. isPalindrome 이란 변수를 boolean 으로 초기화 하여 true

체스판 피스 개수의 디폴트 값과 입력 받은 현재 존재하는 피스의 개수를 이용하여 올바른 체스 세트를 만드는 프로그램countTokens 를 사용할 때 token 사용으로 값이 변할 수 있으므로 변수에 저장하도록 하자.

Python의 중복 제거인 set 기능을 활용했다.

▶︎ 숫자로 된 리스트 중에 접두어로 겹치는 부분이 있으면 false 를 출력한다. 접두어가 되는 리스트 요소를 따로 뽑아서 비교해야 하는데 방법이 떠오르지 않았다. 결국 정렬을 통해 리스트를 나열하고 정렬된 숫자는 앞 뒤로 접두어가 될 경우가 존재하기에 if 문으로

이 함수는 해당하는 문자열이 특정 문자 또는 문자열로 시작하는지 체크하는 함수다.체크하여 여부를 확인하고 ture or false 를 반환한다.체크할 문자열.startsWith(비교할 값) 의 형식대로 사용한다.특정 문자열로 끝나는지 체크하며, 로직은 startsWit

각 의상의 종류의 개수만큼 경우의 수가 달라지므로 종류의 개수와 각 종류마다 몇 개의 의상이 존재하는지 구하는지가 중요했다. Map 을 활용하여 <의상의 종류, 개수> 와 같이 HashMap을 만들고 반복문을 통해 각 개수끼리 곱한 후 결과 값을 반환하였다. 마지

사용자로부터 입력받은 영어단어 중 각 알파벳의 사용 빈도수를 측정해서 제일 빈도가 높은 알파벳을 찾는 알고리즘이다. 소문자나 대문자는 상관 없으며, 최대 빈도수가 없는 경우엔 '?' 를 출력하도록 한다. a~z 까지의 카운트를 할 배열을 만들어준다.입력받은 단어를 한

charAt(index) 이와 같이 사용하면 해당 String 문자열의 index 위치에 있는 값이 나온다.

한 학생의 '수업이름 학점 성적' 에 대한 값을 20개 받으면 평균 학점을 구하는 프로그램이다. 평균 학점은 '총 성적 / 총 학점' 이므로 이를 활용해 문제를 풀었다. 학점이 'P' 인 경우는 성적에 제외해야 된다.학생의 성적을 String 으로 받지만 이를 해당하는

StringIndexOutOfBounds 에러가 발생했다. 만약 i 가 문자열의 마지막 인덱스라면 범위를 넘어가게 되기 때문이다. 따라서 문자열의 길이 - 1 을 한 값이 i 보다 크다면 로직이 수행되도록 수정했다. d에 대한 크로아티아 알파벳을 찾아낼 때 wordLe

두 개의 2차원 배열을 입력받은 값으로 저장하고 행렬 덧셈을 하는 문제다.문제를 접근할 때 설명대로 배열 두개를 초기화하여 입력받은 값을 저장하는 방식으로 하였다. 물론 이렇게 풀어도 정답은 나오지만 굳이 배열을 두개 생성하지 않고 두번째 배열 값을 받을 때 첫번째 배

별 찍기 문제이며 아래와 같이 풀었다. 특히 별찍기 문제가 어려운 거 같다. 이해하기보다 먼저 로직을 여러번 해보며 익히면 좋을 거 같다. 별을 찍을 때 무조건 홀수 단위로 찍게 되는데 이 특징 때문에 2n-1 을 사용함을 알게 되었다.

2차원 배열문제이다.2차원 배열에 입력 받은 81개의 숫자를 입력한 뒤 입력받은 숫자 중 가장 큰 값과 그 값에 해당하는 행열 인덱스를 출력하는 문제이다.처음에 9\*9 2차원 배열을 만든 뒤, 입력 받은 값을 배열에 넣는 과정 속에 최댓값을 비교하여 구하는 로직을 추

2차원 배열 문제이다.입력으로 받은 문자들을 2차원 배열에 넣은 뒤 행열을 반대로 출력하는 문제이다.row 는 k , column 은 ㅣ 로 초기화문제에서 무조건 5줄의 문자와 최대 15글자로 이루어진다고 하였으므로 5\*15 2차원 배열을 생성하였다. 이 후 값을 다

2차원 배열에서 입력 받은 좌표의 +10 범위의 공간 크기를 구하는 문제이다. 도화지의 100\*100 배열을 boolean 자료형으로 만들어 flase로 지정해준 뒤, 반복에서 해당 배열 인덱스에 접근할 때 최초 접근이면 true로 바꾸는 로직을 통해 count 를

알고리즘 학습 문제 풀이모든 테스트 케이스에서 최대 이익을 낼 수 있는 계산을 하는 알고리즘1,000,000일 동안 10,000의 가격으로 매일 사게 되면 100,000,000,000 이 되므로 int형으로 불가능 long 사용 일단, 처음에 접근한 방식은 가격이 '3

입력 N 개의 수가 주어졌을 때, 일정구간의 합을 구하는 방법for 문을 사용해도 되지만, 시간적 조건이 있다면 아래와 같은 방식으로 입력 받음과 동시에 합에 대한 S 배열을 생성하여 풀 수 있다.A 라는 배열에 5,4,3,2,1 이 들어왔을 때 각 자릿수의 누적 합인

BufferedReader 로 입력 받은 String 문자열을 charAt(i)를 통해 한 글자씩 추출이 가능하다.이 글자를 int 형으로 바꾸려면 어떻게 할까?우선, char 형을 바로 출력하면 아스키 코드 값으로 출력된다. 그렇기에 아스키 코드 값이 아닌 실제 정수

문자열을 자를 땐, str = '012345' 이라 가정했을 때str.substring(3) -> 345str.substring(3,6) -> 345와 같이 출력된다.

선입선출 FIFO → 제일 먼저 들어간 값이 제일 먼저 나온다.백준 2164 문제선언관련 함수add() → 값 추가peek() → 값 확인poll() → 값 출력 후 삭제element() → peek 과 비슷, 하지만 값이 없을 경우 오류 출력size() → 자료구조의

앞 뒤의 수를 확인해 오른쪽으로 순차적으로 이동하며 배열의 값을 크기대로 정렬한다.N개의 인덱스가 존재하는 배열일 경우 N개를 N번씩 돌아가며 정렬해야하므로 N^2의 시간복잡도를 가지게 된다.백준 2750오름차순 정렬하여 출력한다.풀이첫 번째는 버블 정렬, 두 번째는

재귀함수로 구현되며 스택구조를 가진다.한 번 방문한 노드는 다시 방문하지 않음시간 복잡도는 O(V+E)로 노드 수 + 에지 수로 구한다.백준 11724풀이!visited\[i] 부분이 처음에 계속 이해가 되지 않았다. visited 는 false로 초기화 되었는데,

문제 이해 각 테스트 케이스마다 학생들의 점수가 주어지는데 해당 점수를 토대로 각 학생들의 등급을 내는 문제이다. 등급을 나누는 기준만 해결하면 쉬운 문제이지만 그 생각이 잘 나지 않아 오래 걸렸다.

1로 적혀 있는 곳에 글자가 들어갈 수 있으며 첫 라인에 주어지는 두개의 수를 N, K로 저장한다.N 은 배열의 가로 세로 크기이며, K 는 단어의 길이이다. 처음에 어떻게 접근해야할지 감이 오지 않아 다른 사람의 풀이를 참고하였다. https://www.yo

입력 받는 정수로 Stack 자료구조에 연산을 수행한다. N 의 최대는 10,000 이므로 이중 for문이 아닌 이상 모든 조건에서 수행가능할 거 같다. 우선 반복 횟수인 N을 입력 받고, 각 반복마다 명령어 + 정수 혹은 명령어 를 입력 받는다.입력 받은 명령어의

요세푸스에 대한 설명이 문제에서 너무 부실하게 설명되어 있다.예를 들어 K를 3이라 정했을 때, 계속 반복하며 3번째의 숫자가 빠지게 되는데 빠지고 난 뒤 다음 수부터 다시 첫번째가 된다.N 크기의 자료구조 큐를 생성하고 1부터 넣는다. 계속 poll() 을 통해 앞의

문제를 이해하는데 너무 오랜 시간이 걸렸고, 다리를 건너는 시간에 대해 이해를 못하고 있던 중에 다른 사람의 풀이를 보고 이해할 수 있었다. 참고다리 위에서 한 칸씩 움직일 때마다 1초가 흐른다. 만약 다리의 길이가 2라면 한 트럭이 지나갈 때까진 2초의 시간이 흐르게

괄호가 ( 가 있으면 무조건 ) 로 닫혀야 하나의 VPS 라는 괄호 문자열이 된다. 문제에서 주어지는 테스트 문자열 중에 VPS가 되는 케이스는 YES, 되지 않는 케이스는 NO 라고 출력한다.스택 자료구조를 활용하여 먼저 '(' 괄호가 입력되면 스택 구조에 넣고, '

🧑🏻‍💻 배열 좌표 이동 구현 문제

입력 받은 문장을 단어마다 잘라서 단어를 뒤집어 출력한다. 그냥 반복문만 사용해서 할 수 있겠지만 스택을 사용하면 시간제한에 걸릴 거 같다. 문장을 입력 받고, 스택을 초기화 한다. (여기서 스택을 생성한게 중요하다. 시간복잡도 해결을 위해)단어의 개수만큼 반복을 한다

이진탐색을 활용하여 여러 길이의 나무를 어떤 길이로 잘랐을 때 M 만큼의 남은 나무들의 합을 구할 수 있는지 푸는 문제.이진탐색을 위해1\. 나무 길이의 최대, 최소 값을 구함 그리고 해당 값으로 중간 값을 구해서 로직을 구현2\. 중간값을 통해 잘려진 남은 나무의 길

각 테스트 케이스별 우선순위에 대한 수를 입력받는다.해당 우선순위별로 프린트가 출력되는데 우선순위가 높은 게 먼저 출력된다. 우선순위가 낮은 경우 다시 뒤로 순번이 밀리게 된다.일단 우선순위로 인해 제일 높은 수인 경우 먼저 출력되므로, 최대값을 구하고자 하였다.해당

주어진 값과 주어진 배열을 이용해 배열안의 값을 찾는 문제이다.숫자가 적혀 있는 카드의 배열과 여러 개의 숫자가 주어지는데, 이 여러개의 수의 값들이 카드의 값으로 있는지 존재 여부를 체크한다.이진탐색을 활용하여 카드의 값을 배열로 만들고, 주어진 정수들의 값을 tar

공통사항DFS & BFS -> visited 배열을 각 노드의 방문 여부를 확인한다.시작 노드 방문처리for(시작 노드의 자식노드 방문 (값이 존재하고, 방문하지 않은 노드일 경우))2-1. 재귀 구현큐에 값 삽입방문 처리while (큐가 존재하는 동안)3-0. sta

🧑🏻‍💻 문제 💡문제 분석 요약 주어진 그래프를 DFS 와 BFS를 통해 탐색을 한 순서에 대해 출력한다. 💡알고리즘 설계 입력받은 그래프와 방문 여부 배열은 static 변수로 선언하여 사용한다. dfs 로직 구현 시작 노드 방문처리 for(시작 노드의

n이란 입력값의 크기를 의미하는 것이고n에 의해 알고리즘이 받는 영향력(반복수)을 표기하는 것보통 N 앞에 상수가 붙으면 해당 상수는 로직에 큰 변화를 볼 수 없으므로 생략한다. ex) 3N -> N, 2N^2 -> N^2알고리즘의 최악의 수를 값으로 표현입력 값의 변

DFS를 활용해서 주어진 그래프 내에 각 DFS 안의 노드가 몇개인지 탐색하는 문제이다. 그래프 배열 생성방문 여부 배열 생성그래프를 처음부터 끝까지 돌면서 1이 있는 인덱스를 만나면 DFS 시작3-1. DFS가 수행될 때 count를 통해 몇 번 재귀 되는지 탐색각

🧑🏻‍💻 문제 💡문제 분석 요약 1 과 0 으로 된 N * M 배열의 미로가 존재한다. 1 이라고 적혀있는 곳으로만 이동 가능하며, 입력으로 주어지는 배열을 통해 처음 시작 위치 좌표에서 (N,M) 즉 제일 오른쪽 하단을 가는 최단 시간을 구해라. 한 칸을

N 과 K 의 숫자 두 개를 입력받는다.N에서 K까지 이동할 때 걸리는 최소 시간을 구해라. 이동하는 방법은 x-1 x+1 2\*x 의 크기만큼 이동할 수 있다. 최소 시간이므로 BFS를 활용하여 푼다.1\. Q 를 초기화 하여 각 노드마다 수행 되는 방법이 x-1 x

세 정수가 주어졌을 때 등차수열이 되도록 만들 수 있는 최소 값 X 를 구하기▶︎ 💡 문제 링크등차수열의 조건을 통해 a를 변경해서 X 를 구할지, b를 변경해서 구할지, c 를 변경해서 구할지에 따라 세가지의 경우가 나오므로 각 경우를 구해서 최솟값을 찾는다.변화량

DFS 또는 BFS 를 통해서 인접한 노드를 탐색하며 몇 번 탐색되는지 구하는 문제이다.BFS 를 활용하여 로직을 설계 했다.1\. 시작 점으로부터 상하좌우를 움직이며 '1'이 있는 경우 큐에 위치에 대한 값을 넣어 반복한다.2\. BFS가 시작할 때마다 count를

DFS 알고리즘을 사용할 때 연산을 줄이기 위한 함수를 활용한 문제SWEA.2808체스판과 같이 N\*N 크기의 칸이 있을 때 체스 퀸 을 둘 수 있는 위치를 구한다.여기서 둘 수 없는 위치는 '대각선과 수직방향' 에 위치할 땐 둘 수 없다. N\*N 크기의 배열에

문제 내에서 주어지는 배열의 요소엔 W 와 B 가 들어가 있다. 인접해 있는 같은 요소끼리 있을 때 그 값의 제곱을 하여 최종적으론 각 요소끼리 제곱한 합을 구한다. DFS 를 통해 모든 배열을 돌면서 각 요소의 합을 구한다.여기서 중요한 건 요소가 W 와 B 두 개가

🧑🏻‍💻 문제 코드 (BFS 와 DFS 활용)

현재 상태에서 볼 수 있는 선택지 중 최선의 선택을 하는 알고리즘.시간복잡도는 우수하나 항상 최적의 해를 보장하지 못한다는 단점이 있음.만약, 서울에서 대전을 거쳐 부산을 가는 가장 빠른 경로를 선택한다고 가정해보자.서울 ~ 대전의 경로에서 가장 빠른 경로는 1번 경로

N 개의 동전이 있을 때 동전의 조합으로 K 원을 만든다. 이때 최소한의 동전 조합 개수를 구해라. 최악의 경우: 최악의 경우 ( K )가 매우 큰 값이고 동전들의 값이 1인 경우입니다. 이 경우 ( K )를 0으로 만들기 위해 ( K )번의 while 반복이 필요합니

N 명의 사람이 존재함각 사람들마다 돈을 인출하는데 걸리는 시간이 정해져 있음.사람들이 한 줄로 서서 모든 사람이 인출한 시간을 구하려면 시간이 계속 누적됨N 명의 사람의 배열 저장 시간 N, N 명의 사람 인출 시간 누적 계산 N2N 이므로 따라서 O(N)누적 값을

Comparable & compareTo회의를 할 수 있는 회의실이 딱 한 개 존재한다.여러 개(N 개) 의 회의 시간(시작 시간, 끝 시간)에 대한 정보를 준다.회의 시간은 서로 겹칠 수 없을 때 가장 많은 회의를 진행하면 몇 번의 회의를 할 수 있을까?단, 회의의

여 2 / 남 1 로 팀을 만들어야 한다.N 명의 여자, M 명의 남자가 있을 때 K 명은 팀에서 제외 된 후 팀을 만든다.팀을 만들 수 있는 최대 개수는?우선 여자는 2명이상이어야 하며, 남자는 1명 이상이어야 한다.팀을 꾸린 후에 인턴쉽에 참가 할 K 명이 되는지도

주어진 L, P, V 를 활용해서 캠핑장 최대 이용 기간을 구해라.일단 주어진 예제를 보면, 처음에 5, 8, 20 케이스를 계산해 보자5일간 최대 이용 가능하므로 2번하면 10일이 된다. 그리고 남는 4일이 L보다 작으므로 결과는 14.예제를 봤을 때 패턴이 존재한다

N 개의 로프를 이용해 물체를 들어 올린다.각 로프마다 들 수 있는 무게가 다 다르다. 로프를 이용해 물체를 들게 되면 각각의 로프에 로프의 개수만큼 나눈 중량이 걸리게 된다.로프들에 대한 정보가 있을 때 최대로 들 수 있는 무게를 구해라.예를 들어 5,3,2,1 의

메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도를 개선한다.부분 문제의 중복: 큰 문제를 작은 부분 문제로 나눌 수 있으며, 이러한 부분 문제가 여러 번 반복될 때 동적 프로그래밍이 유용.최적 부분 구조: 문제의 최적 해결 방법이 부분 문제의 최적

B O J 순서대로 보도 블럭을 밟을 수 있다. 각 보도블럭을 건너는 에너지는 보도블럭의 거리에 제곱이다.주어진 보도블럭 조합으로 건널 수 있는 최소의 에너지를 구해라.최소 값을 구하는 목적이므로, 각 연산을 저장할 배열을 초기화 할 때 Integer.MAX_VALUE

곡의 개수 N시작 볼륨 S볼륨 최대치 M각 노래마다 바꿀 수 있는 볼륨의 크기 정보모든 노래를 진행하면서 각 노래마다 변경할 수 있는 볼륨 값으로 볼륨을 더하거나 뺄 수 있다. 마지막 곡을 연주할 때 가장 높은 볼륨은 몇일까?각 노래마다 볼륨 값을 더하거나 빼기 때문에

주어진 N \* N 의 2차원 배열에서 좌상단에서 시작해 우하단으로 가는 경우의 수를 구한다.무조건 오른쪽 또는 아래로 내려갈 수 있으며 각 인덱스의 값이 칸을 이동할 수 있는 값이다.처음엔 시작점부터 시작해서 인덱스 값으로 우측 또는 아래로 움직이며, 움직일 때 N의

상담을 진행하면 각 상담별 정해져 있는 페이를 받는다. 상담의 기간 동안은 다른 상담을 진행할 수 없다.최대 수익은?DP 를 활용하여 각 날짜별 받을 수 있는 최대 페이의 값을 저장해가며 마지막 날의 값을 출력한다. 두번의 반복문으로 2N이기에 최종적으로 N의 시간복잡

숫자 1,2,3 을 더해서 정수 n 을 만들 수 있는 경우의 수를 구해라초기 조건 설정: 주어진 작은 수들(1, 2, 3)에 대해 가능한 모든 경우의 수를 초기화DP 배열 갱신: 각 숫자 i를 1, 2, 3의 합으로 나타내기 위해, i를 만들 수 있는 모든 방법을 작은

버튼이 4개만 존재하는 키보드가 있다.A 버튼을 누르면 화면에 A 가 출력된다. Ctrl A 버튼을 누르면 화면의 모든 내용이 선택된다.Ctrl C 버튼을 누르면 화면의 모든 내용이 복사된다.Ctrl V 버튼을 누르면 복사된 내용이 출력된다.N 번 키보드를 누를때 A의

프로그래머스 문제 링크처음에 반복문으로 q의 크기만큼 반복하게 했지만 q의 크기가 줄어들면서 오류가 생겼다.자료구조를 사용할 땐 while 을 활용하자!

재귀를 활용한 문자열 조합과, 소수 판별은 언젠가 또 이용될 거 같으니 꼭 다시 복습하기!문제 링크주어진 숫자를 이용하여 모든 조합의 숫자를 구한 뒤, 소수의 개수를 출력모든 문자열의 조합으로 만들 수 있는 숫자들 생성1 숫자의 중복을 없애기 위해 HashSet 사용하

던전이 3개 있고, 현재 피로도가 100이라고 가정.던전 A: 최소 필요 피로도 50, 소모 피로도 30던전 B: 최소 필요 피로도 40, 소모 피로도 20던전 C: 최소 필요 피로도 30, 소모 피로도 10초기 상태피로도: 100탐험 경로: \[]던전 A를 탐험 (A

백준 2573그림상 빈칸은 바닷물이며 숫자가 빙산의 높이이다. 각 빙산마다 바닷물과 마주하고 있는 면의 수 만큼 녹게 되어 한 해가 지날때마다 면의 수만큼 사라지게 된다.아래의 그림은 1년 뒤의 빙산 모습이다.문제에서 결국 원하는 건 빙산의 조각이 2개 이상으로 되는

"A E I O U" 에 대한 문자들만 이용하여, 길이 '5' 이하의 모든 단어를 만들고문제에서 원하는 단어가 몇번째에 있는지 구해라.주어진 문자로 조합을 만들었을 때 중복 되는 문자들은 불필요하므로 HashSet 을 이용하여 중복 단어를 제거한다.문자들이 사전 순서대

보기에 문제는 쉬웠다. 주어진 배열을 그래프 형태로 변형한 뒤 연결 간선을 하나씩 삭제하며 매번 dfs 를 진행하고dfs 탐색 수만큼의 차를 구해 최소 값을 구한다. 하지만, 생각으로는 너무 많은 시간복잡도를 요구할 거 같아 쉽게 접근하지 못했다. 방법은 간단했다. 그

여러 경우의 수가 존재하기에 재귀를 이용해 풀면 될 것 같다. 재귀 부분 오랜만에 보니 또 익숙치 않다. 다시 풀어보기로

문제 풀이 다음에 다시 풀어보기로