알고리즘
1.[알고리즘] - 기초(1~50)
오늘부터 파이썬 기초부터 시작해서 알고리즘 공부를 하려고 한다.
2.[알고리즘] - 기초(51~90)
오늘까지 프로그래밍 기초 문제를 풀었다. 내일 부터는 알고리즘 공부를 하면서 백준 문제를 풀 예정이다.
3.[알고리즘] - 그리디
최적의 해에 가까운 값을 구하기 위해 사용여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식근사치 추정에 활용반드시 최적 해 X최적 해에 가까운 값을 구하는 방법 중의 하나
4.[알고리즘/백준] 2839번 : 설탕 배달(python)
5.[알고리즘/백준] 11399번 : ATM(python)
...
6.[알고리즘/백준] 11047번 : 동전 0(python)
동전 금액을 내림차순으로 정렬해서 비교하는게 맞다고 생각했다.
7.[알고리즘/백준] 1931번 : 회의실 배정(python)
처음 생각2차원 배열로 만들고 시작 시간으로 정렬 후 처음 들어오는 회의는 전체 회의의 (제일 마지막에 끝나는 시간 - 제일 처음 시작하는 시간) / 2 보다 작아야 한다 라고 생각을 했다... 근데 손코딩으로 도저히 불가능해서 1시간 고민 후 답을 보았다.한번에 조건
8.[알고리즘/백준] 1026번 : 보물(python)
정말 간단하게 풀었다. a를 미리 정렬하고 for 문으로 a를 하나씩 꺼내온다. b는 가장 큰 것만 가져와서 곱해주고 결과에 더한 후 곱했던 수를 remove로 삭제한다
9.[알고리즘/백준] 1541번 : 읽어버린 괄호(python)
내가 생각한 방법은 -를 만나면 괄호를 바로 열고 괄호 안의 값이 최대가 되도록 해준다는 방법이다...\-를 만나면 괄호를 시작하고 다음 -를 만나면 괄호를 닫는다.
10.[알고리즘/백준] 1541번 : 거스름돈(python)
!\[](https://images.velog.io/images/y7y1h13/post/a9a4f389-2548-4d87-9ac4-b6ed5ea87276/image.png이건 쉬운 문제이다. 그냥 기본적인 그리디 알고리즘 문제.가장 큰 동전을 최대한 많이 준다
11.[알고리즘/백준] 2217번 : 로프(python)
최소공배수를 구하는 문제라고 생각했다. 3개중에 두개만 사용해도 괜찮으니까 비교했을때 최소공배수가 가장 큰게 무개라고 생각했다.
12.[알고리즘/백준] 10162번 : 전자레인지(python)
굉장이 쉬운문제인데 막 풀었다가 엄청 틀렸다.처음에 생각은 마지막 남은 숫자가 0이 아니면 -1을 출력하는것다음에 해본건 미리 10으로 나눠서 0이 아니면 -1을 출력이게 조금 더 빠르다\`n = int(input())ans = \[]for i in (300, 60,
13.[알고리즘/백준] 10610번 : 30(python)
30의 배수는 0이 무조건 있어야한다.3의 배수는 각 자리를 다 더해서 3의 배수
14.[알고리즘/백준] 1789번 : 수들의 합(python)
처음 수에서 1부터 뺴주면 된다고 생각했다. 마지막 수가 작거나 같으면 출력.
15.[알고리즘/백준] 1946번 : 신입 사원(python)
서류 순위로 정렬을 하고 서류 1순위의 면접 순위보다 높은 사람이 있으면 합격한다고 생각했다.하지만 이렇게 하면 답이 안나온다...면접 순위가 더 높은 사람이 있으면 현재 값을 더 높은 사람의 값으로 바꾸고 계속 비교를 진행해야 한다.처음에는 그냥 input()으로 받
16.[알고리즘/백준] 15903번 : 카드 합체 놀이(python)
매번 가장 작은 두 수를 더한다고 생각했다.다른 풀이를 찾아보니 우선순위 큐를 이용하면 된다고 한다.
17.[알고리즘/백준] 11497번 : 통나무 건너뛰기(python)
ㅇㅇ
18.[알고리즘/백준] 11501번 : 주식(python)
처음에는 앞에서 부터 비교한다고 생각했다.이렇게 하면 답이 안나온다... 시간초과도 나고...그래서 생각을 바꿔서 뒤에서 부터 제일 큰 수를 가지고 하나씩 빼서 결과에 더하자고 생각했다.
19.[알고리즘/백준] 9009번 : 피보나치 (python)
미리 피보나치를 구해서 리스트에 저장 후 가장 큰 피보나치부터 가져와서 비교 후 원래 값에서 빼주는 형식으로 구현.이제는 함수로 구현하려고 함...
20.[알고리즘/백준] 1052번 : 물병(python)
21.[알고리즘/백준] 2798번 : 블랙잭(python)
3중 for문을 써서 풀었다...찾다보니 python에 itertools모듈의 combinations 함수가 있었다.알아서 순열을 만들어 준다.
22.[알고리즘/백준] 2231번 : 분해합(python)
수 하나와 각 자리수를 더하면 되는데 나는 1부터 다 하면 너무 비효율적이라고 생각했다. 그래서 주어진 수를 2로 나누어서 해야한다고 생각함.
23.[알고리즘/백준] 2309번 : 일곱 난쟁이(python)
순열을 이용해서 풀었다. 두개씩 짝지어서 sum(전체) - sum(순열) = 100 이면 답이라고 생각함...
24.[알고리즘] - bfs 구현
25.[알고리즘/백준] 16173번 : 점프왕 쩰리bfs(python)
bfs 문제이다... 처음 bfs 문제를 풀어봐서 바로 답을 보고 한 단계씩 따라서 갔다.
26.[알고리즘/백준] 1388번 : 바닥 장식(python)
가로 세로 따로 비교했다.
27.[알고리즘/백준] 2606번 : 바이러스(python)
기본 bfs로 풀었다. bfs 구현이 가능하면 풀린다.
28.[알고리즘/백준] 14562번 : 태권왕(python)
간단하게 bfs로 풀면 된다. 두가지 경우를 다 큐에 넣고 답이 나올때 까지 돌리면 된다.
29.[알고리즘/백준] 1012번 : 유기농 배추(python)
아직 적응이 안되서 너무 오래 걸렸다...1이면 bfs를 돌려 동서남북 다 검사한다. bfs를 실행할 때 마다 cnt+1
30.[알고리즘/백준] 16173번 : 점프왕 쩰리dfs(python)
이번에는 dfs로 풀었다.
31.[알고리즘/백준] 1260번 : DFS와 BFS(python)
예제는 맞게 나오는데 계속 틀렸다고 나와서 찾아보니 set형은 정렬이 보장되지 않는다는걸 처음 알았다. 따라서 extend부분에서 정렬을 해주었다.
32.[알고리즘/백준] 2667번 : 단지번호붙이기(python)
bfs와 dfs를 구현할 줄 알면 풀린다.dfs 조금 더 빠르다.
33.[알고리즘/백준] 11724번 : 연결 요소의 개수(python)
큐를 이용해서 짜고싶었는데 도저히 방법을 몰라서 재귀로 짰다...
34.[알고리즘/백준] 2748번 : 피보나치 수 2(python)
dp를 이용해서 구하면 된다... 점화식을 생각해야 해서 dp는 어려운듯 하다.
35.[알고리즘/백준] 2839번 : 설탕 배달dp(python)
이번에는 dp로 풀어봤다.
36.[알고리즘/백준] 9625번 : BABBA(python)
dp로 간단하게 구현해서 풀었다.
37.[알고리즘/백준] 1463번 : 1로 만들기(python)
리스트 대신 딕셔너리를 사용해서 값을 찾는 연산 속도를 줄일 수 있다.
38.[알고리즘/백준] 4889번 : 안정적인 문자열(python)
스택을 이용하여 문제를 풀었다.
39.[알고리즘/백준] 1105번 : 팔(python)
자리수를 비교하는게 핵심이다.1\. 자리수가 다르면 0개....
40.[알고리즘/백준] 1049번 : 기타줄(python)
여러가지 경우를 생각해서 풀어야한다.패키지 <= 낱개x6패키지 <= (N%6) \* 낱개
41.[알고리즘/백준] 4673번 : 셀프 넘버(python)
set을 이용하여 푸는 문제이다. 모든 경우의 수를 다 생각해야함.
42.[알고리즘/백준] 1065번 : 한수(python)
1~99까지는 다 한수이기 때문에 더해준다.나머지는 빼기로 비교해서 카운트 해준다.
43.[알고리즘/백준] 14888번 : 연산자 끼워넣기(python)
순열을 이용해서 풀었다.
44.[알고리즘/백준] 2178번 : 미로 탐색(python)
처음에는 count 변수를 두고 풀었는데 그렇게 풀면 주변에 1이 있으면 계속 더해져서 답이 안나왔다. 확실한 길로 갈때만 1을 더해주면 된다.
45.[알고리즘/백준] 1697번 : 숨바꼭질(python)
간단하게 풀린다. 3가지 경우를 계속 계산
46.[알고리즘/백준] 4963번 : 섬의 개수(python)
기본적인 bfs문제이다. 대각선 방향도 고려해야 한다.
47.[알고리즘/백준] 2468번 : 안전 영역(python)
3중 for문을 써도 되나 고민했던 문제다... 이거 거의 한시간 걸렸는데 10분만에 다 풀어놓고 visitedj로 해놔서 계속 못 찾았다... 변수명 신경써서 해야겠다.
48.[알고리즘/백준] 2583번 : 영역 구하기(python)
좌표값을 리스트로 나타내는 작업을 하면 나머지 부분은 dfs로 풀면 쉽다.
49.[알고리즘/백준] 1003번 : 피보나치 함수(python)
0과 1의 개수를 계속 써보니 0과 1도 피보나치였다.
50.[알고리즘/백준] 11726번 : 2xn 타일링(python)
dp는 아직 익숙하지가 않아서 힘들다.... 가로 길이에 주목해서 풀면된다.
51.[알고리즘/백준] 9095번 : 1, 2, 3 더하기(python)
1부터 4까지 계산해보니 점화식을 세울 수 있었다.
52.[알고리즘/백준] 14241번 : 슬라임 합치기(python)
정렬해주고 계산하면 된다...
53.[알고리즘/백준] 17615번 : 볼 모으기(python)
처음에는 감이 안와서 다른 사람들 코드를 참고했다.제일 오른쪽, 왼쪽으로 모으는 경우를 계산하면 된다.
54.[알고리즘/백준] 19539번 : 사과나무(python)
배수를 이용하여 풀면되는 문제이다.다 더한게 3의 배수이면서 //2 > //3 이면 'YES'
55.[알고리즘/백준] 1543번 : 문서 검색(python)
글자 하나씩 가져와서 넣고 안에 해당 글자가 있으면 초기화 한다.
56.[알고리즘/백준] 1002번 : 터렛(python)
처음에는 뭔가 했는데... 여러개의 점이 나온다에서 힌트를 얻었다. 원이 아니면 여러개의 점이 나오기가 불가능!원의 방정식을 사용했다.
57.[알고리즘/백준] 1051번 : 숫자 정사각형(python)
최소가 1이기 때문에 1을 지정해주고 하나씩 늘려가면서 비교한다.SET형을 사용하여 비교하면 편하다.set 안에는 하나의 자료형만 들어가야함
58.[알고리즘/백준] 7568번 : 덩치(python)
하나씩 가져와서 전체랑 비교하면 된다.
59.[알고리즘/백준] 7568번 : 스타트와 링크(python)
combinations를 이용해서 팀을 나누어 풀면 되니다.
60.[알고리즘/백준] 7568번 : 스타트와 링크(python)
combinations를 이용해서 팀을 나누어 풀면 되니다.
61.[알고리즘/백준] 1182번 : 부분수열의 합(python)
combinations를 이용해서 1~ N+1 까지의 조합을 계산해서 풀었다.
62.[알고리즘/백준] 10819번 : 차이를 최대로(python)
처음에는 최대 - 최소 이렇게 생각했는데 틀렸다... 순열을 이용해서 모든 경우를 다 계산해야한다.
63.[알고리즘/백준] 11725번 : 트리의 부모 찾기(python)
1이 시작이기 때문에 1부터 시작해서 bfs를 돌리면 된다.
64.[알고리즘/백준] 1389번 : 케빈 베이컨의 6단계 법칙(python)
모든 경우를 다 더하면 된다.
65.[알고리즘/백준] 1325번 : 효율적인 해킹(python)
방향 그래프로 생각하고 풀면된다.
66.[알고리즘/백준] 1926번 : 그림(python)
간단한 dfs, bfs 문제이다.위에가 bfs 밑에가 dfs 이다.
67.[알고리즘/백준] 1743번 : 음식물 피하기(python)
간단한 bfs, dfs 문제이다
68.[알고리즘/백준] 2210번 : 숫자판 점프(python)
모든 경우를 다 탐색해야 한다. 재귀를 이용하여 나오는 수들을 set에 넣으면 중복이 제거된다.
69.[알고리즘/백준] 1149번 : RGB거리(python)
풀이 방법이 도저히 안떠올라서 다른 사람들 풀이를 참고했다.위에서 하나씩 계산해서 내려가면 된다...
70.[알고리즘/백준] 2579번 : 계단 오르기(python)
처음에는 앞으로 가는 경우만 생각했는데 이미 올라온 경우를 생각해야 하는 문제였다..
71.[알고리즘/백준] 11053번 : 가장 긴 증가하는 부분 수열(python)
이건 set형으로 중복 없애고 풀어보기도 하고 다 해봤는데 계속 틀렸다고 나와서 답을 봤다... LIS를 사용해야 한다고 한다. 새로 하나 배웠다.
72.[알고리즘/백준] 1063번 : 킹(python)
처음에 실버 4라서 엄청 만만해게 봤는데 막상 구현하려니까 너무 어려웠다... 나는 딕셔너리를 사용해서 방향을 다 저장하고 풀었다.
73.[알고리즘/백준] 1120번 : 문자열(python)
문자열을 한칸씩 밀면서 최소값을 구해주면 된다.
74.[알고리즘/백준] 1138번 : 한 줄로 서기(python)
키가 1인 사람부터 주어지기 때문에 반복문을 사용하여 돌려준다. 1의 위치를 찾았으면 순서대로 2 3 4 ... 찾으면 된다.
75.[알고리즘/백준] 1747번 : 소수&팰린드롬(python)
소수이면서 팰린드롬인지 체크하면 된다.
76.[알고리즘/백준] 9663번 :N-Queen(python)
대각선 비교가 중요하다고 생각했다. boardi - boardx == i-x값이 동일하면 대각선에 있다.
77.[알고리즘/백준] 14502번 : 연구실(python)
골드 문제를 풀기 시작한게 오늘이라... 한번에 알고리즘 두개를 써야하는지 몰랐다. 조합과 dfs를 함께 쓰면 풀린다.dfs를 구현할 때 큐, 재귀 둘 다 해봤는데 큐를 구현해서 하는게 훨씬 빨랐다.
78.[알고리즘/백준] 1759번 : 암호 만들기(python)
완전 노가다로 풀었다. 자음 모음을 분리해서 combinations를 갯수별로 해주고 그걸 합쳐서 해결함.
79.[알고리즘/백준] 1759번 : 암호 만들기(python)
완전 노가다로 풀었다. 자음 모음을 분리해서 combinations를 갯수별로 해주고 그걸 합쳐서 해결함.
80.[알고리즘/백준] 15686번 : 치킨 배달(python)
처음에는 dfs와 백트래킹을 써야하는줄 알고 시간을 다 버렸다... 치킨집과 집들을 각각 리스트에 넣는다.치킨집이 최대가 되면 치킨거리가 최소가 된다.따라서 각 리스트를 combinations를 해서 치킨집 한개와 집 여러개의 거리를 구하는 방법으로 풀었다.
81.[알고리즘/백준] 18405번 : 경쟁적 전염(python)
queue에 바이러스 정보를 다 줘야한다. 그러면서 0이 나오면 주변에 있는거로 바꾸고 다시 추가
82.[알고리즘/백준] 7576번 : 토마토(python)
익은 토마토 위치를 따로 저장한다. 저장할 때 위치 및 날짜를 0으로 설정해서 저장.bfs를 돌리면서 주변에 익은 토마토들을 하나씩 큐에 저장. 저장하면서 day+1을 해준다.
83.[알고리즘/백준] 10026번 : 적록색약(python)
처음에 정상인 사람부터 답을 내고 그 다음 R=G로 바꿔서 풀면된다.
84.[알고리즘/백준] 7569번 : 토마토(python)
다른 토마토 문제랑 다르게 높이가 있다. 따라서 3차원 리스트로 풀어야한다.
85.[알고리즘/백준] 2156번 : 포도주 시식(python)
처음에는 마지막 와인을 무조건 마시는줄 알고 풀었다. 하지만 마지막 와인을 마시지 않는 경우도 생각해서 풀어야한다.
86.[알고리즘/백준] 9251번 : LCS(python)
처음에 어떻게 푸는지 몰라서 답을 봤다. 문자를 하나씩 추가하면서 푸는 문제이다.
87.[알고리즘/백준] 2502: 떡 먹는 호랑이(python)
dp랑 브루트포스 둘 다를 이용해야한다.처음 1, 2번째 숫자가 정해져있지 않아서 그 숫자를 찾기위해 브루트포스를 이용하고, 맞는지 확인하는건 dp를 이용한다.
88.[알고리즘/백준] 10828: 스택(python)
모든 명령을 함수로 구현했다. 처음에 input()으로 입력을 받으니 시간초과가 나서 stdin.readline()으로 받으니 해결
89.[알고리즘/백준] 9093: 단어 뒤집기(python)
사실 처음에는 ::-1로 풀려고 했는데 이 문제의 의도는 스택을 익히기 위한 문제로 보여서 스택으로 풀었다.
90.[알고리즘/백준] 9012: 괄호(python)
스택을 이용해서 풀었다. 닫는 괄호가 나오면 스택에 넣고 여는 괄호가 나오면 스택에서 닫는 괄호를 pop 해주었다.
91.[알고리즘/백준] 1874: 스택 수열(python)
스택의 특성을 이해해야 푸는게 가능하다.
92.[알고리즘/백준] 1406: 에디터(python)
처음에는 커서의 위치를 숫자로 주면서 계속 변화시켰다. 그랬더니 시간 초과가 나버린... 고민고민하다가 스택 두개로 구현하면 될 것 같아서 해보았다. 스택을 두 개 준비하고 그 사이에 커서가 있다고 생각한다. 왼쪽으로 커서를 옮기면 왼쪽 스택에서 pop을 하고 오른쪽
93.[알고리즘/백준] 10845: 큐(python)
deque를 이용해서 큐를 만들어서 풀면된다.readline 사용해야 시간초과 안남
94.[알고리즘/백준] 1158: 요세푸스 문제(python)
스택을 이용해서 풀었다. K번째 수이기 때문에 그 앞에 수들을 popleft로 빼고 append로 맨 뒤에 넣어줬다.
95.[알고리즘/백준] 10866 : 덱(python)
간단하게 덱의 기능을 구현하는 문제이다.
96.[알고리즘/백준] 17413: 단어 뒤집기2(python)
다른 방법 말고 큐랑 스택을 이용해서 풀고 싶었다.
97.[알고리즘/백준] 10799: 쇠막대기(python)
처음에는 큐를 이용해서 풀었다. 근데 시간이 너무 오래 걸림... 방법은 '('의 갯수를 저장하고 ()을 만나면 ( 갯수만큼 더해준다. )을 만나면 막대기 한개가 끝난거라 +1을 해준다...나중에 다른 답을 보니 스택으로 풀려있었다.
98.[알고리즘/백준] 17298: 오큰수(python)
스택을 이용하여 풀었다. 처음에는 스택 두개를 이용해서 풀어야하나 생각했는데 그렇게하면 오른쪽에 자기 자신보다 큰게 두개 이상이면 순서를 넘어가 버린다. 그래서 풀이를 참고했는데 인덱스를 스택에 넣어주고 비교해주면 된다고 했다.
99.[알고리즘/백준] 1935: 후위 표기식2(python)
후위 표기식이 뭔지 몰라서 찾아봤다... 스택에 순서대로 넣어주다가 연산자가 나오면 피연산자 두개를 pop해서 계산 후 다시 스택에 넣어주는 방식으로 풀었다.
100.[알고리즘/백준] 1918: 후위 표기식(python)
후위 표기식 2보다 조금 더 어렵다.괄호가 제일 구현하기 어려웠다. 여는 괄호를 방패라고 생각하고 풀면 쉽다. 괄호보다 먼저 들어간 기호들은 괄호가 있는 한 계속 순위가 밀리게 된다.
101.[알고리즘/백준] 10808: 알파벳 개수(python)
여러가지 방법이 있지만 자료구조를 연습하기 위해서 counter를 쓰지않고 스택으로 풀었다.
102.[알고리즘/백준] 10808: 알파벳 찾기(python)
이것도 여러가지 방법이 있지만... 자료구조를 이용해서 풀었다.
103.[알고리즘/백준] 10820: 문자열 분석(python)
EOF때문에 조금 오래 걸렸다..
104.[알고리즘/백준] 2743: 단어 길이 재기(python)
솔직히 파이썬은 len을 쓰면 해결이 된다. 하지만 자료구조를 이용해서 풀었다.
105.[알고리즘/백준] 11655: ROT13(python)
자료구조를 이용해서 풀었다.
106.[알고리즘/백준] 10824: 네 수(python)
자료구조를 이용해서 풀었다...
107.[알고리즘/백준] 11656: 접미사 배열(python)
자료구조를 이용했다. 하나씩 pop(0)을 해주면서 남아있는 문자들을 리스트에 추가했다.
108.[알고리즘/백준] 2609: 최대공약수와 최소공배수(python)
유클리드 호제법을 사용하면 된다고 한다. 처음 알았다...
109.[알고리즘/백준] 1934: 최소공배수(python)
두 수의 곱 / 최소공약수를 해주면 된다.파이썬 gcd를 이용하는게 편함.
110.[알고리즘/백준] 1978: 소수 찾기(python)
소수 판별하는 함수를 만들어서 풀었다.약수의 존재 원리(?)를 이용해서 풀면 더 빠르게 해결 가능하다.예를 들어서 설명하자면,25의 약수는 1, 5, 25이다.이는 다음과 같이 앞뒤로 짝을 지을 수가 있다.1 x 25 = 255 x 5 = 2525 x 1 = 251과
111.[알고리즘/백준] 1929: 소수 구하기(python)
에라토스테네스 체를 사용해서 풀었다.약수를 이용하면 시간을 많이 줄일 수 있다.
112.[알고리즘/백준] 6588: 골드바흐의 추측(python)
일단 에라토스테네스의 체를 이용해서 소수를 다 구한다. 나는 array의 길이만큼 for문을 돌리되, i가 작은 수부터 시작되기 때문에만약 arrayi와 arrayn-i가 둘다 array에 존재할 경우 해당 값을 출력하고 바로 break를 걸었다.
113.[알고리즘/백준] 6588: 팩토리얼 0의 개수(python)
리스트로 변경하여 뒤에서부터 0의 갯수를 체크함
114.[알고리즘/백준] 6588: 팩토리얼 0의 개수(python)
리스트로 변경하여 뒤에서부터 0의 갯수를 체크함
115.[알고리즘/백준] 9613: GCD 합(python)
파이썬의 gcd와 combinations를 사용해서 문제를 풀었다. 두개를 짝지어서 gcd를 구해주면 된다.2중 for문으로 풀어도 되지만 combinations를 쓰는게 더 편함
116.[알고리즘/백준] 11727: 2 x n 타일링 2(python)
1 - |2 - ||, =, ㅁ3 - |||, |=, =|, ㅁ|, |ㅁ4 - ||||, ||=, |=|, =||, ==, ㅁㅁ, ㅁ||, ㅁ=, |ㅁ|, ||ㅁ, =ㅁ이렇게 규칙을 찾으면 된다.dpi - 1 + dpi - 2 \* 2
117.[알고리즘/백준] 11052: 카드 구매하기(python)
p1 = 카드 1장의 가격p2 = 카드 2장의 가격...dp1 = 카드 1장 최고 가격dp2 = 카드 2장 최고 가격...dpi = 카드 i장의 최고 가격만약 4장의 카드를 최고 가격으로 사려면?dp4 - 1 + p1 => 3장의 최고 가격 + 카드 1장의 가격dp4
118.[알고리즘/백준] 16194: 카드 구매하기 2(python)
앞의 문제와 점화식은 같지만 dp의 리스트를 다르게 만들어야 한다.0으로 다 만들면 min을 하면 0값만 들어가게된다. 따라서 각 카드 팩의 값을 깊은 복사를 이용하여 dp에 복사한다.
119.[알고리즘/백준] 15990번 : 1, 2, 3 더하기 5(python)
처음에 몰라서 답을 보았다...아마 점화식을 보면 이해가 안될 것 이다.마지막에 1, 2, 3으로 끝나게 되는데1로 끝나는 갯수, 2로 끝나는 갯수, 3으로 끝나는 갯수1로 끝나면 뒤에 2, 3을 붙일 수 있다. 뒤에 1을 붙이려면 구하려는 수보다 1 작은 수 에서 붙
120.[알고리즘/백준] 10844: 쉬운 계단 수(python)
가지치기를 그리다가 규칙을 발견했다...1차원으로는 도저히 불가능해서 2차원으로 했다.자리수(1) 0 1 1 1 1 1 1 1 1 1자리수(2) 1 1 2 2 2 2 2 2 2 1자리수(3) 1 3 3 4 4 4 4
121.[알고리즘/백준] 2193: 이친수(python)
길이 1 2 3 4 5개수 1 1 2 3 5이런 규칙을 만족한다.dpi = dpi-1 + dpi+1
122.[알고리즘/백준] 14002: 가장 긴 증가하는 부분 수열 4(python)
LIS를 구한 후 max_dp = 가장 긴 증가하는 부분 수열의 길이max_idx = max_dp의 위치l = 가장 긴 증가하는 부분 수열을 담을 리스트이렇게 만들었다.max_idx와 max_dp가 같으면 LIS에 해당하는 수이기 때문에 리스트에 추가해주고 max_id
123.[알고리즘/백준] 1912: 연속합(python)
쉬운 문제인데 40분이나 고민했다...모르겠어서 다 써봤다... \-4를 예로 들면 10까지 가장 큰 합은 10이고, -4까지는 두가지 경우가 있다. 10 -4 / -4즉 자기 자신과 전의 가장 큰 합중에 max값을 구하면 된다.max(dpi-1+ai, ai)
124.[알고리즘/백준] 1699: 제곱수의 합(python)
자기 자신보다 작은 제곱수를 이용하여 푸는 문제이다.1부터 시작하여 자기 자신에서 제곱수를 빼고 해당하는 dp에 +1 해주면 된다.min(dpi, dpi - 제곱수 + 1)
125.[알고리즘/백준] 2225: 합분해(python)
이 테이블을 보면 dpk = dpk-1n + dpkn-1 의 규칙을 보이는걸 알 수 있다.
126.[알고리즘/백준] 15988: 1, 2, 3 더하기 3(python)
1 2 3 4 51 2 4 7 13dpi = dpi-1 + dpi-2 + dpi-3
127.[알고리즘/백준] 1309: 동물원(python)
두개의 방법이 있다.규칙을 찾기0 1 2 3 41 3 7 17 41보면 dpi = dpi-1 \* 2 + dpi-2이런 규칙이 있다.하지만 이렇게 풀면 어려운 dp문제 풀기가 불가능하다.이전 경우를 사용해야한다... 현재 내가 선택할 수 있는 경우는1\. 사자를 넣지
128.[알고리즘/백준] 11057: 오르막 수(python)
마지막에 끝나는 수로 생각해서 풀었다.0으로 끝나려면 이전의 수가 01로 끝나려면 이전 수가 1 이하2로 끝나려면 이전 수가 2 이하...9로 끝나려면 이전 수가 8 이하...경우의 수를 다 더해주면 답이 나온다.ex) dpi = dpi-1 + dpi-1 + dpi-1
129.[알고리즘/백준] 9465: 스티커(python)
0 1 2 3 450 4030 1001번 인덱스는 왼쪽 대각선의 수를 더해준다.그 다음 인덱스 부터는 왼쪽 대각선의 두개의 수 중에 더 큰 수를 더해준다.dp0 = max(dp1, dp1)dp1 = max(dp0, dp0)
130.[알고리즘/백준] 11054: 가장 긴 바이토닉 부분 수열(python)
max를 이용해서 풀면 답 안나온다.맨 앞에서 LIS를 적용 시키고, 뒤집어서 적용 시켜준다.그리고 두개를 합쳐주면 되는데... 뒤집어서 계산 했던거는 인덱스가 반대로 들어간다. 따라서 다시 뒤집어서 더해주면 된다.
131.[알고리즘/백준] 13398: 연속합 2(python)
기존 연속합과 하나를 제거한 연속합을 비교하면 된다.dp0는 제거하지 않고 구하는 연속합dp1는 제거하고 구하는 연속합dp1 = max(dp0, dp1 + ai)현재 숫자를 제거한 수와, 기존 숫자를 제거한 수 중에 큰 수를 고른다.
132.[알고리즘/백준] 3085: 사탕 게임(python)
모든 경우를 다 돌아야한다...처음에는 N-1경우로 놓고 풀었더니 마지막줄이 경우로 들어가지 않았다...행의 i+1이 N을 넘어가면 바꾸지않고 열의 i+1이 N을 넘어가면 바꾸지 않는게 핵심이다...
133.[알고리즘/백준] 1476: 날짜 계산(python)
받은 리스트와 같으면 종료시키고 답을 출력
134.[알고리즘/백준] 1107: 리모컨(python)
처음에는 permutations를 이용해서 풀려다가 실패했다...숫자를 0부터 다 체크해야한다. 만약 고장난 숫자라면 패스하고 고장난 숫자가 없으면 그 숫자로 계산을 한다.1000000을 하는 이유는 채널이 500000인데 숫자는 9까지 있으므로 만약 9를 제외하고 나
135.[알고리즘/백준] 1748: 수 이어 쓰기 1(python)
규칙을 찾아서 풀어야한다.1~9 -> 910~99 -> 90 2100~999 -> 900 3자세히보면 9 (10^자릿수) (자릿수)N의 길이를 저장한다.l은 N의 길이이다. l에서 1을 빼주어야한다.왜냐하면 만약 N이 5이면 l은 1이 들어온다.1은 10의 자리
136.[알고리즘/백준] 15649: N과 M(1)(python)
백트래킹을 이용해서 푸는 문제이다.재귀를 사용
137.[알고리즘/백준] 15650: N과 M(2)(python)
이번에는 오름차순으로 구해야하기 때문에 dfs에 현재 수를 준다.
138.[알고리즘/백준] 15651: N과 M(3)(python)
여러개를 골라도 되기 때문에 if문을 제거해주면 된다.
139.[알고리즘/백준] 15652: N과 M(4)(python)
이번에는 if문을 없애고 dfs에 현재 숫자도 줘야한다.
140.[알고리즘/백준] 15654: N과 M(5)(python)
수를 받아서 정렬을 해야한다.정렬 후 그 수로 백트래킹 실행
141.[알고리즘/백준] 15655: N과 M(6)(python)
현재 수를 주고 백트래킹 실행
142.[알고리즘/백준] 11048: 이동하기(python)
이전의 왼쪽, 오른쪽, 대각선 칸들 중 가장 큰 수를 찾고 현재 칸의 수를 더한다.dpi = max(dpi-1, dpi, dpi-1) + 현재 수
143.[알고리즘/백준] 15656: N과 M(7)(python)
이번에는 중복이 가능하기 때문에 길이만 체크 해준다.
144.[알고리즘/백준] 15657: N과 M(8)(python)
백트래킹을 수행할 때 현재 숫자를 줘야한다.
145.[알고리즘/백준] 18290: NM과 K(1)(python)
2차원 백트래킹 문제이다. visited 리스트를 만들어 풀어도 되지만...2중 for문을 이용하여 하나씩 탐색한다. 오른쪽, 아래로만 이동하게 만들어 간단하게 만들었다.또한 넘겨주는 값에 합과 깊이를 함께 넘겨줬다.
146.[알고리즘/백준] 14501번 : 퇴사(python)
두가지 경우로 나누어서 풀면 된다. 선택하는 경우, 선택 안하는 경우선택을 하지 않으면 날짜에서 +1을 해준다.선택을 하면 day+소요날짜를 더한게 N보다 작으면 백트래킹 실행'==' N인 이유는 7일이 되면 계산하기 위해서
147.[알고리즘/백준] 7562번 : 나이트의 이동(python)
너비 우선 탐색을 이용한다... 이유는 넓게 퍼져가면서 최소를 찾아야 하기 때문bfs 한 단계 마다 +1을 해준다. 먼저 도착하면 출력
148.[알고리즘/백준] 13913번 : 숨바꼭질 4(python)
숨바꼭질 1에서 이동했던 위치를 기록해줄 리스트 하나를 더 만들어준다.위치에 도달하면 기록했던 리스트를 하나씩 가져와 역순으로 출력한다.
149.[알고리즘/백준] 11060번 : 점프 점프(python)
처음에 dp리스트를 만들 때 숫자를 지정해 주었다.N으로 만들어준 이유는 만약 N이 입력이 되면 최대 점프 횟수는 N-1이기 때문이다.만약 i + j가 N보다 작으면 dpi+j = min(dpi + 1, dpi + j)dpi + 1은 한칸만 가는 방법이고 dpi + j
150.[알고리즘/백준] 2529번 : 부등호(python)
0부터 시작하기 때문에 처음에 if문에 걸리는 수가 가장 작은 수이다. 그 다음에 계속해서 나오는 수들은 점점 커지기 때문에 계속 MAX를 갱신.총 세가지 경우로 나누었는데...1\. 아무 숫자도 선택이 안되어 있는 경우2\. 숫자가 들어있고 부등호가 <3\. 부
151.[알고리즘/백준] 14226번 : 이모티콘(python)
bfs를 이용해서 풀었다.세가지 경우를 모두 q에 추가해 주었다.만약 방문했으면 넘어갔다.
152.[알고리즘/백준] 10942번 : 팰린드롬?(python)
처음에는 dp로 어떻게 풀어야하는지 막막했다.여기서 팰린드롬의 경우의 수는 총 3가지 이다.1\. 길이가 1인 경우2\. 시작과 끝이 같고 가운데가 팰린드롬인 경우3\. 시작과 끝이 같고 길이가 2인경우이렇게 세가지 경우에 관해서만 dp에 1을 추가해준다.for문에서
153.[알고리즘/백준] 10972번 : 다음 순열(python)
permutation으로 풀면 시간초과가 난다. O(N!)임...규칙을 찾아야 한다.예를 들면3 2 4 13 4 1 23 4 2 14 1 2 3이라고 하면제일 오른쪽부터 시작한다. 만약 지금 수가 그 다음 수보다 크면 인덱스를 저장하고...다시 for문을 돌린다3 2
154.[알고리즘/백준] 10973번 : 이전 순열(python)
다음 순열 문제랑 완전 반대이다.이전 수가 다음 수 보다 크면 맨 뒤에서 부터 자기보다 큰 수를 찾아야한다.또한 정렬은 큰 수 부터 정렬이 되게 해야함.
155.[알고리즘/백준] 10974번 : 모든 순열(python)
permutation을 쓰면 금방 풀린다. 하지만 배우는 의미가 없음dfs를 이용했습니다. 하나씩 추가해서 길이가 n이 되면 그걸 출력했습니다.for문을 사용하여 0부터 n까지 돌렸고 +1한걸 visited에 추가했습니다.visited의 길이는 n의 길이와 똑같기 때문
156.[알고리즘/백준] 13549번 : 숨바꼭질 3(python)
처음에 시간이 다 1이 느는줄 알았다... 하지만 나중에 보니 순간이동은 시간이 늘지 않았다.가중치가 0, 1로 이루어져 있으면 0-1bfs를 사용하면 된다.만약 가중치가 여러개면 다익스트라를 사용가중치가 0인 계산이 들어오면 appendleft를 이용해서 큐 맨 앞에
157.[알고리즘/백준] 15989번 : 1, 2, 3 더하기 4(python)
1로 만드는 경우는 전체가 한가지...2로 만드는 경우는 dpi-23으로 만드는 경우는 dpi-3다 더해주면 답
158.[알고리즘/백준] 10971번 : 외판원 순회 2(python)
permutation으로 풀면 시간 초과가 난다.백트래킹으로 풀었다.처음 번호, 현재 번호, 합, 갯수를 넘겨주었다.만약 갯수가 N과 같다면 제일 마지막 도시이기 때문에 처음 도시로 가는 비용을 추가하고 작은지 큰지 비교한다.
159.[알고리즘/백준] 1261번 : 알고스팟(python)
bfs문제이다.0 or 1의 가중치를 가지고 있기 때문에 0-1bfs를 이용하여 풀면 된다.왜 -1로 만들어야 하는지 이해가 가지 않았는데 디버깅을 해보니 가중치가 0 or 1이기 때문에 계속 0이 나오게 된다. 그래서 -1로 만들어 주었다.
160.[알고리즘/백준] 6603번 : 로또(python)
순열을 사용해서 풀었다.맨 앞 숫자는 빼고 만들어야 한다. 1:
161.[알고리즘/백준] 11723번 : 집합(python)
시간을 줄이기 위해서 꼭 readline()을 써야한다. 안쓰면 시간초과 나옴...python에서 집합은 set()을 사용하면 된다.또한 discard(x)는 만약 x가 집합 안에 있으면 삭제하고 없으면 무시하고 넘어간다.remove(x)를 쓰면 x가 집합 안에 없으면
162.[알고리즘/백준] 14391번 : 종이 조각(python)
비트마스킹 개념을 잘 몰라서 너무 힘들었다.처음에는 그냥 N자리를 가지면 그 수가 가장 크다고 생각했다. 하지만 예외도 있었다.비트마스킹을 사용하려면 2차원을 1차원으로 바꿔야한다.나는 가로를 1 세로를 0으로 두고 했다.만약에 1111 0000 0000 0000 이면
163.[알고리즘/백준] 16926번 : 배열 돌리기 1(python)
큐를 이용해서 풀었다.기준을 잡아서 기준을 따라 겉을 한 바퀴 돌면 큐에 다 들어가게 되고 그걸 rotate로 밀어주면 된다.0,0 -> 1,1 -> 2,2... 처음 시작은 항상 이렇게 해주었다.만약 -2를 계속 빼서 0이 나오면 마지막이기 때문에 그만했다.
164.[알고리즘/백준] 14225번 : 부분수열의 합(python)
여러가지 방법이 있다.처음에는 combinations를 사용하여 풀었다.두번째 풀이는 1씩 증가하면서 다음 수가 더 크면 현재 수가 가장 작은 수..
165.[알고리즘/백준] 16929번 : Two Dots(python)
문제dfs를 이용하여 경우를 탐색한다.만약 처음 시작점과 현재 탐색점이 같고 4개 이상이면 yes를 출력한다.
166.[알고리즘/백준] 1495번 : 기타리스트(python)
처음에 백트래킹으로 풀었다가 틀렸다...곡과 점수로 dp 리스트를 만들어야 한다.각 곡별로 0 ~ M까지의 점수를 받을 수 있기 때문에 리스트를 만들고 0으로 초기화한다.처음은 dp0이다. 왜냐하면 맨 처음에 S로 시작하기 때문이다.dpi-1 == 1이면 계산을 해준다
167.[알고리즘/백준] 15658번 : 연산자 끼워넣기(2)(python)
백트래킹을 이용해서 푸는 문제이다. 처음에는 연산자 부분에 for문을 넣어서 풀었는데 생각해보니 어짜피 +부터 처리할텐데 for문을 쓰지않고 if문을 + -> - -> \* -> / 이 순으로 넣으면 된다...
168.[알고리즘/백준] 16947번 : 서울 지하철 2호선(python)
순환선을 찾으려면 dfs를 사용하고거리를 찾으려면 bfs를 사용하면 된다.순환선은 dfs를 계속 실행하다가 다시 시작점으로 돌아오면 순환선이라고 한다.단 조건이 있다. 1-2-1은 순환선이 아니지만 자기 자신으로 돌아온다. 따라서 역을 2개이상 포함해야 한다.거리는 순
169.[알고리즘/백준] 12869번 : 뮤탈리스크(python)
dp를 3차원 리스트로 만들어서 풀었다. 61개를 만들지 않고 받는 체력중에 가장 큰 체력으로 리스트를 만듦...permutations를 사용하여 9, 3, 1을 조합했다. 계속해서 빼다가 세 수가 0이하로 내려가면 return을 해줌...만약 scv가 3마리가 아니면
170.[알고리즘/백준] 16197번 : 두 동전(python)
bfs풀면 된다고 생각했다.방문을 어떻게 처리해야하나 고민했는데 생각해보니 어짜피 10을 넘어가면 -1을 출력할거라 딱히 상관이 없었다.
171.[알고리즘/백준] 10422번 : 괄호(python)
처음에는 뭔가 싶었다... 카탈란의 수 라는걸 쓰라고 하는데 이런거 쓰기 싫어서 그냥 dp로 풀려고 계속 해봤다.전체를 N이라고 하면무작위의 위치에 여는 괄호 하나가 나왔다고 하자. 그리고 그 괄호를 닫는 괄호의 위치를 i라고 하면괄호 사이에 들어가 있는 괄호의 갯수는
172.[알고리즘/백준] 16198번 : 에너지 모으기(python)
구슬 하나를 없애고 양 옆 수를 곱해서 더하면서 풀면 된다.백트래킹을 사용했다.만약 길이가 2이면 두개를 곱하고 더 큰걸 저장한다.
173.[알고리즘/백준] 2293번 : 동전 1(python)
다차원 리스트로 풀려고 했는데 너무 리스트가 커져서 다른 방법으로 풀었다.1로 만드는 경우2로 만드는 경우... 이런 식으로 나눠서 풀었고...만약 1과 2로 3을 만들려면111/ 1+2 이렇게 만들면 된다.이 경우는 1로 3을 만드는 경우에 2로 만드는 경우를 추가한
174.[알고리즘/백준] 2580번 : 스도쿠(python)
가로 세로 9칸을 다 검사한 후 통과하면 넣어주었다. 만약 틀리면 백트래킹을 이용해서 다시 되돌아 왔다.
175.[알고리즘/백준] 2294번 : 동전 2(python)
이전의 코인에 +1을 하는 경우와, 자기자신이 가장 작은 경우로 나눠서 작은걸 선택하면 된다.
176.[알고리즘/백준] 2003번 : 수들의 합(python)
이 문제는 투포인터를 이용한 문제이다.s, e라는 변수를 인덱스로 이용하여 푼다.sum(as:e) > M -> s += 1sum(as:e) < M -> e += 1sum(as:e) == M -> ans += 1e가 끝에 도달하면 s만 계속해서 1씩 더해준다.
177.[알고리즘/프로그래머스] KAKAO - 신고 결과 받기(python)
딕셔너리 한개로 풀었다.딕셔너리를 이름 : 0으로 초기화 시켜준다.맨 앞 숫자는 신고를 당한 횟수이다. 뒤에 신고한 사람의 이름을 넣어준다.처음 for문으로 딕셔너리를 0으로 만들어 준다.두번째 for문으로 신고당한 횟수, 신고한 사람의 이름을 넣어준다.세번째 for문
178.[알고리즘/프로그래머스] KAKAO - 숫자 문자열과 영단어(python)
replace함수를 사용해서 풀었습니다.
179.[알고리즘/백준] 16928번 : 뱀과 사다리 게임(python)
그냥 bfs쓰면 쉬운 문제이다.뱀, 사다리 두가지를 리스트로 만들려고 했지만 그럴 필요가 없다.만약 리스트안에 있으면 해당 숫자로 바꿔주고 그 숫자가 방문한 숫자이면 가지말자.
180.[알고리즘/백준] 1806번 : 부분합(python)
투포인터로 풀었다... 카카오 인턴 코테에서 배운걸 잘 써먹는 중이다.인덱스를 계속 옮기면서 합을 구하고 길이를 저장한다.
181.[알고리즘/백준] 16948번 : 데스 나이트 (python)
최소를 찾는 문제이기 때문에 bfs를 이용했다. 방문체크를 해주면서 계속 가면 된다.
182.[알고리즘/백준] 11058번 : 크리보드(python)
dp문제인데 왜 붙여넣기가 최대 3번인지 모르겠어서 찾아보다가 증명한걸 보았다.블로그 여기서 참고했다...
183.[알고리즘/백준] 1644번 : 소수의 연속합(python)
에라토스테네스의 체와 투포인터를 이용하여 풀었다.처음에 소수들을 리스트에 저장하고 투 포인터로 인덱스를 옮겨가면 합을 구했다.
184.[알고리즘/백준] 13458번 : 시험 감독(python)
총감독관은 1명이 무조건 있어야하기 때문에 학생수에서 총감독관을 빼준다.만약에 학생수가 0 이하라면 다음 수로 넘어간다.
185.[알고리즘/백준] 14503번 : 로봇 청소기(python)
주어진 조건에 맞게 하나씩 구현하면 된다.왼쪽이 비어있으면 그대로 for문을 종료시키고 진행함.왼쪽 회전을 할 때 공식을 찾아봤는데 (d + 3)% 4 이런 공식이 있었다!! 이걸 활용해서 풀었다.
186.[알고리즘/백준] 14891번 : 톱니바퀴(python)
문제처음에 문제를 잘못 이해해서 돌리고 나서 다르면 회전시키게 풀었다...처음에 먼저 비교를 한다. 같으면 회전 x 다르면 회전리스트를 생성해서 현재 돌려야하는 톱니에 수를 넣고 다르면 -1을 곱해서 넣어줬다.끝나면 rotate를 이용하여 회전
187.[알고리즘/프로그래머스] - 전화번호 목록(python)
문제문제의 취지는 hash를 사용딕셔너리를 이용하여 키-값으로 만들어 놓는다.사실상 값은 중요하지 않다.키 값을 하나씩 가져온다. 가져온 키 값을 분리하여 한 단어씩 temp에 저장하면서 해당 temp가 딕셔너리에 키로 있는지 확인한다. 만약 temp가 현재 numbe
188.[알고리즘/프로그래머스] - 문자열 압축(python)
문제자르는 경우가 1부터 //2 까지 이다.만약에 자르고 뒤에가 남는다면 이어붙인다.현재 자른 문자열이랑 이전 문자열을 비교해준다. 같으면 +1다르면 현재 몇개가 같았는지 비교하고 a에 추가해준다.최종적으로 min을 사용하여 값을 비교
189.[알고리즘/백준] 3190번 : 뱀(python)
1초씩사과가 없으면 몸 전체 이동2-1. 몸은 deque를 써서 넣어주고 사과 없으면 맨 앞에 빼준다.2-2. 만약 현재 좌표가 deque안에 없으면 넣어주고 있으면 종료사과가 있으면 deque안에 넣어준다.사과 위치는 2차원 리스트를 만들어 1로 표시해준다.(시작 좌
190.[알고리즘/프로그래머스] - 오픈채팅방(python)
문제 enter, change때만 이름을 바꿀 수 있다. 1-1. name딕셔너리를 이용 record를 돌면서 enter 혹은 leave를 만나면 answer에 저장
191.[알고리즘/프로그래머스] - 위장(python)
문제해시문제이다.처음에 딕셔너리로 각각 몇개인지 만들고,headgear는 총 2개 있으니, 스파이에게는 총 3가지의 경우의 수가 있다.1번을 입는다.2번을 입는다.headgear를 아무것도 입지 않는다.eyewear는 총 1개 있으니, 스파이에게는 총 2가지의 경우의
192.[알고리즘/백준] 20055번 : 컨베이어 벨트 위의 로봇(python)
칸 회전(rotate사용)1-1. robot-1 = 0 마지막 로봇 내리기로봇 이동(제일 오른쪽 로복 찾아서)2-1. 벨트 내구도 체크2-2. 로봇 유,무 체크2-3. 마지막 로봇 내리기첫 칸 내구도 체크0 갯수 체크
193.[알고리즘/백준] 16234번 : 인구 이동(python)
bfs를 돌면서 연합을 찾아서 리스트에 저장한다.해당 리스트를 가져와서 인구를 조정한다.만약 리스트가 비어있다면 종료한다.이렇게 풀면 시간 초과가 난다. pypy로 풀었다.... 조금 더 고민해서 python으로 해야지
194.[알고리즘/프로그래머스] - 괄호 변환(python)
문제과정을 함수로 나누어 코딩을 했습니다.u, v로 나누기왼쪽부터 검사하여 괄호 열림, 닫힘 괄호 갯수가 동일하면 그 부분으로 나눈다.올바른 괄호 문자열만약에 큐가 비어있는데 닫는 괄호가 나오면 False열린 괄호가 큐에 들어있고 닫힌 괄호가 들어오면 pop나머지 부분
195.[알고리즘/프로그래머스] - 베스트앨범(python)
문제장르별 플레이 횟수와 음악별 플레이 횟수로 나누었다.장르별 플레이 횟수를 sort하여 for문을 돌린다.곡 별 플레이 횟수를 sort하여 하나씩 answer에 추가한다. 곡당 2개씩... 따라서 cnt를 주고 2이면 break를 해주었다.
196.[알고리즘/프로그래머스] - 뉴스 클러스터링(python)
문제처음에는 정규표현식을 이용하여 영어 알파벳만 골라냈다.그 후 for문을 이용하여 union 및 intersection을 구하였다.더 좋은 방법을 찾았다!isalpha()를 이용하여 알파벳을 찾았다.교집합과 합집합을 구하여교집합의 합은 교집합의 원소를 가져와 coun
197.[알고리즘/프로그래머스] - 기능개발(python)
문제시간을 이용해서 풀었다.처음 시간을 0으로 두고 시간을 speeds에 곱해가면서 100이 넘어가면 해당 숫자를 popleft를 해주고 count를 1 증가
198.[알고리즘/프로그래머스] - 프린터(python)
문제가장 높으면 출력하면서 answer += 1없으면 맨 뒤로 보낸다.deque를 이용하여 popleft사용해서 빼고 append로 넣기
199.[알고리즘/프로그래머스] - 거리두기 확인하기(python)
문제bfs를 이용하여 문제를 풀었다.만약 아무도 앉지 않은 자리이면 q에 추가했다.cnt를 두어 거리를 계산했고, 2를 넘어가면 bfs를 끝냈다.
200.[알고리즘/프로그래머스] - 다리를 지나는 트럭(python)
문제다리의 무게를 sum으로 구하면 시간 초과가 난다.합을 담을 변수를 주고 만약 bridge0이 0이 아니면 빼준다.트럭의 0번째를 s와 더했을 때 무게를 넘지 않으면 bridge에 append 넘으면 그대로
201.[알고리즘/프로그래머스] - 수식 최대화(python)
문제처음 수식을 분리.deque로 만들기permutations를 이용하여 연산자 조합하기큐를 이용하여 연산하기분리했던 연산에서 해당하는 연산자가 나오면 s에 넣었던 가장 마지막 숫자와 현재 k 안에 있는 숫자를 연산해서 s에 넣는다.
202.[알고리즘/프로그래머스] - 주식가격(python)
문제스택 / 큐에 속해있는 문제인데 완전탐색으로 풀어도 효율성에서 통과가 된다...스택으로 풀면 O(n)으로 풀림해석도 엉망
203.[알고리즘/프로그래머스] - 튜플python)
문제문자열을 나누는게 관건인 문제이다.나누고 길이순으로 정렬하고 하나씩 넣는다.
204.[알고리즘/프로그래머스] - 더 맵게(python)
문제heapq를 사용해서 풀어야하는 문제였다.정렬이 자동으로 되기 때문에. while문을 써서 구하면 된다.
205.[알고리즘/프로그래머스] - 순위 검색(python)
문제처음에는 데이터 베이스에 데이터를 넣는것 처럼 하려고 인덱싱을 이용해서 풀었는데 너무 복잡해져서 포기했다.찾다보니 조합 및 이진탐색을 이용해서 푸는것을 보았고 해당 방법으로 풀었다.가져와서 split으로 나눠주기해당 배열을 combinations을 이용하여 조합단어
206.[알고리즘/프로그래머스] - 가장 큰 수(python)
문제cmp_to_key를 사용해서 문제를 풀었다.compare함수를 만든다.6, 10, 2를 예로 들면6, 10이 문자이기 때문에 a + b -> 610b + a -> 106두개를 비교하면 a + b가 더 크기 때문에 1을 반환한다.작으면 -1, 같으면 0을 반환똑같은
207.[알고리즘/백준] 15591번 : MooTube(python)
기본 bfs문제이다.각 경로를 저장해준다.bfs를 이용하여 하나씩 가져오고 만약 K보다 크다면 q에 넣어주고 cnt += 1
208.[알고리즘/프로그래머스] - 타겟 넘버(python)
문제재귀를 이용해서 문제를 풀었다.재귀를 돌면서 만약 cnt가 길이랑 같으면 멈추고 target이랑 비교를 했다.return을 해주면 길이가 1 짧아지고 -로 바뀐다.
209.[알고리즘/프로그래머스] - 프렌즈4블록(python)
문제구현문제이다.1\. 전체를 돌면서 위 아래 대각선이 같은걸 찾는다.2\. 찾은 위치를 1로 바꾼다.3\. 1의 갯수를 센다.4\. 맨 밑 부터 탐색하며 만약 1이면 위에를 내려준다.5\. while을 사용하여 1이 아닐때 까지 감소시키고6\. 바꿔준다.
210.[알고리즘/프로그래머스] - 캐시(python)
문제if문을 사용하여 경우를 세개로 나누어 구현했다.cache안에 현재 도시가 있는 경우cache의 길이가 최대 길이가 아닌 경우cache의 길이가 최대이고 cache 안에 현재 도시가 없는 경우
211.[알고리즘/프로그래머스] - 멀쩡한 사각형(python)
문제규칙을 찾으려고 다 해봤지만 결국 못했다...블로그를 보고 이해해서 풀었다.참고사각형을 직접 그려서 잘라보고...밀어보면 가로 세로 만큼 없어진다유클리드 호제법을 이용해서 최대공약수를 구해서 풀면된다.
212.[알고리즘/프로그래머스] - 124 나라의 숫자(python)
문제1 2 411 12 1421 22 2441 42 44111 112 114121 122 124...이런 방식으로 진행이 된다.자세히 보면 3의 배수이면 끝자리가 4이다.만약에 6을 124로 나타내면6 % 3 = 0\-46 // 3 = 2만약 또 3으로 나눠주면 2가
213.[알고리즘/백준] 18258번 : 큐 2(python)
간단하게 구현하는 문제이다.풀이 방법이 두가지가 있는데1\. 그냥 구현2\. 투포인터 사용
214.[알고리즘/백준] 2164번 : 카드2(python)
큐를 이용하여 문제를 풀었다.
215.[알고리즘/백준] 14425번 : 문자열 집합(python)
python에서 set는 hash table로 구현된다. 원소 판단이 O(1)으로 가능list는 모든 원소를 다 확인 O(N)set or dict를 사용해서 풀면된다.set의 intersection을 사용하면 중복이 없어져서 답이 다르게 나온다.
216.[알고리즘/백준] 1991번 : 트리 순회(python)
재귀를 이용했다.노드를 만들기 위해 딕셔너리를 사용하여 노드를 저장했다.전위 순회는 루트, 왼쪽 자식, 오른쪽 자식순으로 방문한다.만약 왼쪽이 비어있지 않으면 왼쪽 자식을 넣고 재귀를 돌린다.전위 순회는 방문하면 바로 출력한다.더이상 가지 못하면 오른쪽 자식으로 간다.
217.[알고리즘/백준] 1789번 : 수들의 합(python)
이진탐색을 사용하여 풀었다.1부터 N 까지의 합은 N \* (N + 1) // 2N의 최대값은 항상 전체 합 보다 작거나 같다.
218.[알고리즘/백준] 11000번 : 강의실 배정(python)
시작 시간과 끝나는 시간을 비교해서 푸는 문제이다.우선순위 큐를 이용.제일 처음 시간과 비교하여 그 값보다 작으면 강의실을 새로 만들고 크면 강의실을 만들지 않아도 된다.
219.[알고리즘/백준] 11659번 : 구간 합 구하기 4(python)
만약 리스트가 a = 1, 2, 3 이면각 구간의 합은 k = 1, 3, 5 이다.이것을 이용하여 1 - 2의 구간합을 구하려면?k2 - k0의 값이 답이 된다.따라서 k끝 - k시작 - 1
220.[알고리즘/백준] 11660번 : 구간 합 구하기 5(python)
이번에는 2차원 배열에서의 누적합이다.가로, 세로 모두 누적합을 구해준다.더하면 중복되는 부분이 생기는데 해당 부분을 빼주고 두번 빼준 부분을 더해준다.
221.[알고리즘/백준] 20291번 : 파일 정리(python)
(.)으로 나눠주고 딕셔너리로 갯수를 세어준다.
222.[알고리즘/백준] 2470번 : 두 용액(python)
투 포인터 문제이다.두 용액의 합을 절대값으로 바꾸고 비교하면 된다.
223.[알고리즘/백준] 10815번 : 숫자 카드(python)
이진탐색 문제이다.가지고 있는 숫자 카드를 정렬한 후 이진탐색으로 하나씩 찾는다.
224.[알고리즘/백준] 15663번 : N과 M(9)(python)
permutations를 사용하여 풀었습니다.중복 제거는 set을 이용했습니다.
225.[알고리즘/leetcode] Remove Duplicates from Sorted Array(python)
리스트를 추가로 생성하지 말라는 규칙이 있다.(Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory
226.[알고리즘/leetcode] Best Time to Buy and Sell Stock II(python)
for 문을 이용하여 현재 값이 다음 값보다 작으면 두수의 차를 결괏값에 더해준다.
227.[알고리즘/leetcode] Reverse String(python)
투포인터를 이용해서 문제를 풀었다.왼쪽, 오른쪽 끝에서 각각 출발하여 바꾸면서 가운데까지 오면 된다.
228.[알고리즘/leetcode] Delete Node in a Linked List(python)
처음에는 원래 링크드리스트 삭제처럼 처음부터 while 문으로 돌려서 해당 노드가 나오면 node.next = node.next.next 이렇게 해서 지우려고 했다.하지만 이 문제는 헤더를 알려주지 않는 문제였고....억지이긴 하지만 지우는 게 아닌 건너뛴다가 맞는 표
229.[알고리즘/leetcode] Rotate Array(python)
방법이 여러가지이다.알고리즘 문제라서 내가 직접 뒤집기를 만들어서 썼다.만약 k가 리스트의 길이보다 길면 k를 길이로 나눠준다.
230.[알고리즘/leetcode] Maximum Depth of Binary Tree(python)
재귀를 이용해서 문제를 해결했다.이진 트리이기 때문에 두개로 나누어서 재귀를 실행했고 자식 노드가 없는 리프 노트까지 내려가면 1을 더해주었다.최종적으로 왼쪽, 오른쪽 값 중 가장 큰 값을 리턴해줌
231.[알고리즘/leetcode] Contains Duplicate(python)
set자료형을 사용했다. set 자료형은 해시 테이블로 구현되어 있기 때문에 시간 복잡도가 빠르다.리스트 자료형에서 in을 이용하면 값을 일일이 확인하기 때문에 오래 걸린다. 하지만 set의 경우에는 해당 값을 해시 함수에 넣어 인덱스에 접근함으로써, 아주 빠르게 해당
232.[알고리즘/leetcode] Merge Sorted Array(python)
non-decreasing order -> 이거 있으면 sort쓰면 안된다. 직접 정렬 해야함!맨 뒤에서 부터 앞으로 땡기면서 비교를 했다. 만약에 m = 0 이 주어지면 맨 마지막 if문에 걸리게 했다.
233.[알고리즘/leetcode] Reverse Integer(python)
0이상이면 부호를 붙이지 않고 0 미만이면 -1을 곱해준다.만약 범위를 넘어가면 0을 리턴
234.[알고리즘/leetcode] Remove Nth Node From End of List(python)
처음에는 몇 개인지 for 문으로 찾고 다시 for 문을 사용하여 삭제했다. 하지만 길이가 2 이하인 것들이 처리가 안돼서 포기. 그다음에는 투포인터로 풀었다. s, e에 각각 tmp 노드를 할당하고 e를 먼저 n 만큼 출발 시켜서 간격을 유지했다. e가 마지막
235.[알고리즘/leetcode] Single Number(python)
처음에는 set을 사용하여 없으면 넣고 있으면 제거하면서 했다. 정답 코드를 보던 중 xor을 이용하여 푼 사람을 봤는데... 아직 갈 길이 멀었다는걸 느꼈다...
236.[알고리즘/leetcode] Intersection of Two Arrays II(python)
처음에 문제 이해를 잘못해서 연속된 배열만 가능한 줄 알았는데 그냥 교집합 구하면 된다.set의 intersection을 먼저 떠올리겠지만 set은 중복이 불가능해서 다른 방법을 찾아야 함그래서 nums1의 숫자 개수를 각각 세어서 딕셔너리로 만들고 nums2에서 하나
237.[알고리즘/leetcode] Plus One(python)
방법이 두개이다.1\. digits를 int로 합치고 +1을 해준다.그 다음 문자열로 만들고 리스트로 변환 후 map을 이용하여 int로 변환.
238.[알고리즘/leetcode] Moves Zeros(python)
투포인터를 이용하여 해결했다.하나씩 옮기면서 0이면 바꾸고 아니면 +1을 해주는 방식으로 함.
239.[알고리즘/leetcode] Two Sum(python)
처음에는 브루트포스로 풀었다. 하지만 시간복잡도가 O(N^2)이다...힌트를 눌러서 보니 뺀 값을 찾으면 된다는 이야기가 있었다.해시테이블을 만들어 값을 찾았다.
240.[알고리즘/leetcode] First Unique Character in a String(python)
counter를 이용하여 각 알파벳 빈도수를 계산.카운터 순으로 정렬이 되지만 같은 빈도수를 가진 것들은 먼저 계산된 것부터 순서가 정렬된다.for 문으로 1인 것 검색.
241.[알고리즘/leetcode] Valid Anagram(python)
242.[알고리즘/leetcode] Valid Palindrome (python)
정규표현식을 이용하여 숫자와 문자를 남기고 없애준다.또한 lower()를 이용하여 소문자로 변경투포인터를 이용하여 해결
243.[알고리즘/leetcode] Reverse Linked List(python)
반복문으로 풀었다.이전 값을 저장해야 한다.처음에는 이전 값이 없기 때문에 None으로 지정했다.현재의 다음 값에 prev를 넣고 이전 값에 현재 값을 저장했다.마지막에는 prev를 리턴해야 전체가 나온다.
244.[알고리즘/leetcode] Valid Sudoku(python)
딕셔너리를 이용하여 해결했다. 있으면 false를 리턴하고 없으면 추가했다.
245.[알고리즘/백준] 2812번 : 크게 만들기(python)
스택을 이용해서 푸는 문제이다.맨 왼쪽에 가장 큰 수가 와야 한다. for 문으로 넣으면 맨 왼쪽에 큰 수가 온다는 보장을 못함.따라서 일단 순회하며 다 넣고 while로 지워줘야 한다.마지막 출력은 맨 끝까지 다 출력하면 자릿수를 넘는 게 존재하기 때문에 N-K로 슬
246.[알고리즘/백준]9375번 : 패션왕 신해빈(python)
경우의 수는 headgear -> (hat, turban, x)eyewear -> (sunglasses, x)두 경우를 곱해서 전부 입지 않은 경우를 빼면 정답이다.=> (headgear + 1) \* (eyewear + 1) - 1
247.[알고리즘/codeforce]Non-zero Segments(python)
누적합을 사용해서 푸는 문제이다.값이 0이 되거나 전 까지의 누적합이 딕셔너리에 있으면 ans+1을 해주고 딕셔너리를 초기화 시킨다.
248.[알고리즘/백준]11279 : 최대 힙(python)
파이썬의 heapq를 이용했다.다만 파이썬 heapq는 최소힙이기 때문에 (-, )이렇게 -값으로 붙여서 우선순위를 뒤집어 주었다.pop을 할 때 1을 적어주면 최대값이 나온다.
249.[알고리즘/백준]1083 : 소트(python)
처음에는 앞에서 순회하면서 인접한 숫자들을 비교하는 버블 정렬인 줄 알았다.사전 순으로 가장 뒷서는 것은 수가 클수록 뒤에 위치한다. 따라서 이동 횟수 안에서 가장 큰 수를 맨 앞으로 가져오면 된다.맨 앞에서 s 범위 안에서 가장 큰 수 찾기가장 큰 수가 맨 앞에 있으
250.[알고리즘/백준]1071 : 소트(python)
이전 소트 문제와 다르게 인접한 수 끼리만 교환할 수 있다는 조건이 없다. 따라서 각 숫자의 개수가 몇개인지 counter를 이용하여 구해주었다.현재 수 보다 +1 더 큰 수가 있다면1-1 현재 수 보다 +2 이상인 수가 있다면 -> 현재 수를 모두 출력하고 +2 이상
251.[알고리즘/백준]1489 : 대결(python)
점수를 가장 크게 만들려면 승리를 우선순위로 두어야 한다.또한 b 팀에서 자기보다 작은 수 중에서 가장 큰 수를 이겨야 최대가 된다.이기는 경우를 다 구한 후 무승부 경우를 구하면 된다.sort에서 reverse를 해준 이유는 큰 수부터 비교를 해야 for문이 일찍 끝
252.[알고리즘/백준]11729 : 하노이 탑 이동 순서(python)
n개의 원반 옮기는 경우를 an이라고 하면an+1의 경우 가장 큰 n+1원반을 옮기기 위해 n개를 옮겨야한다.n개의 원반을 1 -> 2로 옮기는게 ann+1원반을 3으로 옮기는게 1다시 n개 원반을 2 -> 3 an\-> an+1 = 2an + 1...2^n - 1가장
253.[알고리즘/백준]17070 : 파이프 옮기기 1(python)
재귀를 이용하여 풀었다.각 경우를 재귀로 구현하면 되는데1\. 가로2\. 세로3\. 대각선가로로 갈 수 있는 건 가로, 대각선세로로 갈 수 있는 건 세로, 대각선대각선으로 갈 수 있는 건 가로, 세로, 대각선각 경우의 좌표로 벽인지 아닌지 판단하고, 범위를 넘어가는지