알고리즘 기초 (프로그래머스 Lv0)
1.Programmers > 같은 숫자는 싫어(JS)
Programmers에서 sql을 풀고 나서 알고리즘을 도전중이다. 실행 & 테스트 환경이 편한 장점이 있다. 효율성까지 고려한 정답은 아래와 같다.
2.백준 > 단어 뒤집기(Java)
맨 처음에 뒤집을 문장의 개수를 입력하고, 이후에 입력한 문장들의 단어를 뒤집어서 개행으로 리스트 출력한다. 클래스 이름이 Main이어야 한다. import한 클래스들은 포함해야 한다.오답 이유 뒤집기는 성공했는데 1줄만 고려해서 짰다. length를 추가 안 함.개행
3.백준 > 괄호
결과 : 정답 (를 넣는 leftStack와 )를 넣는 rightStack을 별도로 선언하고 줄마다 괄호를 쪼개는 것은 for문과 charAt()메서드를 사용해서 nextToken()을 처리하는 방식을 썼다.
4.백준 > 스택 수열
결과 : 예시 결과는 제대로 출력했지만 오답 cnt를 이용한 for문에서 k 초기화에서 cnt + 1하지 않아서pop하는 조건 분기처리를 틀려서 (값이 다를 경우 바로 NO를 출력하도록 하기)cnt++이 아니라 inputNum값으로 엎어치기하는 것이다. 중간에 NO인
5.백준 > 에디터
명령어에 따라 커서를 바꿔가며 문자를 추가 또는 삭제한다. 최종적으로 문자열을 출력한다.시간초과로 실패.substring과 StringBuilder 조작을 해서? 더 나은 방법을 찾다가 2개의 스택으로 풀라고 해서 다시 풀었다. 훨씬 코드가 간결하다. leftStack
6.백준 > 큐
큐를 직접 구현하기 성공 구현과 로직은 머리 안에 있었는데 문제를 제대로 안 읽어서 헤맸다. push는 print하면 안되고 문제 제출할 때 클래스명과 제출할 때 문제 확인하는 걸 잊었다;;push x와 같은 명령어의 경우 명령어와 파람을 분리해야 하는데 기존에는 ch
7.백준 > 요세푸스 문제
결과 예제는 제대로 출력하지만 틀렸음. 오답노트 소요 시간 1.5일
8.백준 > 스택
업로드중.. 스택 결과 정답 어려웠던 점 스택은 정적과 동적으로 나뉘는데 arrayList로 구현은 가능한데, 배열로 구현하는 것이 어려웠다. 배열은 선언순간부터 크기를 지정해야 하기 때문에 length가 항상 값들이 다 들어있는지 확신할 수 없다. 그래서
9.백준 > 덱
업로드중.. 덱(Deque) 덱을 util 쓰지 않고 구현하기 덱(Deque)이란? 스택과 큐만 들어보고 덱은 처음이었다. 덱은 양방향 큐와 같다. 앞뒤로 선입선출이 가능한 구조이다.
10.백준 > 단어 뒤집기 2
띄어쓰기를 기준으로 단어 내부 순서만 뒤집기태그로 감싸져 있는 경우 태그의 순서는 그대로 두고 <>안의 단어만 내부 순서 뒤집기(띄어쓰기 내부 적용 마찬가지)처음에 if문이 3중 이상으로 복잡해 지길래 ' '를 처리하는 경우와 <>를 추가하는 경우로 나누어서
11.백준 > 알파벳 찾기
업로드중..주어진 소문자 영어 단어를 보고, 단어에 없는 알파벳은 -1로, 있는 알파벳은 영어 단어 내의 index를 출력하라. 정답 원하는 값을 출력하기 위해서는 2가지를 알아야 한다. 1\. 알파벳의 아스키 코드 - 97 (소문자이기 때문에 -97을 한다)2\. 문
12.백준 > 알파벳 개수
주어진 소문자 영어 단어를 보고, 단어에 든 알파벳의 개수를 배열로 나타내기. 정답 아래 부분과 배열 초기화를 0으로 한다는 점만 제외하면 알파벳 찾기 문제와 동일하다. 알파벳의 등장 횟수만큼 ++한다. 5분 내
13.백준 > 문자열 분석
문자열 N개가 주어졌을 때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하기 정답 알파벳 단어 문제에서 사용했던 빼기 방법을 사용해 보았다. (charAt(i) - 97) 보통 백준은 N으로 먼저 입력할 문장 등의 수를 입력받는데 이번에는 제한이
14.[백준, 자바] 11655번 - ROT13
ROT13 알파벳 + 13번째 자리의 알파벳으로 문자열을 암호화하기.
15.[백준, 자바] 11656번 - 접미사 배열
접미사 배열 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.
16.[백준, 자바] 10824번 - 네 수
네 수 a+b와 c+d를 더한 값을 출력하여라.
17.[백준, 자바] 1918번 - 후위 표기식
중위 표기법을 후위 표기법으로 바꿔보자.
18.[백준, 자바] 17298번 - 오큰수
오큰수 해당 숫자의 오른쪽에 있는 숫자들 중에서 큰 수이며, 동시에 가장 왼쪽에 있는 수를 출력해야 한다. 결과 오답 -> 시간 초과(이중 for문) 오답 분석 스택에 항상 값만 담는 것이라고 생각했는데 배열 주소, 즉 인덱스를 담을 생각은 전혀 못 했다. 소요
19.[백준, 자바] 1929번 - 소수 구하기
위 문제는 백준 기초 > 소수 찾기와 관련이 있다. https://www.acmicpc.net/problem/1978 소수 구하기 풀이 Q. 에라토스테네스의 체 소수 판별 알고리즘으로 유명하다. 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)
20.[백준, 자바] 1978번 - 소수 찾기
주어진 숫자 배열에서 소수가 몇 개인지 찾아보자.
21.[백준, 자바] 1934번 - 최소공배수
주어진 두 수의 최소공배수 구하기
22.[백준, 자바] 10430번 - 나머지
첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.정답
23.[백준, 자바] 2609번 - 최대공약수와 최소공배수
최대공약수와 최소공배수 유클리트 호제법이란? 최대공약수를 구하는 공식이다. 최소공배수는 주어진 로 쉽게 구할 수 있다. 결과 소요 시간 30분내
24.[백준, 자바] 11005번 - 진법 변환2
진법 변환을 한다는 것은 2진법은 2로, 8진법은 8로 지정된 숫자를 계속 나눈다는 것이다.
25.[백준, 자바] 2089번 - -2진수
난 -2진법이라길래 2진법으로 이루어진 수의 보수를 구하는 것이라고 생각했다.
26.[백준, 자바] 1935번 - 후위표기식2
결과는 동일한데 틀렸다가, 답보고 제출했다가 몇 달 지나서 까먹은 채로 재도전해서 로직 맞추고, println() 형식만 틀림. > System.out.printf("%.2f", numberStack.pop()); 문제가 소수점 2번째 자리까지 출력이라
27.[백준, 자바] 1373번 - 2진수 8진수
BigInteger의 두번째 매개변수로 원하는 진법의 숫자를 넣으면 그 값으로 변환할 수 있다.
28.[백준, 자바] 1212번 - 8진수 2진수
BigInteger와 toString()을 쓰면 된다.
29.[백준, 자바] 11576번 - Base Conversion
엉망진창 미래 진법 풀기
30.[백준, 자바] 11653번 - 소인수분해
주석 달아가면서 열심히 풀었음.
31.[백준, 자바] 11653번 - 숨바꼭질 6
나는 수빈이 기준으로 동생들 사이의 거리를 가지고 계산하는 줄 알았는데, 수빈이가 첫번째 동생부터 차례로 각 동생들 위치로 가면서 계산을 해야 한다.
32.[백준, 자바] 9613번 - GCD 합
어떻게 풀어야 하는지는 맞았는데 입력값 맨 앞의 수까지 연산에 넣어서 망함;;
33.[백준, 자바] 1676번 - 팩토리얼 0의 개수
문제 링크 https://www.acmicpc.net/problem/1676 최종 코드
34.[백준, 자바] 11052번 - 카드 구매하기
백준 사이트의 테스트 케이스는 통과했으나, 20% 정도 채점하다가 틀렸습니다 판정받음
35.[백준, 자바] 11048번 - 이동하기
개인적으로 동적 프로그래밍은 처음 진입하기가 너무 어려운 알고리즘이었다.
36.[백준, 자바] 1149번 - RGB
빨간집은 이전 집이 초록색이거나 파란색일 때 가능하다. 초록집은 이전 집이 빨간색이거나 파란색일 때 가능하다. 파란집은 이전 집이 빨간색이거나 초록색일 때 가능하다.
37.[백준, 자바] 17404번 - RGB2
dp[][]와 data[][]와 paint[]가 필요하다.
38.[백준, 자바] 16194번 - 카드 구매하기 2
왜 i-j를 하냐면, i는 전체 카드팩의 수를 나타내고, j는 현재 사려는 카드팩의 개수이기 때문이다.
39.[백준, 자바] 9095번 - 1,2,3 더하기
먼저 1,2,3을 나타내는 방법을 구해보자. 1 = 12 = 1+1, 23 = 1+1+1, 1+2, 2+1, 3그렇다면 4는?
40.[백준, 자바] 11726번 - 2*n 타일링
나는 머리가 나빠서 손으로 해결하려들기에 또 일일이 다 그렸다.
41.[백준, 자바] 11727번 - 2*n 타일링 2
풀이그림을 그려도 이해가 어려웠다. 일단 1, 2, 3의 경우를 직접 그려봐야 한다.
42.[백준, 자바] 2193번 - 이친수
피보나치 수열이랑 풀이가 똑같다. 처음에 1~N자리의 이친수를 모두 구하는 줄 착각했다가 다시 풀었다. 궁리를 해보니 결국 피보나치였다.
43.[백준, 자바] 2225번 - 합분해
2가지 방법이 있는데, 재귀 함수를 사용해서 푼다. 아님 초기화를 한 다음에 이중 for문으로 처리한다.
44.[백준, 자바] 10799번 - 쇠막대기
)가 나오면 stack.pop()을 하든 변수값을 --하든 해야 한다.이게 왜냐면, ()가 완성되어서 쇠막대기들이 일괄로 잘릴 때도...
45.[백준, 자바] 15990번 - 1,2,3 더하기 5
01,2,3 더하기 시리즈 중 하나인데, 같은 숫자가 2번 이상 연속되면 안된다는 조건이 문제를 더 어렵게 만들었다.
46.[백준, 자바] 9465번 - 스티커
처음 한 생각은 그냥 좌대각선 우대각선 중에 큰 값을 골라서 dp에 저장하면 되지 않을까였다. 물론 안된다.
47.[백준, 자바] 11057번 - 오르막 수
아래 2가지 Action으로 끝낼 수 있다. 2차원 dp를 만들어 1자리수의 경우 1로 초기화한다. ...
48.[백준, 자바] 10844번 - 쉬운 계단 수
풀이오르막 수랑 비슷한 거 같아서 진짜 혼자 풀려고 이 악물었던 문제렷다. 대충 아래처럼 표를 만들어서 점화식을 만들었다.
49.[백준, 자바] 11055번 - 가장 큰 증가하는 부분 수열
이 문제의 경우 기준점을 정하는 것이 중요했다. 이게 알고 나면 굉장히 간단함.
50.[백준, 자바] 2156번- 포도주 시식
개인적으로는 하향식(bottom-up)을 선호한다. 포도주를 마시기 위한 3가지 조건을 잘 알아야 하는데, 하나도 모르겠어서 난항을 겪었던 문제.
51.[백준, 자바] 11055, 11722, 11054 - 수열 기초 시리즈
이번에는 연관된 수열 문제 3개를 한꺼번에 정리해보겠다.
52.[백준, 자바] 2225번- 합분해
사실 2차원 dp를 선언하고 본인의 왼쪽 값과 위쪽 값을 더한 값으로 본인을 갱신하면 된다. 근데 그 점화식에 도달하기에 실패한 부분;;
53.[백준, 자바] 1932번- 정수 삼각형
위에서부터 왼쪽 대각선 또는 오른쪽 대각선으로 내려오면서 최댓값을 구하는 케이스다. 같은 층을 선택할 수 없다. 이 문제는 전형적인 dp로서 RGB류의 문제가 생각이 났다.
54.6월 3주차 - 탐욕 [백준, 자바] 1542번: 잃어버린 괄호
수학을 못해서인지 괄호를 칠 수 있는 범위를 잘못 생각했다. 난 단지 괄호랑 숫자를 한 페어로 생각해서 돌아갈 거라고 생각했는데~ 55-(50+40)결론적으로 덧셈끼리 먼저 계산해야 한다.
55.6월 3주차 - 탐욕 [백준, 자바] 11399번: ATM
Arrays.sort() 또는 Counting Sort 알고리즘을 써서 배열을 정렬해서 이중 for문으로 본인 + 이전 값들 더하면 끝
56.6월 3주차 - 탐욕 [백준, 자바] 11047번: 동전 0
국룰 탐욕 알고리즘 문제. ATM과 마찬가지인 방법으로 풀었다.값들이 오름차순으로 정렬되어 있을 때, for문을 돌려서 가장 큰 동전부터 나눈 몫을 count에 더하고, 나머지값으로 기존 K를 갱신했다.
57.6월 3주차 - 탐욕 [백준, 자바] 1931번: 회의실 배정
처음에는 이전 회의실 끝나는 시간이랑 다음 회의실 시작하는 시간만 비교하면 될 것이라고 생각했는데 아님. 일단 회의실 배정 시간을 끝나는 시간이 큰 순으로 정렬을 한다.
58.탐욕 알고리즘 시리즈 1 후기
DP와는 다르게 먼저 어떻게 정렬을 한 다음에 연산을 할 지를 생각해야 했다. 기존 연산 결과를 재사용하지 않는다, 다만 아직도 탐욕스럽게 가장 좋은 방법을 고른다의...
59.백준 탐욕 알고리즘 - 2885, 9082(java)
https://www.acmicpc.net/workbook/view/4380원하는 초콜릿의 개수를 0으로 만들어 가는 과정이라고 생각해야 한다. 열심히 구현했는데 시간 초과가 났다.
60.[leetcode, java] - find-first-and-last-position-of-element-in-sorted-array
백준을 업로드하다 좀 뜸했는데, 그동안 공부 방법에 회의?를 느껴서 더 기초로 내려가고, 참고하는 자료도 기본 3개는 깔았다.
61.[LeetCode, java] - Snapshot Array
특정 배열의 인덱스별로 스냅샷을 생성하는 클래스를 구현하는 문제이다. TreeMap이라는 자료구조가 생소했는는데 이번에 floorEntry() 메서드로 새로 학습했다.
62.[LeetCode, java] - Valid Perfect Square
mid*mid가 num가 동일한지만 체크하면 된다.
63.LeetCode - Two Pointer 문제들 회고
two pointer 알고리즘을 easy, medium을 번갈아 가면서 풀고 있는데 기억해두고 싶은 것들을 간단히 적어보았다.
64.프로그래머스 고득점 Kit (스택과 큐) 요약
스택과 큐 문제를 다시 풀어보면서 템플릿처럼 요약을 했다.
65.자바 오름차순/내림차순 정렬 공식
로직 떠올리기에 더 시간을 들이기 위해서 정렬 코드를 외워보자.
66.DFS랑 BFS
DFS랑 BFS 터득하기
67.6월 3주차 - 탐욕 [백준, 자바] 13305번: 주유소
https://www.acmicpc.net/problem/13305 서브테스크라서 정답/오답이 아닌 부분 정답 결과도 나오는 문제였다. 처음에 로직을 틀려서 오답, 로직만 맞아서 58점, int형에서 long으로 고쳐서 100점을 받았다. 정답률은 낮은데 막상 알게
68.278. First Bad Version
https://leetcode.com/problems/first-bad-version/description/?envType=problem-list-v2&envId=rab78cw1 grind 75의 easy 문제다.
69.57. Insert Interval
https://leetcode.com/problems/insert-interval/?envType=problem-list-v2&envId=rab78cw1
70.56. Merge Intervals
https://leetcode.com/problems/merge-intervals/?envType=problem-list-v2&envId=rab78cw1
71.1. Two Sum
https://leetcode.com/problems/two-sum/?envType=problem-list-v2&envId=rab78cw1 Grind 75의 Easy 문제다.
72.프로그래머스 기초 입문 - java로 대소문자 처리하기
알파벳으로 대소문자를 핸들링하면서 필요한 자바의 Character 메서드를 정리했다.
73.프로그래머스.H-index
https://school.programmers.co.kr/learn/courses/30/lessons/42747
74.프로그래머스.특이한 정렬
https://school.programmers.co.kr/learn/courses/30/lessons/120880간만에 접근법에 도달한 문제였다.
75.프로그래머스.피자나눠먹기
https://school.programmers.co.kr/learn/courses/30/lessons/120815문제를 어떻게 풀어야 하는지는 파악했지만 최소공배수를 구하는 공식을 몰라서 이 부분만 gemini를 이용해서 정답을 맞췄다.
76.프로그래머스.한 번만 등장한 문자
https://school.programmers.co.kr/learn/courses/30/lessons/120896
77.프로그래머스.직각삼각형 출력하기
https://school.programmers.co.kr/learn/courses/30/lessons/120823
78.프로그래머스.옷가게 할인 받기
https://school.programmers.co.kr/learn/courses/30/lessons/120818
79.프로그래머스.k의 개수
https://school.programmers.co.kr/learn/courses/30/lessons/120887
80.프로그래머스.가까운 수
업로드중..https://school.programmers.co.kr/learn/courses/30/lessons/120890
81.프로그래머스 최댓값 만들기 (2)
https://school.programmers.co.kr/learn/courses/30/lessons/120862
82.프로그래머스 잘라서 배열로 저장하기
https://school.programmers.co.kr/learn/courses/30/lessons/120913
83.프로그래머스 진료순서 정하기
https://school.programmers.co.kr/learn/courses/30/lessons/120835
84.프로그래머스 7의 개수
https://school.programmers.co.kr/learn/courses/30/lessons/120912
85.프로그래머스-문자열 계산하기
https://school.programmers.co.kr/learn/courses/30/lessons/120902구조는 맞췄으나 마지막에 temp의 남은 몫에 대한 계산이 없어서 틀린 문제다.if문은 대략 다음과 같다. 캐릭터가 숫자인 경우 캐릭터가 ' '인
86.프로그래머스 - 외계행성의 나이
https://school.programmers.co.kr/learn/courses/30/lessons/120834여기서 숫자를 알파벳으로 변형하는 공식을 외우면 좋다. v는 1,2,3....과 같은 숫자를 의미한다. (char)('a' + v) // 소문자로
87.프로그래머스 - 개미 군단
https://school.programmers.co.kr/learn/courses/30/lessons/120837거스름돈 문제와 완전히 똑같은 문제다. 시간이 오래 걸린 포인트는 while문의 >= 부분이었다. \>=를 써야 정확하게 “딱 나누어 떨어지는 경
88.프로그래머스 - 공 던지기
https://school.programmers.co.kr/learn/courses/30/lessons/120843이 문제를 보는 순간 요세푸스 문제가 떠올랐다. 배열의 최소 길이는 2 이상을 보장하니 queue에 다 집어넣고 k-1번만큼 2개씩 뽑았다. 그러
89.프로그래머스 - 2차원으로 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/120842
90.프로그래머스 - 자릿수 더하기
https://school.programmers.co.kr/learn/courses/30/lessons/120906기존의 나였다면 개별로 쪼개서 다시 StringBuilder를 사용해서 int로 바꿔는 등 더 복잡하게 처리했겠지만 이번에는 char를 이용해서
91.프로그래머스 - 주사위의 개수
https://school.programmers.co.kr/learn/courses/30/lessons/120845일단 그림을 그려봤다. 상자 가로가 10이고 주사위 가로가 3일 때 10 / 3 = 3이니까 3이다. 상자 세로가 8이고 주사위 가로가 3일 때
92.프로그래머스 - OX퀴즈
http://school.programmers.co.kr/learn/courses/30/lessons/120907이번에도 그림을 먼저 그려봤다. 계산식의 정답 유무에 따라서 O 또는 X를 정답 배열에 채우는 문제인데, 항상 x,y, expected가 1개로 고
93.프로그래머스 - 컨트롤 제트
https://school.programmers.co.kr/learn/courses/30/lessons/120853바로 전에 더했던 숫자를 뺀다는 말을 이해하는 데 시간이 걸렸다. 꼬아서 생각해서 길을 돌아간 듯 하다. 여하튼 문자열과 정수형의 형변환을 제대로
94.프로그래머스 - 직사각형 넓이 구하기
https://school.programmers.co.kr/learn/courses/30/lessons/120860처음에는 단순하게 x1과 x2의 x축 거리의 차이와 x2와 x3의 y축 차이를 곱하면 되지 않을까 하고 코드를 작성했다. 그랬더니 샘플케이스만 통
95.프로그래머스 - 암호 해독
https://school.programmers.co.kr/learn/courses/30/lessons/120892군 전략가 머쓱이는 전쟁 중 적군이 다음과 같은 암호 체계를 사용한다는 것을 알아냈습니다.암호화된 문자열 cipher를 주고받습니다.그 문자열에서
96.프로그래머스 - 외계어 사전
https://school.programmers.co.kr/learn/courses/30/lessons/120869dic과 spell 모두 중복된 원소를 갖지 않는다. 1 ≤ dic의 크기 ≤ 101 ≤ dic의 원소의 길이 ≤ 10 (규모가 작음을 알 수 있
97.프로그래머스 - 369게임
https://school.programmers.co.kr/learn/courses/30/lessons/120891입출력 예 설명입출력 예 3은 3이 1개 있으므로 1을 출력합니다.입출력 예 29423은 3이 1개, 9가 1개 있으므로 2를 출력합니다.3,6,
98.프로그래머스 - 구슬을 나누는 연습
https://school.programmers.co.kr/learn/courses/30/lessons/120840내 수학은 초등학교에서 멈췄는데... 그게 중요한 건 아니고. 이 문제는 완전탐색이 아니라 정석적인 조합(combination) 문제다. 결국 구
99.프로그래머스 - 삼각형의 완성 조건(2)
https://school.programmers.co.kr/learn/courses/30/lessons/120868👉 정수 범위 개수 구하기✅ 기본형: L ≤ x ≤ R → 개수 = R - L + 1✅ 너 문제처럼 (부등호 strict): L < x
100.프로그래머스 - 이진수 더하기
https://school.programmers.co.kr/learn/courses/30/lessons/120885주어진 두 이진수를 10진수로 변환해서 정수형 sum을 만들고 그걸 다시 이진수 문자열로 반환하는 문제다. 로직은 어렵지 않지만 자바 메서드는 꼭
101.프로그래머스 - 숨어있는 숫자의 덧셈(2)
https://school.programmers.co.kr/learn/courses/30/lessons/120864숫자가 아니면 더하지 않는다. 숫자라면 다음이 숫자가 아닐 때까지 sb를 사용해서 합친 후 더한다. 마지막에 sb가 남아있는지 확인하고 남아 있으
102.프로그래머스 - 영어가 싫어요
https://school.programmers.co.kr/learn/courses/30/lessons/120894내 풀이대로 가려면 v 변수는 널을 대비하여 Integer로 가야 한다. 반복문을 뭘 쓸지 고민했으나 단순 for문으로 충분하다 생각하여 그리 했
103.프로그래머스 - 배열 회전시키기
https://school.programmers.co.kr/learn/courses/30/lessons/120844배열을 왼쪽 또는 오른쪽으로 1칸씩 회전시킨 배열을 반환하는 문제이다. 이 문제는 요소를 push하는 것이 아닌 pull하는 코드를 짜야 한다.
104.프로그래머스 - 캐릭터의 좌표
https://school.programmers.co.kr/learn/courses/30/lessons/120861이 문제의 핵심은 내가 중앙에 있다는 것이다. 그래서 절반만 이동해도 4방향 끝단에 도달할 수 있기 때문에 사전에 limit을 걸어야 한다.3개