알고리즘(파이썬)
1.알고리즘
알고리즘 블로그 작성할거임.
2.DFS/BFS
DFS와 BFS는 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘이다.
3.그리디 알고리즘
그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
4.정렬 알고리즘
정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
5.이진 탐색
이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
6.DP
동적 계획법
7.다익스트라
다익스트라 최단 경로 알고리즘은 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 거리를 구해주는 알고리즘이다.
8.[백준] 1010 (실버5)
서쪽에는 n개, 동쪽에는 m개의 사이트가 있다. 서쪽과 동쪽을 잇는 다리를 지으려고 한다. (한 사이트에는 최대 한 개의 다리만 연결!) 다리를 최대한 많이 지을 수 있는 방법은 n개의 다리를 짓는 것이다. 해당 문제는 간단한 원리이다. 동쪽의 m개의 사이트 중, 다리가 지어질 n개만 고르면 된다. 다리는 겹쳐지지 않아야 하기 때문에, 동쪽의 n개의 사이...
9.[백준] 16173 (실버5)
10.[백준] 1026 (실버4)
S가 최솟값을 갖게 하는 방법은 가장 작은 수와 가장 큰 수를 곱해서 각각 더하는 것이다. 예를 들어 A=[2, 4, 6], B=[5, 3, 2]인 경우 A와 B를 각각 오름차순이나 내림차순으로 정렬해서 S를 계산한다면 46이 나오게 된다. 반면, A를 오름차순, B를 내림차순으로 정렬해서 S를 계산한다면 34가 나오게 된다. 위의 소스코드는 정렬을 각...
11.[백준] 1065 (실버4)
12.[백준] 1764 (실버4)
그냥 듣도 못한 사람을 리스트로, 보도 못한 사람을 리스트로 만들어서 겹치는 이름을 뽑아 사전순으로 출력하는 간단한 문제이다. 집합 자료형 set은 list와 달리 append() 메서드가 아닌 add() 메서드를 사용한다. 간단히 & 연산자를 통해 공통 데이터를 뽑아 list에 담고 sorted() 메서드로 정렬하여 result 리스트에 담는다.
13.[백준] 1920 (실버4)
기본적인 탐색 문제이다. 배열에 해당하는 수가 존재하는 지 1과 0으로 표현하면 된다. 배열 정렬 binary search
14.[백준] 11047 (실버4)
간단한 Greedy 알고리즘 문제이다. 위의 소스코드는 동전 관련 문제에서 자주 보이는 알고리즘이다. 남은 값을 동전으로 나눈 몫만큼 count를 올리고, 남은 값을 동전으로 나눠 남은 나머지가 남은 값이 된다.
15.[백준] 11399 (실버4)
순서가 뒤로 갈수록 인출 시간은 누적된다. 총 인출 시간이 최소가 되게 하도록 하는 문제이다. 문제에서 제시하듯, 누적 합이 최소가 되는 방법은 인출 시간이 가장 짧은 사람부터 돈을 인출하게 하는 것이다. 따라서 이는 간단한 정렬 문제이다. 이중 반복문을 사용한 이유는 단순히 배열의 합을 구하는 것이 아니라, 1 + (1+2) + (1+2+3) + .....
16.[백준] 1431 (실버3)
위 소스코드는 zip 함수를 사용하는데, 이는 각 배열에 대해 병렬 처리를 할 수 있도록 도와준다. 아래는 zip 함수의 예제이다. 위 소스 코드의 실행결과는 아래와 같다. (1, 'A') (2, 'B') (3, 'C')
17.[백준] 1463 (실버3)
해당 문제는 대표적인 다이나믹 프로그래밍 문제이다. 2를 1로 만드는 연산은 1을 빼는 것 혹은 2로 나누는 것, 총 1번이다. 3을 1로 만드는 연산은 우선 1을 빼서 2로 만든 후, 2를 1로 만드는 연산 1번을 더하는 것으로 총 2번이다. 하지만 3으로 나누는 연산이 더 효율적으로 작동하므로 총 1번의 연산으로 가능하다. 4를 1로 만드는 연산은 ...
18.[백준] 2579 (실버3)
문제는 다음과 같고, 시간 제한과 메모리 제한은 각각 1초와 128 MB이다. 대표적인 다이나믹 프로그래밍 문제이다. dp 테이블에는 해당 계단을 무조건 밟는 경우의 값을 기록할 것이다. 따라서 dp[0]는 0번째 계단의 점수가 된다. dp[1]은 0번째와 1번째를 모두 밟는 경우이다. dp[2]는 0번째와 2번째를 밟거나, 1번째와 2번째를 밟는 경우...
19.[백준] 2606 (실버3)
시작노드가 주어질 때, 갈 수 있는 노드의 수를 구하는 문제이다. dfs 혹은 bfs로 문제를 풀 수 있다. bfs의 경우, 큐에서 원소를 pop 했을 때, 해당 원소에 대해 핵심 로직을 작성한다. dfs의 경우, 재귀로 인해 함수가 호출됐을 때 핵심 로직을 작성한다.
20.[백준] 1012 (실버2)
이 문제는 상하좌우로 인접해있는 1의 묶음 개수를 세는 것이다. 각 지점에서 dfs 혹은 bfs를 통해 방문처리는 1 -> 0으로 바꾸는 것으로 하여 그래프를 탐색하면 된다. 각 지점에서 dfs 혹은 bfs가 끝날 때마다 count를 하나씩 올려준다. dfs 함수는 인접한 곳을 모두 둘러본 뒤 true 혹은 false를 return 한다. false인 경...
21.[백준] 1260 (실버2)
해당 문제는 대놓고 BFS/DFS 문제이다.
22.[백준] 2644 (실버2)
가족 관계가 그래프 형태로 주어지고, 그래프를 따라 탐색하며 촌수를 1씩 더해가는 프로그램을 작성하면 된다. 모든 가족 관계를 둘러봤을 때, 서로 이어져있지 않다면 -1 출력!
23.[백준] 2805 (실버2)
최대와 최소 사이에서 필요한 값을 찾는 문제이다. 범위가 주어져있기 때문에 이분 탐색을 활용하면 문제를 굉장히 빠르게 풀 수 있다.
24.[백준] 4963 (실버2)
해당 문제는 너무 자주 본 유형이다. 이제는 그냥 dfs, bfs임이 자동으로 생각난다. 달라진 점이라면 그저 대각선으로의 이동도 고려해야 한다는 점 뿐이다.
25.[백준] 11053 (실버2)
이번 문제는 DP 문제이고, 나는 개인적으로 DP가 너무 어렵다,,, 수열의 크기만큼 dp테이블을 만든다. dp테이블의 초기값이 1인 이유는, 각각에 해당하는 수열의 길이를 의미한다. 즉. {10, 20, 10, 30, 20, 50}에 대하여 각각의 dp테이블 값은 1이다. (수열의 길이가 1이기 때문이다.) dp 테이블에는 증가하는 수열의 길이를 저장한...
26.[백준] 11724 (실버2)
연결되어 있는 덩어리들의 개수를 구하라는 문제이다. 앞서 풀어본 많은 문제들과 너무 유사하니 자세한 설명은 생략하겠다. 그래프 탐색 이후, 카운트 값을 1을 증가시키는 방식이다. dfs에 의한 시간초과 문제나, recursion 문제는 위의 주석 방식으로 해결가능하다.
27.[백준] 16401 (실버2)
막대를 잘라서,,, 나눠주거나 합하고,,, 주어진 범위 내에서 특정값을 찾는,,, 어디선가 많이 본 패턴이다. 그렇다! 이분 탐색으로 쉽게 풀 수 있는 문제이다.
28.[프로그래머스] 더 맵게 (Heap)
https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코딩테스트 연습의 힙 챕터 문제이다. 요구사항은 배열의 최소값이 특정 값 이상이 될 때까지 특정 계산을 몇 차례 해야하는 지를 구해야 하는 문제이다. 이 때, 특정 계산에는 배열의 첫 번째와 두 번째 최소값이 필요하다. 맨 처음...
29.[프로그래머스] 포켓몬 (Set)
https://school.programmers.co.kr/learn/courses/30/lessons/1845 해당 문제의 풀이는 한 줄 밖에 되지 않는 매우 간단한 문제이다. 이 문제를 포스팅하는 이유는 파이썬의 set 자료형 때문이다. 중복을 완전히 없애고 싶을 때, 우리는 파이썬의 set 자료형을 사용할 수 있고, 수학에서의 집합 연산을 똑같이 적...
30.[프로그래머스] K번째 수 (리스트 슬라이싱)
https://school.programmers.co.kr/learn/courses/30/lessons/42748 문제에 대한 설명은 다음과 같고, 매우 간단하다. 이 문제는 파이썬에서 간단하게 리스트를 자를 수 있는 방법을 소개하기 위함이다. 위의 코드가 의미하는 바는 다음과 같다. >slice_list를 start 인덱스부터 end-1 인덱스까지 ...
31.[프로그래머스] 정수 삼각형 - Map
https://school.programmers.co.kr/learn/courses/30/lessons/43105 문제는 다이나믹 프로그래밍 문제이다. 다이나믹 프로그래밍 문제는 개인적으로 가장 어려워 하는 유형인데 그래도 어렵지 않게 점화식을 구할 수 있었던 비교적 가벼운 문제였다. 이 문제를 포스팅하는 이유는 2차원 배열에서의 최대값을 찾는 로직을 작...
32.[프로그래머스] 등굣길
https://school.programmers.co.kr/learn/courses/30/lessons/42898 문제를 어떻게 풀어야 하는지에 대한 생각을 하는 데에는 크게 어려움을 겪지 않았으나, 구현에 있어서 어려움을 겪은 문제이다. 웅덩이가 있는 곳을 제외하여, 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 경로의 경우의 수를 구하는 문...
33.[프로그래머스] 신고 결과 받기 - defaultdict
https://school.programmers.co.kr/learn/courses/30/lessons/92334 문제 이해는 그닥 어렵지 않다. 아이디어를 떠올리기도 그닥 어렵지 않았다. 신고한 사람과 신고 받은 사람을 사전 자료형을 사용해 이리저리 볶으면 해답이 나올 것이 뻔히 보이는 문제였다. 기존 사전 자료형을 이용해 문제를 풀어보니, 치명적인 오...
34.[백준] 11725 (실버2)
그래프들이 노드와 간선으로 쭉 이어진 모습과 각 노드들을 모두 탐색해야 하는 걸 보니 dfs/bfs 문제인 것 같다는 생각이 든다. 어렵지 않게 풀 수 있다.!
35.[백준] 18352 (실버2)
코끼리코 10번 돌고 문제 읽어도 다익스트라를 활용하는 문제라는 것을 알 수 있다. 다익스트라 문제를 풀기 위해서는, 다익스트라 알고리즘 자체를 외워두는 것이 좋다. 어렵지 않기 때문에 금방 외우지만 또 금방 까먹기 때문에 자주자주 봐줘야하는 유형이다.
36.[프로그래머스] 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909 떠오른 아이디어는 open 괄호 ( 가 나오면 스택에 값 추가, close 괄호 ) 가 나오면 스택에서 값을 빼는 것이었다. 결과적으로 스택의 크기가 0인 경우에만 True를 반환한다. close 괄호 ) 가 open 괄호 ( 보다 많은 즉...
37.[프로그래머스] 가장 먼 노드 - 배열 원소 개수 세기
https://school.programmers.co.kr/learn/courses/30/lessons/49189 간단히 설명하면, 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 구하는 문제이다. dijkstra 알고리즘을 활용하면 특정 노드로부터 다른 모든 노드까지의 거리를 구할 수 있으므로 쉽게 풀 수 있다. > list.count(특정값) 해당...
38.[백준] 1850 (실버1)
최대 공약수를 구하는 알고리즘을 작성하는 문제이다. 1학년 2학기에 C언어를 처음 배울 때, 재귀함수 부분에서 해당 알고리즘을 유클리드 호제니 뭐니 해서 배웠던 기억이 난다. (그 때로 돌아가고 싶다..ㅎ) 하지만 우리는 파이썬의 math 라이브러리를 이용해서 간단하게 풀도록 하겠다. 유클리드 호제법 a>b인 두 수 a, b에 대해 a와 b의 최대공...
39.[백준] 2178 (실버1)
bfs 알고리즘을 사용하지 않고는 참을 수 없는 병에 걸린 것 같다. 이제는 문제가 너무 쉽게 보이는 수준이 됐다.
40.[프로그래머스] 성격 유형 검사하기
https://school.programmers.co.kr/learn/courses/30/lessons/118666 문제 설명이 너무 길어서 따로 캡쳐해서 올리진 않겠다. 저번에 배운 defaultdict를 사용한 문제이다. 문제 이해만 하고, defaultdict를 사용해야겠다는 아이디어가 금방 떠올라서 어렵지 않게 문제를 풀 수 있었다.
41.[프로그래머스] 로또의 최고 순위와 최저 순위
https://school.programmers.co.kr/learn/courses/30/lessons/77484 로또 번호 6자리 중, 낙서로 인해 지워진 번호는 0으로 표기된다. 알고자 하는 것은 해당 로또 번호의 최고와 최저 순위이다. 즉, 0으로 표시된 번호가 다 당첨이었을 경우와 0으로 표시된 번호가 모두 당첨이 아닐 경우의 순위를 각각 구하는 ...
42.[프로그래머스] 전화번호 목록 - startswith
https://school.programmers.co.kr/learn/courses/30/lessons/42577 어렵지 않다고 생각한 문제이다. 접두사의 의미를 헷갈려서 푸는데에 시간이 조금 걸렸다. 접두어 관계인 숫자가 포함되어 있으면 False를, 포함되어 있지 않으면 True를 반환해야 한다. 접두어 관계의 의미가 '포함'인줄 알았는데, "어떤 ...
43.[프로그래머스] 기능개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586 문제 해결의 아이디어를 떠올리는 데에는 어려움이 없었다. 각 공정별로 완료까지 남은 기간을 days 배열에 담아둔다. 예를 들어 days = [5, 10, 1, 1, 20, 1] 이라고 하자. 5일짜리 공정 1개, 10일, 1일, 1일짜리 공...
44.[프로그래머스] 신규 아이디 추천 - 문자열 변형
https://school.programmers.co.kr/learn/courses/30/lessons/72410 해당 규칙에 맞춰 차근차근 아이디를 변형하면 되는 간단한 문제이다. 문자열 변형 관련해서 많은 메서드들을 알게 된 문제이다. > isupper(), islower(), upper(), lower() 대문자이거나 소문자인지 확인하고, 대문...
45.[프로그래머스] 가장 큰 수 - 정렬 key, lambda
https://school.programmers.co.kr/learn/courses/30/lessons/42746 아이디어를 떠올리는 데에는 큰 시간이 걸리진 않았지만, 코드로 구현하는 데 있어 시간을 많이 잡아먹은 문제이다. 우선 간단하게 numbers를 앞자리가 큰 수가 오도록 하여 정렬해야겠다는 생각이 든다. int 상태로 정렬을 하게 되면 10이...
46.[프로그래머스] 네트워크 DFS/BFS
https://school.programmers.co.kr/learn/courses/30/lessons/43162 해당 문제는 뭉텅이의 개수를 세는 것이라고 이해하면 된다. 위의 그림에서 보면 1번과 2번이 연결되어 있기 때문에 한 뭉텅이로 보고, 3번을 독립적인 뭉텅이로 보아, 총 2개의 뭉텅이가 있다고 볼 수 있다. 뭉텅이 관련 문제는, 각각의 노드...
47.[프로그래머스] 여행경로 DFS
https://school.programmers.co.kr/learn/courses/30/lessons/43164 출발지와 도착지가 적힌 tickets 리스트가 주어지고, ICN으로부터의 경로를 출력하면 되는 문제이다. 이 때 경로가 2가지 이상이라면, 알파벳 순으로 가는 경로를 출력하면 된다. 우선 나는 출발지 별로 도착지들을 알파벳의 역순으로 리스트...
48.[프로그래머스] 옹알이 - replace
https://school.programmers.co.kr/learn/courses/30/lessons/120956 문제의 테스트케이스가 이상한건가...? 우선 아래 문제설명과 테스트 케이스를 살펴 보자. 아이는 현재 옹알이 중이라 {"aya", "ye", "ma", "woo"} 4가지 발음과 그 조합으로 밖에 말할 수 없다. 첫 번째 입력 케이스는 ...
49.[프로그래머스] 소수 찾기 - itertools permutations
https://school.programmers.co.kr/learn/courses/30/lessons/42839 문제는 위와 같고, 아이디어가 어렵다기 보다는 각각의 찢어진 종이 조각으로 만들 수 있는 숫자를 만드는 과정에서 구현이 까다로웠다. num 배열이 만들어지는 과정을 주목해서 살펴두자.
50.[프로그래머스] - 키패드 누르기
https://school.programmers.co.kr/learn/courses/30/lessons/67256 간단하게 문제를 요약하자면, (1, 4, 7)은 왼손으로 누르고 (3, 6, 9)는 오른손으로 누르고 (2, 5, 8, 0)은 가까이 있는 손으로 누르되 거리가 같으면 자기의 주손으로 누르는 것이다. 우선 내 풀이 아이디어는 아래와 같다. ...
51.[프로그래머스] JadenCase 문자열 만들기 - title, capitalize
https://school.programmers.co.kr/learn/courses/30/lessons/12951 문제는 너무 간단하다. 처음에 문제를 풀 때는 각 단어별로 첫번째 문자는 대문자로, 그 뒤에 나머지 문자열은 하나하나 소문자로 바꿔주는 코드를 작성했다. islower(), isupper(), lower(), upper() 등의 함수를 사용했...
52.[프로그래머스] 피보나치 수
https://school.programmers.co.kr/learn/courses/30/lessons/12945 피보나치 수를 구하는 간단한 문제인데, 내가 알던 풀이 외에 좋은 풀이가 있어 기록하려 한다. 물론 엄청 기발하다거나 다른 풀이는 아니고 그냥 .. ㅋㅋ
53.[프로그래머스] 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163 우선 내가 작성한 코드와 그에 대한 테스트 점수는 아래와 같다. bfs 방식으로 풀이를 했는데, 주어진 단어를 모두 방문해야했기 때문이다. 보통은 왜 80점을 받는지 납득할 수 없는 경우가 많은데, 이번엔 내가 왜 80점을 받는 지 안다....
54.[프로그래머스] 영어 끝말잇기
https://school.programmers.co.kr/learn/courses/30/lessons/12981 어렵지 않은 간단한 문제이다. 우리가 평소 아는 끝말잇기 규칙에 위배되는 사람을 찾는 그런 문제이다. 내 풀이에 비해 굉장히 깔끔한 코드가 예시답안으로 작성되어 있어 소개하려 한다. 우선 내 풀이의 경우 deque 라이브러리를 활용해 큐 ...