Eunhye Kim

Eunhye Kim

All progress takes place
outside the comfort zone.

Posts

Problem Solving

[백준 BOJ_2096] 내려가기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어주었습니다. 처음에는 3차원 배열로 내려가며 각각 max와 min을 갱신하여 구해주었지만 메모리 초과가 나게 되었습니다. 그래서 한 줄씩 입력받아 cache를 갱신해주며 풀어주었습니다. cache는 다음과 같습니다. ...

[백준 BOJ_11660] 구간 합 구하기 5 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어주었습니다. graph의 각각 첫 번째 행과 열(graoh[0][i], graph[i][0])은 이 전의 값을 누적하며 더해주었습니다. 첫 번째 행과 열을 제외한 나머지 칸들은 왼쪽에 있는 값(graph[x-1][...

[백준 BOJ_2206] 벽 부수고 이동하기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 풀어주었습니다. visited를 다음과 같은 3차원 배열로 만들어줍니다. visited[y][x][0] = 좌표 (x, y)까지의 벽을 부수지 않은 상태에서의 최단 경로 visited[y][x][1] = 좌표 (x, ...

[백준 BOJ_1865] 웜홀 Python 풀이

출처: 백준 온라인 저지 문제 풀이 벨만-포드 (Bellman-Ford) 알고리즘을 이용하여 풀어주었습니다. 우선 벨만-포드 알고리즘은 가중치가 음수일 때에도 사용가능한 최단거리 알고리즘입니다. 벨만-포드 알고리즘에서는 모든 간선을 정점의 수만큼 반복하여 비교해주는데, ...

[백준 BOJ_12865] 평범한 배낭 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법을 이용하여 풀어주었습니다. cache는 다음과 같습니다. cache[i][j] = i번째 물건까지 고려했을 때, 최대 j 무게를 가지는 물건의 가치 최대 합 물건의 무게(W)와 가치(V)를 입력받고, 1부터 K까지 돌려...

[백준 BOJ_1238] 파티 Python 풀이

출처: 백준 온라인 저지 문제 풀이 다익스트라(dijkstra)를 이용하여 구현해주었습니다. 간선들을 확인하여 인접리스트를 만들어주었습니다. 단방향이기 때문에 서로에게 추가해주는 것이 아닌 출발점을 key로 가지고, 도로의 길이와 도착점의 tuple을 heappush를 ...

[백준 BOJ_1918] 후위 표기식 Python 풀이

출처: 백준 온라인 저지 문제 풀이 Stack을 이용하여 풀어주었습니다. 각각 연산의 우선순위를 저장해주는 priority라는 dictionary를 만들어주었습니다. 먼저 계산이 되어야 할 곱셈, 나눗셈은 2로, 덧셈과 뺄셈은 1로, 그리고 연산은 아니지만 stack에...

[백준 BOJ_1967] 트리의 지름 Python 풀이

출처: 백준 온라인 저지 문제 풀이 DFS로 풀어주었습니다. 이미 풀었던 아래의 문제와 입력값을 받는 방식만 다를 뿐 풀이는 거의 동일합니다. [백준 BOJ_1167] 트리의 지름 Python 풀이 코드 import sys sys.setrecursionlim...

[백준 BOJ_18870] 좌표 압축 Python 풀이

출처: 백준 온라인 저지 문제 풀이 입력받은 list를 중복제거 해준 뒤 정렬해주어 다시 sorted_X에 저장해줍니다. 정렬된 list를 바탕으로 해당 숫자를 key로, index를 value로 가지는 dictionary를 만들어줍니다. 그 후에는 입력받은 list를...

[백준 BOJ_11399] ATM Python 풀이

출처: 백준 온라인 저지 문제 풀이 탐욕법(Greedy)로 풀어주었습니다. 우선 기다리는 사람들이 가장 적게 기다리려면 인출하는데 걸리는 시간이 가장 적은 순서대로 서야 됩니다. 그래서 받아준 입력값 P를 오름차순으로 정렬해주고 for loop을 돌아주며 이전 사람이 기...

[백준 BOJ_1167] 트리의 지름 Python 풀이

출처: 백준 온라인 저지 문제 풀이 DFS로 풀어주었습니다. 이 문제를 풀기에 앞서 트리의 지름을 구하기 위해서는 먼저 알아야 할 부분은 다음과 같습니다. 임의의 노드에서 가장 먼 거리를 가지는 노드는 트리의 지름을 이루는 두 노드 중 하나이다. 이것만 알게 된...

[백준 BOJ_9095] 1, 2, 3 더하기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다. cache[i] = 1, 2, 3의 합으로 정수 i를 나타낼 수 있는 방법의 수 4부터 10까지 각각 다음과 같은 세 가지 경우의 수를 더해주면 됩니다. i-1를 ...

[백준 BOJ_7576] 토마토 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS를 이용하여 풀어주었습니다. 시작하기 전 익지 않은 토마토의 수를 세어주어 cnt에 저장해주었습니다. 익지 않은 토마토가 없다면 바로 0을 출력하게 했습니다. 또한 세어줄 때 익은 토마토의 좌표를 queue에 담아주었고, 익지...

[백준 BOJ_13549] 숨바꼭질 3 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS를 이용하여 풀어주었습니다. visited를 여유롭게 500,000개의 math.inf로 초기화 해준 뒤 매번 visited를 더 짧은 time으로 갱신해주어 풀어주었습니다. time이 result보다 클 땐 더 이상 진행하지 않...

[백준 BOJ_1504] 특정한 최단 경로 Python 풀이

출처: 백준 온라인 저지 문제 풀이 최단거리 알고리즘인 다익스트라(dijkstra)를 이용하여 구현해주었습니다. heapq 모듈을 사용하여 구현해주었고, dist를 math.inf로 초기화해주고, 다익스트라를 통해 src에서 출발하여 도착할 수 있는 최단경로를 upda...

[백준 BOJ_9465] 스티커 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache를 따로 만들어주지 않고 입력받은 stickers의 값을 갱신하며 풀어주었습니다. 현재 위치의 스티커를 고른다는 전제하에 고를 수 있는 스티커의 조건은 두 가지의 경우의 수로 나뉩니다. 현재...

[백준 BOJ_1043] 거짓말 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 비밀을 알고 있는 사람의 번호들을 set으로 저장해줍니다. 모든 파티의 멤버들 또한 set으로 저장하여 parties라는 list에 추가해줍니다. 파티의 멤버에 비밀을 알고 있는 사람이 포함된다면 그 파티 멤버를 truth...

[백준 BOJ_11404] 플로이드 Python 풀이

출처: 백준 온라인 저지 문제 풀이 플로이드 와샬(Floyd Warshall) 알고리즘을 이용해 풀어주었습니다. i에서 k를 거쳐 j까지 간 거리가 현재 graph에 저장된 거리보다 짧다면 갱신해주었습니다. 이후에 inf를 0으로 값을 바꿔주며 시작도시와 도착도시가 ...

[백준 BOJ_11725] 트리의 부모 찾기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 DFS로 풀었습니다. 우선 입력으로 주어진 edge를 바탕으로 인접리스트를 만들어주었습니다. 각 노드의 부모노드 번호를 저장하는 parents list를 만들어준 뒤, dfs로 1부터 돌아주며 해당 노드가 leaf라면 return을...

[백준 BOJ_1103] 게임 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법을 더한 DFS으로 풀었습니다. cache는 다음과 같습니다. cache[y][x] = 좌표 (x, y)까지 도달하는 최장거리 visited를 따로 만들어주어 cycle 체크를 해주었습니다. 이미 방문했다면 cycle...

[백준 BOJ_1620] 나는야 포켓몬 마스터 이다솜 Python 풀이

출처: 백준 온라인 저지 문제 풀이 dictionary를 이용하여 풀어주었습니다. 우선 N만큼의 포켓몬 입력을 list로 받아준 뒤, 포켓몬의 이름을 key로, 포켓몬의 번호를 value로 가지는 numbers를 pokemons list를 이용해 만들어주었습니다...

[백준 BOJ_12852] 1로 만들기 2 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다. cache[i][0] = 1에서 정수 i까지 만드는데 드는 최소 연산의 숫자 cache[i][1] = 1에서 정수 i까지 만드는데 거친 숫자들의 list N에서 출발하는 ...

[프로그래머스_92343] 양과 늑대 Python 풀이

출처: 프로그래머스 문제 풀이 DFS로 풀어주었습니다. visited로 방문한 노드를 체크해주며 돌아줍니다. is_wolf를 체크하며 해당 노드에 양이나 늑대가 있는지 확인해주었습니다. 양이라면 sheep를, 늑대라면 wolf의 숫자를 늘려주며, 늑대의 ...

[프로그래머스_67257] 수식 최대화 Python 풀이

출처: 프로그래머스 문제 풀이 우선 divide 함수로 문자열 expression에서 숫자와 연산자를 구분해줍니다. 그 뒤 permutations 모듈을 사용하여 연산자의 우선순위 경우의 수를 구해줍니다. 그렇게 구해준 우선순위를 모두 확인해주며 구할 수 있는 가장 ...

[프로그래머스_1844] 게임 맵 최단거리 Python 풀이

출처: 프로그래머스 문제 풀이 BFS로 풀어주었습니다. visited를 따로 만들어주지 않고 map의 값을 바꿔주었습니다. y와 x좌표를 tuple로 넣어주며 popleft를 해주면서 최단거리를 구해주었습니다. 갈 수 있는 모든 거리에 벽이 없는지 확인(map의 ...

[프로그래머스_68645] 삼각 달팽이 Python 풀이

출처: 프로그래머스 문제 풀이 반시계 방향으로 삼각달팽이를 순서에 맞게 채워넣어 구현해주었습니다. 삼각형을 주어진 n의 크기로 0으로 초기화해주어 다음과 같이 만들어줍니다. n=4일 때, snail = [[0], [0, 0], [0, 0,...

[프로그래머스_72413] 합승 택시 요금 Python 풀이

출처: 프로그래머스 문제 풀이 최단거리 알고리즘인 다익스트라(dijkstra)를 이용하여 구현해주었습니다. heapq 모듈을 사용하였고 dijkstra 함수는 출발 노드인 src에서부터 다른 노드간의 최단거리를 담는 list를 반환합니다. 모든 지점을 돌아주며 중...

[백준 BOJ_1890] 점프 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다: 좌표가 (x, y)일 때, cache[i][j] = 좌표 (j, i)까지 갈 수 있는 경로의 수 출발 지점인 (0, 0)에는 1을 저장해주어 시작합니다. 각 좌표를 돌아주며...

[백준 BOJ_1062] 가르침 Python 풀이

출처: 백준 온라인 저지 문제 풀이 backtracking으로 풀었습니다. 우선 배운 알파벳을 체크해주기 위해 learned 라는 list를 만들어줍니다. 모든 단어는 기본적으로 “anta”로 시작하고 “tica”로 끝나야 하기때문에 “a”, “c”, “i”, “n”,...

[프로그래머스_12978] 배달 Python 풀이

출처: 프로그래머스 문제 풀이 동적계획법을 더해준 BFS로 풀어주었습니다. 여기서 cache는 다음과 같습니다. cache[i] = 1번 마을에서 i번 마을로 가는 최소 시간 최소시간을 찾는 문제이기 때문에 cache를 모두 float(“inf”)로 초기화해준 뒤 ...

[백준 BOJ_2023] 신기한 소수 Python 풀이

출처: 백준 온라인 저지 문제 풀이 backtracking으로 풀었습니다. 우선 숫자가 소수가 되려면 가장 앞에 오는 숫자는 소수가 되어야 합니다. 그래서 first에 1부터 9까지의 수 중 소수인 2, 3, 5, 7을 넣어줍니다. 그 뒤로 오는 숫자는 소수가 아니어...

[백준 BOJ_14888] 연산자 끼워넣기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 DFS를 이용하여 풀어주었습니다. dfs 함수를 만들어주었고 parameter는 다음과 같습니다. cnt: 이떄까지 연산한 숫자의 개수 res: 이때까지 연산하여 나온 값 add: 남은 덧셈의 개수 sub: 남은 뺄셈...

[백준 BOJ_1495] 기타리스트 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다: cache[i][j] = i번째 곡을 j 볼륨으로 연주 가능한지 여부 cache[1][3] = 1 이라면 첫번째 곡을 볼륨 3으로 연주가 가능하다는 뜻 각각 이전 곡의 가...

[백준 BOJ_8911] 거북이 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 status에 x와 y의 상태를 담아줍니다. status는 거북이가 바라보고 있는 방향을 다음과 같이 알려줍니다. status = [x, y] x와 y는 한 눈금 앞으로 (F) 갈 때 더해주는 값이 들어가게 됩니다. 북 = [0...

[백준 BOJ_5430] AC Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 p와 n의 값을 받은 뒤, 배열형식의 문자열을 배열로 바꿔줍니다. 배열을 deque로 바꿔주어 pop과 popleft를 자유자재로 사용할 수 있게 합니다. func_num에 연속되는 함수의 개수를 세어줍니다. 연속되는 함수가 ...

[백준 BOJ_9019] DSLR Python 풀이

출처: 백준 온라인 저지 문제 풀이 최소 경로를 찾아야 하기 때문에 BFS를 이용하여 풀어주었습니다. 우선 dq에 시작하는 수인 A와 빈 배열을 넣어줍니다. 후에 명령어가 추가되면 빈 배열에 명령어를 추가해줍니다. 이미 방문한 수에는 방문하지 않게끔 정수의 범위인 0부터...

[프로그래머스_12911] 다음 큰 숫자 Python 풀이

출처: 프로그래머스 문제 풀이 10진수를 2진수를 바꿔주는 decimalToBinary함수를 만들고, check 함수로 n과 1의 개수가 같은 수를 확인해주었습니다. n+1 부터 check 함수를 거치며 1의 개수가 같은 수를 찾아 바로 return 해주었습니다. 코드 ...

[백준 BOJ_1753] 최단경로 Python 풀이

출처: 백준 온라인 저지 문제 풀이 최단거리 알고리즘인 다익스트라(dijkstra)를 이용하여 구현해주었습니다. heapq 모듈을 사용하여 구현해주었고, dist를 math.inf로 초기화해주고, 다익스트라를 통해 K에서 출발하여 도착할 수 있는 최단경로를 update해...

[백준 BOJ_1743] 음식물 피하기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 구현해주었습니다. 방문할 때마다 visited를 1로 update 해주며, 상하좌우로 연결된 쓰레기의 개수를 cnt에 누적하여 세어주었습니다. while loop이 끝날 때마다 result에 더 큰 값으로 저장해주었고 마지...

[프로그래머스_64064] 불량 사용자 Python 풀이

출처: 프로그래머스 문제 풀이 permutations 모듈을 사용하여 구현해주었습니다. check 함수를 만들어 해당 아이디가 불량사용자 아이디인지 체크해주었습니다. 불량사용자 아이디가 아니라면 continue로 넘겨주고, 불량사용자 아이디라면 중복을 제거하고 ...

[프로그래머스_17677] 뉴스 클러스터링 Python 풀이

출처: 프로그래머스 문제 풀이 Counter 모듈을 이용하여 구현해주었습니다. set을 이용하여 교집합(intersection) 또는 합집합(union)을 구해줄 수 도 있지만, set은 중복을 제거하기 때문에 이 문제와는 맞지 않았습니다. 각각의 단어의 두 글자가 ...

[프로그래머스_81302] 거리두기 확인하기 Python 풀이

출처: 프로그래머스 문제 풀이 find_p 함수를 만들어주어 각 대기실의 응시자의 위치를 찾아 주었습니다. 응시자가 없거나 한 명밖에 없으면 거리두기를 준수하고 있기 때문에 바로 1을 추가해주었고, queue를 pop해주며 각각의 응시자들이 나머지 응시자들과 거리두...

[프로그래머스_12913] 땅따먹기 Python 풀이

출처: 프로그래머스 문제 풀이 동적계획법으로 풀어주었습니다. cache는 그 위치의 숫자를 선택했을때 가질 수 있는 최대값입니다. 이 전의 값들 중(j-1) 같은 열의 위치를 제외하고 나머지 중에 가장 큰 값에 그 위치의 숫자를 더한 값을 저장해주었습니다. 코드 de...

[백준 BOJ_2290] LCD Test Python 풀이

출처: 백준 온라인 저지 문제 풀이 단순구현 해주었습니다. N이 1일 때를 기준으로 표현할 수 있는 모든 가로, 세로 줄은 다음과 같이 7개였습니다. 맨 위 가로 줄 첫 번째 왼쪽 세로 줄 첫 번째 오른쪽 세로 줄 중간 가로 줄 두 번째 왼쪽 세로 줄...

[프로그래머스_42898] 등굣길 Python 풀이

출처: 프로그래머스 문제 풀이 동적계획법으로 풀어주었습니다. 일단 움직일 수 있는 범위가 오른쪽과 아래쪽밖에 없으므로 돌아가는 경우는 생각해주지 않아도 되기 때문에 모든 경로가 최단거리가 됩니다. 우선 n * m 크기의 graph를 만들어주고, 1로 초기화해주었습니다...

[프로그래머스_67258] 보석 쇼핑 Python 풀이

출처: 프로그래머스 문제 풀이 Counter를 이용하여 구현해주었습니다. cnt_gems에 gems의 Counter를 저장해줍니다. start와 end는 각각 포함하는 보석의 시작 index와 끝 index를 의미합니다. 구간을 최소화하기 위해서는, 조건을 충족하면...

[프로그래머스_42626] 더 맵게 Python 풀이

출처: 프로그래머스 문제 풀이 heap을 이용하여 풀어주었습니다. 주어진 scoville을 heapify해주고, 두 번의 heappop을 해주어야 하기 때문에 while문의 조건을 scoville의 길이가 2 이상인 경우와, scoville의 가장 작은 원소가 K보다 작...

[프로그래머스_42587] 프린터 Python 풀이

출처: 프로그래머스 문제 풀이 deque를 이용하여 풀어주었습니다. priorities의 index를 저장하는 idx를 deque로 만들어줍니다. max_prior에는 가장 높은 우선순위의 값을 저장해줍니다. 가장 높은 우선순위가 아니라면 popleft해주고 바로 a...

[백준 BOJ_1946] 신입사원 Python 풀이

출처: 백준 온라인 저지 문제 풀이 그리디로 풀어주었습니다. 지원자를 서류 순위로 정렬해준 뒤 가장 높은 서류 순위의 사람의 인터뷰 순위를 저장해준 뒤, 더 높은 순위를 가진 사람이 있다면 result를 누적해주었습니다. 코드 T = int(input()) for _...

[백준 BOJ_2606] 바이러스 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 구현했습니다. 인접리스트를 구현해준 뒤, 시작 노드를 queue에 넣고 탐색을 시작합니다. popleft를 해주면서 방문하지 않았다면 해당 노드를 visit에 넣어주고, queue를 해당 노드와 연결된 모든 노드들을 exten...

[프로그래머스_92341] 주차 요금 계산 Python 풀이

출처: 프로그래머스 문제 풀이 입차할때 시간을 넣어주고 출차할때는 pop해주어 나온값을 출차시간에서 빼서 다시 넣어주었습니다. 입차만 하고 출차하지 않은 차는 status_dict으로 확인해주어 예외처리해주었습니다. 코드 from collections import...

[프로그래머스_87390] n^2 배열 자르기 Python 풀이

출처: 프로그래머스 문제 풀이 패턴을 찾아 처리해주었습니다. 해당 row에 따른 row_lst는 다음과 같습니다. row_lst = [row]*row + [i for i in range(row+1, n+1)] 가장 처음과 마지막은 예외처리를 해주고 나머지 반복되...

[프로그래머스_42627] 디스크 컨트롤러 Python 풀이

출처: 프로그래머스 문제 풀이 우선 jobs를 요청시간이 가장 빠른 순서로 오름차순 정렬해주었습니다. 아래와 같은 조건 아래에 돌아주었습니다. idx가 jobs의 길이보다 작다 = 아직 요청하지 않은 작업이 있다 ready가 비어있지 않다 = 대기 중인 처리...

[백준 BOJ_16953] A → B Python 풀이

출처: 백준 온라인 저지 문제 풀이 greedy로 풀었습니다. B를 A로 만들어주면서 불가능하면 -1을 return 해주었습니다. 우선 마지막 숫자가 1일 때는 뒤에 1을 붙여주었을 테니 뒤에 1을 제외해주기 위해 B를 10으로 나눈 값으로 저장해주었습니다. 그렇지 않...

[백준 BOJ_11403] 경로 찾기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 플로이드 와샬(Floyd Warshall) 알고리즘을 이용해 풀어주었습니다. i에서 k를 거쳐 j까지 갈 수 있다면 adj[i][j]는 도달 할 수 있으므로 1로 처리해주었습니다. 코드 # 플로이드 와샬(Floyd Warshall)...

[백준 BOJ_1874] 스택 수열 Python 풀이

출처: 백준 온라인 저지 문제 풀이 실제로 스택을 만들어주어 구현하였습니다. stack에 아무 숫자도 없을 때는 넣어주고, stack의 마지막 숫자가 curr_num이랑 같지 않을 때는 curr_num이 더 클 때는 숫자를 append ...

[백준 BOJ_18111] 마인크래프트 Python 풀이

출처: 백준 온라인 저지 문제 풀이 완전탐색으로 풀어주었습니다. 우선, field는 2차원 배열로 주어지지만 딱히 좌표가 필요한게 아니므로 1차원 배열로 받아주어도 무관합니다. 그 다음 가장 큰 높이를 가지는 순서대로 정렬해줍니다. field가 가지는 가장 높은 높이...

[프로그래머스_77485] 행렬 테두리 회전하기 Python 풀이

출처: 프로그래머스 문제 풀이 rotate이라는 함수를 따로 만들어주었습니다. rotate은 주어진 전역변수 matrix를 주어진 범위 내의 테두리에 위치한 수만 한 칸씩 돌려 값을 저장해줍니다. 또한 돌려지는 값들 중 가장 작은 수인 min_num을 찾아 retu...

[백준 BOJ_1107] 리모컨 Python 풀이

출처: 백준 온라인 저지 문제 풀이 완전탐색으로 풀어주었습니다. 우선 result를 100에서 N까지의 거리(+던지 -던지 숫자 버튼을 쓰지 않고 채널 변경하는 경우)로 초기화 해주었습니다. 고장난 버튼이 없다면, 숫자 버튼을 눌러서 변경하는 것과 위의 경우 중 최소값...

[백준 BOJ_1038] 감소하는 수 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다: # cache[i][j] = 숫자 i로 시작하는 j+1 자릿수의 감소하는 숫자들의 배열 # i = 0 cache[0][0] = [0] # j = 0 # i = 1 cache[1...

[백준 BOJ_1697] 숨바꼭질 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 풀었습니다. 처음에 visited를 사용하지 않고 풀었을 때는 메모리 초과가 났습니다. 그래서 visited로 해당 수를 방문해주지 않았을 때만 방문해주었습니다. visited에 걸리는 시간을 누적해주었기 때문에 마지막에는...

[백준 BOJ_1966] 프린터 큐 Python 풀이

출처: 백준 온라인 저지 문제 풀이 단순히 구현해주었습니다. 중요도를 담는 list인 priority와 몇 번째 문서였는지의 정보를 담는 nth_lst를 만들어주었습니다. 그런 뒤, 지시사항에서 말한대로 가장 앞에 있는 문서의 중요도를 확인하고 나머지 문서들 중 중요도...

[프로그래머스_43162] 네트워크 Python 풀이

출처: 프로그래머스 문제 풀이 DFS로 풀어주었습니다. 방문하지 않은 노드를 찾아서 queue에 넣어주고, 찾은 노드에 연결된 다른 노드들을 찾아 방문해주며, 연결된 노드에서 연결된 또 다른 노드를 찾아주기 위해 queue에 넣어준 뒤, 연결된 노드들은 queue에 ...

[프로그래머스_42839] 소수 찾기 Python 풀이

출처: 프로그래머스 문제 풀이 완전탐색으로 permutation을 이용해 모든 가능한 수를 찾아주었습니다. 소수를 판별하는 함수를 따로 만들어주었고, 함수 내에서 제곱근만큼만 돌려주어 효율을 높였습니다. 소수라면 num_set에 넣어주고 마지막에는 중복제거를 위해 se...

[프로그래머스_42586] 기능개발 Python 풀이

출처: 프로그래머스 문제 풀이 가장 앞의 기능이 완료되는 기간을 days에 저장해준 뒤, 모든 progress들에 days만큼 진행되는 progress를 더해주었습니다. 앞에서부터 연속되는 배포 가능한 기능(진행상황이 100%이거나 넘는 기능)들의 개수를 세어주었고, a...

[백준 BOJ_1141] 접두사 Python 풀이

출처: 백준 온라인 저지 문제 풀이 접두사가 아닌 문자열을 찾기 위해 다른 단어의 접두사인 단어의 수를 세어주기로 했습니다. 우선 같은 문자열이 있다면 하나만 포함할 수 있으므로 중복을 제거해주기 위해 set을 썼습니다. 그런 뒤 보다 빠르게 접두사를 찾아주기 위해 ...

[백준 BOJ_1012] 유기농 배추 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 풀었습니다. M*N의 크기를 가지는 2차원 배열 graph를 만들어 준 뒤, 배추가 있는 좌표에 1을 넣어주었습니다. 만들어진 graph를 가지고 1이 있는 좌표를 찾아주어 queue에 넣고 BFS를 시작합니다. 상하좌우...

[백준 BOJ_2667] 단지번호붙이기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS를 이용하여 풀었습니다. 방문할 때마다 cnt를 늘려주었고, 상하좌우에 1이 있는지 확인해주며 queue에 추가해주었습니다. queue에 추가하는 순간 field의 값을 0으로 바꿔주면서 중복하여 추가하지 않게끔 했습니다. 함수...

[백준 BOJ_1931] 회의실 배정 Python 풀이

출처: 백준 온라인 저지 문제 풀이 그리디 알고리즘을 이용해 풀어주었습니다. timeline을 끝나는 시간이 빠른순서로 정렬해주었습니다. 끝나는 시간이 같다면 시작하는 시간이 빠른 순서로 정렬되게끔 두번째 key로 넣어주었습니다. 그런 뒤 가장 끝나는 시간이 빠른 미...

[백준 BOJ_10819] 차이를 최대로 Python 풀이

출처: 백준 온라인 저지 문제 풀이 backtracking으로 풀었습니다. 모든 경우의 수를 확인해주기 위해 시작하는 숫자 또한 for loop으로 돌려주었고, 고르지 않은 수들의 list인 not_picked에서 하나를 골라 prev_num과 뺀 값의 절대값을 sum_...

[프로그래머스_12973] 짝지어 제거하기 Python 풀이

출처: 프로그래머스 문제 풀이 처음에는 구현 문제인 줄 알고 열심히 풀어보았지만 번번이 효율성 테스트를 통과하지 못했습니다. 그래서 생각하다 저번에 푼 이전의 값을 고려해주기 위해 stack을 사용한 괄호문제가 생각났습니다. stack에 각각의 문자를 넣어주기 전, s...

[프로그래머스_42578] 위장 Python 풀이

출처: 프로그래머스 문제 풀이 해시 문제라서 dictionary를 이용하여 풀었습니다. 처음에는 combination을 쓰는 접근을 하였으나 후에 dictionary로 구현하는 것이 더 효율적임을 깨닫게 되었습니다. dictionary를 이용하여 각각 의상 종류에 따...

[프로그래머스_42579] 베스트앨범 Python 풀이

출처: 프로그래머스 문제 풀이 우선, 해당 장르의 곡들을 아래와 같이 index 0에는 장르의 누적 재생 횟수를, 그 다음부터는 고유번호 i와 노래 재생 횟수에 -1을 곱해준 값을 가지는 tuple을 넣어줍니다. 매 곡마다 누적 재생 횟수를 갱신하고 tuple을 appe...

[백준 BOJ_2504] 괄호의 값 Python 풀이

출처: 백준 온라인 저지 문제 풀이 stack을 이용해 모든 경우의 수를 체크해주었습니다. 설명은 아래의 코드에 달린 주석과 같습니다. 코드 str1 = input() stack = [] num = 1 result = 0 for i in range(len(str1)):...

[프로그래머스_42888] 오픈채팅방 Python 풀이

출처: 프로그래머스 문제 풀이 우선, 바뀐 닉네임을 저장해주기 위해 for loop을 돌려 user라는 dictionary에 유저 아이디에 따른 닉네임을 저장해주었습니다. 그 이후로는 닉네임을 바꾸었을 때는 따로 메세지를 출력하지 않기 때문에 제외해준 뒤, 해당 유저 ...

[백준 BOJ_3085] 사탕 게임 Python 풀이

출처: 백준 온라인 저지 문제 풀이 브루트 포스로 모든 경우의 수를 체크해주었습니다. 이론은 간단합니다. 서로 다른 swap 가능한 두 수를 찾아 swap해주고, check함수로 가장 긴 연속 부분을 구해준 뒤 result를 update해주었습니다. 처음에 check...

[백준 BOJ_2178] 미로 탐색 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS로 풀어주었습니다. 방문하는 좌표에 현 좌표값을 누적해 더해주었고 그 결과 해당 좌표에 도달할 수 있는 최소값으로 저장이 됩니다. 코드 from collections import deque N, M = map(int, inp...

[백준 BOJ_14501] 퇴사 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀었습니다. cache는 다음과 같습니다. cache[i][0] = i+1번째 날을 포함하지 않는 경우 cache[i][1] = i+1번째 날을 포함하는 경우 for loop을 처음부터 N길이 까지 돌려준 뒤 퇴사...

[프로그래머스_43165] 타겟 넘버 Python 풀이

출처: 프로그래머스 문제 풀이 DFS로 풀어주었습니다. 시작하는 수가 양수일 때와 음수일 때를 넣어준 뒤, 해당 수에서 다음 index의 수를 더해준 값과, 빼준 값을 queue에 넣어줍니다. 모든 수를 다 썼을 때, target과 num이 같다면 answer를 증가시...

[프로그래머스_86052] 빛의 경로 사이클 Python 풀이

출처: 프로그래머스 문제 풀이 각각 turnRight, turnLeft, goStraight 함수는 빛이 d방향에서 들어왔을 때 가야하는 좌표 y, x와 들어가는 좌표를 기준으로 들어가는 방향 d를 return해줍니다. move함수는 주어진 ch에 따라 판단하여 위의...

[프로그래머스_42895] N으로 표현 Python 풀이

출처: 프로그래머스 문제 풀이 동적계획법을 활용한 완전탐색으로 풀었습니다. cache는 다음과 같습니다. cache[num] = [] num개의 N으로 만들 수 있는 수 각각의 cache에는 5, 55, 555, 5555 … 와 같은 수를 넣어줍니다. cache[...

[프로그래머스_43238] 입국심사 Python 풀이

출처: 프로그래머스 문제 풀이 이분탐색으로 풀어주었습니다. 걸리는 시간의 최솟값을 구해야할 값으로 두고 이분탐색을 합니다. lo와 hi를 각각 가능한 최솟값과 최댓값으로 초기화해줍니다. lo = 사람 수(n)와 심사관의 수(len(times))가 같고 모든 심사...

[백준 BOJ_1011] Fly me to the Alpha Centauri Python 풀이

출처: 백준 온라인 저지 문제 풀이 y지점에 도착하기 바로 직전의 이동거리를 반드시 1광년으로 하려 하기 때문에 N이 주어진다면 다음과 같이 이동해야 최소 거리가 됩니다. 보여지는 숫자는 작동 횟수 당 이동하는 거리 1 2 3 ... N/2-1 N/2 N/2-1 ... ...

[프로그래머스_42860] 조이스틱 Python 풀이

출처: 프로그래머스 문제 풀이 그리디 문제라고 하여 그리디로 풀어주려했지만 채점할 때는 그리디 문제로 채점하지 않는다고 합니다. 그래서 구현으로 풀어주었습니다. 일단 바꿀 알파벳을 고르기 위해 커서를 옮기는 가로 움직임(hori_move)과 알파벳을 바꾸는 세로 움직임...

[백준 BOJ_2805] 나무 자르기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이분탐색을 이용하여 풀었습니다. 우선 나무들의 높이를 저장해둔 trees를 내림차순으로 정렬해줍니다. 이분탐색으로 찾을 값을 설정할 수 있는 높이의 최댓값(height)으로 두기 위해 lo와 hi를 height이 가질 수 있는 최솟값...

[프로그래머스_42890] 후보키 Python 풀이

출처: 프로그래머스 문제 풀이 itertool의 combinations를 응용해 풀어보았습니다. combination과 permutation의 작동방식은 아래와 같습니다. from itertools import permutations, combinations items ...

[프로그래머스_43163] 단어 변환 Python 풀이

출처: 프로그래머스 문제 풀이 DFS로 풀었습니다. 가지치기로 일단 target이 단어에 없다면 변환할 수 없기 때문에 제외해주었습니다. 이미 확인해준 단어를 중복하여 확인하지 않기 위해 visited를 만들어주었고, 시작하는 단어랑 한 개의 알파벳만 다른 단어들을 v...

[백준 BOJ_1024] 수열의 합 Python 풀이

출처: 백준 온라인 저지 문제 풀이 아래와 같이 O(N)인 투 포인터 알고리즘으로 시도했지만 런타임 아웃으로 실패했습니다. 더 빠른 알고리즘이 필요한건가 하고 고민하다 문제 유형이 수학인것을 보고 공식을 찾아야겠다고 생각하게 되었습니다. N, L = map(int, in...

[백준 BOJ_1326] 폴짝폴짝 Python 풀이

출처: 백준 온라인 저지 문제 풀이 BFS를 이용해 풀어주었습니다. queue에 시작점(src)를 넣어주며 이미 방문했던 step은 방문하지 않게끔 visited도 같이 넣어주었습니다. dist는 dist가 가질 수 있는 최대 거리인 N+1으로 초기화해주었고 dist를 ...

[백준 BOJ_1270] 전쟁 - 땅따먹기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 구현 문제였습니다. Counter 모듈을 사용하여 가장 많은 수의 troop이 절반을 초과하는 지 확인해주었고, 그렇지 않으면 “SYJKGW”를 출력해주었습니다. 코드 from collections import Counter N ...

[백준 BOJ_2217] 로프 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어 보겠습니다. 문제의 $k$개의 로프를 사용하여 중량이 $w$인 물체를 들어올릴 때, 각각의 로프에는 고르게 $\frac{w}{k}$만큼의 중량이 걸리게 된다는 부분을 다시 이해하면 최대로 올릴 수 있는 중량은 아래와...

[백준 BOJ_9461] 파도반 수열 Python 풀이

출처: 백준 온라인 저지 문제 풀이 파도반 수열이라 해서 피보나치 수열과 크게 다를 바가 없습니다. 피보나치 수열은 fib(N) = (N-1) + (N-2) 이라면, 파도반 수열은 (N-2) + (N-3) 입니다. 동적계획법으로 간단하게 cache[0], cache[...

[백준 BOJ_9251] LCS Python 풀이

출처: 백준 온라인 저지 문제 풀이 예시로 주어진 문자열을 비교하는 표를 만들어보았습니다. 이 표가 그대로 memoization을 위 한 cache가 됩니다. 비교하는 문자가 같을 경우 이전의 공통부분(cache[i-1][j-1])에 문자를 추가해주어야 합니다. 문...

[백준 BOJ_2579] 계단 오르기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 주어진 조건을 예시 input으로 이해해 보았습니다. # stairs = [10, 20, 15, 25, 10, 20] 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. Start $ \rightarrow ...

[백준 BOJ_2565] 전깃줄 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이 문제는 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)의 응용 문제 입니다. 우선, 각 전깃줄을 tuple로 받은 뒤 list에 넣어줍니다. 그런 뒤 list를 tuple 첫 번째 값에 따라...

[백준 BOJ_2156] 포도주 시식 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이 문제에서 중요하게 봐야할 조건은 연속으로 놓여있는 세 잔을 모두 마실 수 없다는 것입니다. 이 부분에서 놓칠 수 있는 부분이 하나 있습니다. 연속으로 놓여있는 세 잔을 모두 마실 수는 없지만 최대로 마실려면 두 잔을 마시고 한 잔만...

[백준 BOJ_1932] 정수 삼각형 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어 보겠습니다. 각 층의 숫자를 담은 tri는 예시 input의 경우에 다음과 같습니다. # tri[floor-1][nums] [ [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4,...

[백준 BOJ_1904] 01타일 Python 풀이

출처: 백준 온라인 저지 문제 풀이 일단 1부터 6까지 만들 수 있는 2진수열을 아래에 나열해보았습니다. N=1: 1 (1) N=2: 11, 00 (2) N=3: 111, 100, 001 (3) N=4: 1111, 1100, 1001, 0011, 0000...

[백준 BOJ_1463] 1로 만들기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어 보겠습니다. cache는 index값으로 헷갈리지 않게 0부터 N+1까지 0으로 초기화된 list로 시작합니다. N=1에는 아무런 연산을 하지 않아도 되기 때문에 0으로 초기화된 값을 딱히 건드리지 않아도 됩니다...

[백준 BOJ_1149] RGB거리 Python 풀이

출처: 백준 온라인 저지 문제 풀이 문제에서 주어진 규칙이 언뜻 보기에는 어려워보이지만 결국 같은 색의 집이 연속해서 칠해지면 안된다는 뜻입니다. Red Green Green (X) Red Green Blue (O) Red Green Red (O) 그러므로...

[백준 BOJ_11053] 가장 긴 증가하는 부분 수열 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어 보겠습니다. cache의 format은 다음과 같습니다. # cache[i] cache[i]: i index까지의 가장 긴 증가하는 부분 수열의 길이 적어도 자기 자신을 포함하니 1로 초기화해줍니다. outer f...

[백준 BOJ_10844] 쉬운 계단 수 Python 풀이

출처: 백준 온라인 저지 문제 풀이 동적계획법으로 풀어 보겠습니다. cache의 format은 다음과 같습니다. # cache[N 자릿수][끝나는 수] cache[1 ~ N][0 ~ 9]: 0 ~ 9로 끝나는 N 자릿수의 개수 한 자릿수(cache[1])는 1부터 9로...

[백준 BOJ_1003] 피보나치 함수 Python 풀이

출처: 백준 온라인 저지 문제 풀이 N에 따라 fib(0)과 fib(1)이 몇 번 호출되는 지 알아보기 위해 0부터 9까지의 결과를 아래에 정리해보았습니다. N fib(0) fib(1) ...

[백준 BOJ_6549] 히스토그램에서 가장 큰 직사각형 Python 풀이

출처: 백준 온라인 저지 문제 풀이 문제를 분할하기 위해 아래의 그림과 같이 히스토그램을 반으로 나눈 뒤 가장 큰 직사각형이 왼쪽에 있는 경우와 오른쪽에 있는 경우, 그리고 나눈 중간에 걸쳐있는 경우 세가지로 분할해주었습니다. 왼쪽과 오른쪽의 경우 중 큰 값으로 저...

[백준 BOJ_11444] 피보나치 수 6 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이 문제는 행렬의 거듭제곱을 이용하여 풀 수 있습니다. 아래의 행렬을 거듭제곱했을 때의 결과를 지켜보면 피보나치 수를 발견할 수 있습니다. [\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}...

[백준 BOJ_10830] 행렬 제곱 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 아래의 행렬의 곱셈을 구하는 선행문제에서 multiply함수를 가져옵니다. [백준 BOJ_2740] 행렬 곱셈 Python 풀이 거듭제곱을 연속하였을 때 수가 커지는 것을 미연에 방지하기위해, 곱해줄 때마다 1000으로 ...

[백준 BOJ_2740] 행렬 곱셈 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이 문제는 분할정복으로 해결이 가능하지만 N과 M의 크기가 100으로 제한되어 있기 때문에 슈트라센 알고리즘보다 3중 for loop를 쓰는 것이 더 효율적이게 됩니다. 행렬의 거듭제곱 문제를 위해 푸는 선행문제라고 봐도 되기 때문에 ...

[백준 BOJ_2630] 색종이 만들기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 종이의 한변의 길이 n과 시작하는 좌표 (y, x)를 받는 quadtree함수를 만들어 주었습니다. n이 1일때는 제일 작은 경우(기저사례) 이기 때문에 해당 좌표의 값을 포함한 list로 반환해줍니다. 문제에서 힌트를 얻을 수...

[백준 BOJ_1992] 쿼드트리 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 영상의 크기 n과 시작하는 좌표 (y, x)를 받는 quadtree함수를 만들어 주었습니다. n이 1일때는 제일 작은 경우(기저사례) 이기 때문에 해당 좌표의 값을 반환해줍니다. 문제에서 힌트를 얻을 수 있듯이 영상을 좌측상단...

[백준 BOJ_1780] 종이의 개수 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 영상의 크기 n과 시작하는 좌표 (y, x), 그리고 각각의 종이의 개수를 세주는 list인 cnt를 받는 nonatree함수를 만들어 주었습니다. cnt[0]에는 -1 종이의 개수를, cnt[1]에는 0 종이의 개수를, cnt[...

[백준 BOJ_1629] 곱셈 Python 풀이

출처: 백준 온라인 저지 문제 풀이 분할정복을 이용해 거듭제곱을 더 빨리 계산할 수 있습니다. 주어진 지수를 반으로 나눈 지수만큼의 거듭제곱을 한 값을 두번 곱해주는 방식입니다. 지수가 홀수 일 경우에는 반으로 나눈 값을 두번 곱해준 뒤 n을 한번 더 곱해줍니다. 각 ...

[백준 BOJ_11401] 이항 계수 3 Python 풀이

출처: 백준 온라인 저지 문제 풀이 이항계수는 다음과 같은 공식으로 구해집니다. \[\binom{N}{K}=\frac{N!}{K!(N-K)!}\] 이러한 이항계수 공식을 페르마의 소정리를 이용하여 다르게 쓸 수 있습니다. 페르마의 소정리란: \[a^{p}\eq...

[백준 BOJ_7568] 덩치 Python 풀이

출처: 백준 온라인 저지 문제 풀이 몸무게와 키의 정보를 tuple로 이루어진 list로 받아줍니다. 등수는 1부터 시작하니 1로 초기화된 N의 크기의 list를 준비합니다. 이중 for loop으로 각각의 몸무게와 키를 비교한 뒤 비교 대상보다 작을 경우 해당 inde...

[백준 BOJ_2798] 블랙잭 Python 풀이

출처: 백준 온라인 저지 문제 풀이 삼중 for loop을 이용하되, 자기 자신을 한번 더 더해주는 것을 막기 위해 for loop의 범위를 제한해줍니다. 첫번째 for loop의 범위는 마지막 두 숫자를 포함하지 않아야하며, (i) 두번째 for loop의 범위는 i의 다...

[백준 BOJ_2447] 별 찍기 - 10 Python 풀이

출처: 백준 온라인 저지 문제 풀이 1 분할 정복 알고리즘을 이용하여 풀어보겠습니다. 분할 정복: 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 방법 N=27이라면 27*27을 9*9로, 9*9를 3*3로, 3*3을 1*1까지 분할시킬 수 있습니다...

[백준 BOJ_2231] 분해합 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 각 자리수의 합을 구해주는 decompose 함수를 재귀호출로 만들어주었습니다. N을 10으로 나누었을 때의 나머지값을 더해주며 N을 10으로 나눈 값으로 재귀호출해줍니다. 더 이상 10으로 나누지 못할 때는 N이 한 자릿수임을 뜻...

[백준 BOJ_1436] 영화감독 숌 Python 풀이

출처: 백준 온라인 저지 문제 풀이 단순히 처음에 문제를 보았을때 예시로 666이 제일 작은 숫자이며 그 다음으로는 1666, 2666, 3666 … 이라 하기 때문에 그다지 어려운 문제로는 보이지 않지만, 이 문제에서는 패턴을 벗어나는 예외의 값을 찾아내는 것이 중요하다고...

[백준 BOJ_11729] 하노이 탑 이동 순서 Python 풀이

출처: 백준 온라인 저지 문제 풀이 하노이 탑에서는 출발지, 경유지, 목적지의 개념이 중요합니다. 결과적으로는 출발지가 1번, 경유지가 2번, 목적지가 3번이 됩니다. 먼저 N=1의 경우에는 상관없이 1번에서 3번으로 옮길 수 있습니다. N=2의 경우에는 1번에서 ...

[백준 BOJ_10872] 팩토리얼 Python 풀이

출처: 백준 온라인 저지 문제 풀이 팩토리얼의 공식은 아래와 같습니다. \[N! = 1 \times 2 \times \dots \times \left(N-1\right) \times N \quad \left(0! = 1\right)\] 이 공식은 아래 같이도 표현 가...

[백준 BOJ_10870] 피보나치 수 5 Python 풀이

출처: 백준 온라인 저지 문제 풀이 피보나치의 수를 구하는 공식은 문제에서 주어졌듯이 아래와 같습니다. \[F_n = F_{n-1} + F_{n-2} \quad(n\ge2)\] 그러므로 기저 사례(base case)는 $F_0$과 $F_1$이 됩니다. 그 이후로는 $F...

[백준 BOJ_1018] 체스판 다시 칠하기 Python 풀이

출처: 백준 온라인 저지 문제 풀이 우선 칠해야 하는 칸의 수를 반환해주는 check 함수를 따로 만들었습니다. board와 시작하는 좌표 y와 x의 값을 받고 주어진 y와 x에서 시작하여 64개의 칸을 모두 체크하며 칠해야 하는 칸의 수를 세어 주었습니다. 패턴의 시...

[Algospot_BOARDCOVER] 게임판 덮기 Python 풀이

문제 출처: Algospot 온라인 저지 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 ...

[Algospot_PICNIC] 소풍 Python 풀이

문제 출처: Algospot 온라인 저지 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않...

[Algospot_BOGGLE] 보글 게임 Python 풀이

출처: Algospot 온라인 저지 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로...

Back to top ↑

Boostcamp AI Tech

[DL Basic] Optimization

Gradient Descent (경사하강법) First-order iterative optimization algorithm for finding a local minimum of a differentiable function 1차 미분한 값을 가지고 반복...

[AI Math] 베이즈 통계학 맛보기

조건부 확률 $P(A \mid B) = $ 사건 B가 일어난 상황에서 사건 A가 발생할 확률 \[= P \left (\frac{A \cap B}{B} \right)\] \[=\frac{P(A \cap B)}{P(B)}\] 위의 식에서 다음과 같은...

[AI Math] 통계학 맛보기

통계적 모델링 적절한 가정 위에서 확률분포를 추정(inference)하는 것이 목표 기계학습과 통계학이 공통적으로 추구하는 목표 유한한 개수의 데이터만으로 모집단의 분포를 알아내는 것은 불가능, 근사적으로 확률분포를 추정할 수 밖에 없다. 예측모형의...

[AI Math] 확률론 맛보기

딥러닝과 확률론 딥러닝은 확률론 기반의 기계학습 이론에 바탕 손실함수(loss function)들의 작동 원리는 데이터 공간을 통계적으로 해석해서 유도 예측이 틀릴 위험을 최소화하도록 데이터를 학습 회귀분석의 손실함수를 계산할 때 쓰이...

[AI Math] 딥러닝 학습방법 이해하기

비선형 모델 신경망(neural network) 선형모델로는 분류문제나 복잡한 패턴의 문제를 풀기 힘들다. 그런 모델을 풀기 위해 비선형모델인 신경망(neural network)를 사용 신경망은 선형모델과 활성함수(activation function)를 합성한 함수 ...

[AI Math] 경사하강법 - 매운맛

경사하강법으로 선형회귀 계수 구하기 선형회귀 목적식 = $\lVert y - X\beta \rVert_2$ 목적식을 최소화하는 $\beta$를 찾아야 하므로 목적식을 각각의 $\beta_k$로 미분한 다음과 같은 그레디언트 벡터를 구해야 한다. [\nabla_{\bet...

[AI Math] 경사하강법 - 순한맛

경사하강법 미분 (differentiation) 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구 \[f'(x) = \lim_{h \to 0}\frac{f(x+h)-f(x)}{h}\] 미분은 함수 $f$의 주어진 점 $(x, f(x))$에서의 접선...

[AI Math] 행렬이 뭐에요

행렬이란? 행(row) 벡터를 원소로 가지는 2차원 배열 행(row)과 열(column)이라는 인덱스(index)를 가진다. 행렬의 특정 행(열)을 고정하면 행(열) 벡터라 부른다. 전치행렬 (transpose matrix): 행과 열의 인덱스가 바뀐 행렬 ...

[AI Math] 벡터가 뭐에요

벡터란? 숫자를 원소로 가지는 리스트(list) 또는 배열(array) 공간에서 한 점을 나타냄 원점(0, 0)으로부터 상대적 위치를 표현 벡터의 연산 숫자를 곱해주면 길이만 변함 (스칼라 곱 scala product) 벡터끼리 같은 모양을 가지면 덧셈, ...

Back to top ↑

Machine Learning

[머신러닝] 07. 머신러닝 지도

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 나에게 필요한 머신러닝을 찾아내는 방법 머신러닝 지도 아래의 머신러닝 지도를 따라가며 어떤 머신러닝 학습법을 이용해야 될지 알아낼 수 있다.

[머신러닝] 06. 강화학습 (reinforcement learning)

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 강화학습 Reinforcement Learning 강화학습 더 좋은 결과를 내기 위해 스스로 노력하며 수련하는 것 지도학습 vs. 강화학습 지도학습이 배움이라면 강화학습은 경험이다. ...

[머신러닝] 05. 비지도학습 (unsupervised learning)

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 비지도 학습 비지도학습 비지도학습을 통해 가지고 있는 데이터의 새로운 의미나 관계를 밝혀낼 수 있다. 군집화 (clustering) 비슷한 것을 찾아서 그룹을 만드는 것 군집화 vs. 분류 ...

[머신러닝] 04. 지도학습 (supervised learning)

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 지도학습 Supervised Learning 머신러닝1 - 회귀 VS 분류 지도학습 가지고 있는 과거의 데이터에 독립변수(원인)와 종속변수(결과)가 있을 때는 지도학습을 이용할 수 있다. 지도학습 = 역...

[머신러닝] 03. 머신러닝의 분류

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 머신러닝의 분류 머신러닝의 여러 분야들 지도학습 (supervised learning) 문제집을 풀듯이 문제와 정답을 비교하고 맞추며 문제풀이에 익숙해지는 것 정답이 있는 문제를 해결하는 ...

[머신러닝] 02. 독립변수와 종속변수

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 독립변수와 종속변수 독립변수 vs. 종속변수 변수들의 관계 값이 변하고 있는 열(Column)은 변수이다. 온도와 판매량은 값이 같이 변하고 있기 때문에 서로 상관관계이다. 온도가 원인이 되고 판매...

[머신러닝] 01. 표 (data set)

강좌 출처 아래 링크의 강좌를 학습한 내용입니다. 머신러닝1 - 표 행과 열의 다른 표현들 데이터 산업에서의 표 아래의 두 가지 방법으로 표를 만들 수 있으나, 데이터 산업에서는 오른쪽의 표처럼 입력하기로 하였다.

Back to top ↑

Deep Learning

[딥러닝] 객체 검출(Object Detection) R-CNN

출처 이 포스팅은 아래의 강좌를 진행하며 정리한 글입니다. 객체 검출(Object Detection) 딥러닝 기술: R-CNN, Fast R-CNN, Faster R-CNN 발전 과정 핵심 요약 R-CNN 동작과정 Selec...

[딥러닝] Intro to TensorFlow

프로젝트 소개 이 프로젝트는 아래 링크의 생활코딩의 딥러닝 강좌를 진행하며 학습하였습니다. Tensorflow (python) 프로젝트 동기 생활코딩의 머신러닝1 강좌를 들은 뒤 딥러닝에도 흥미가 생겼고 실제로 코드를 작성하며 실습하...

Back to top ↑

Sorting

퀵 정렬(quick sort)

퀵 정렬은 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할합니다. 이를 위해 퀵 정렬은 파티션(partition)이라고 부르는 단계를 도입하는데, 이는 배열에 있는 수 중 임의의 ‘기준 ...

병합 정렬(merge sort)

병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬합니다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다. 병합 정렬은 각 단계마다 반으로 나눈 부분 문제를 재귀 호출을 이용해 해결...

선택 정렬(selection sort)

선택 정렬은 모든 $i$에 대해 $A[i…N-1]$에서 가장 작은 원소를 찾은 뒤, 이것을 $A[i]$에 넣는 것을 반복합니다. 찾는 과정이 inner for loop, 시간 복잡도는 $O(N)$이기 때문에 선택 정렬은 최악의 경우와 최선의 경우 모두 $O(N^2)$의 시간 복잡...

삽입 정렬(insertion sort)

삽입 정렬은 전체 배열 중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일을 반복하는 방식으로 동작합니다. 삽입 정렬의 최선의 경우는 처음부터 이미 정렬된 배열이 주어지는 경우입니다. 모든 원소는 처음부터 제자리에 있기 때문에 j에 대한 while문은 매번 즉시 종료하게 됩니다...

Back to top ↑

Python for Coding Test

[이코테 강좌] 다이나믹 프로그래밍

출처 이 포스팅은 아래의 강좌를 진행하며 정리한 글입니다. (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산한 결과...

[이코테 강좌] 이진 탐색

출처 이 포스팅은 아래의 강좌를 진행하며 정리한 글입니다. (이코테 2021 강의 몰아보기) 5. 이진 탐색 이진 탐색 순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 정렬되어 ...

[이코테 강좌] Greedy(탐욕법)

출처 이 포스팅은 아래의 강좌를 진행하며 정리한 글입니다. (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 문제를 풀기 위한 최소한의 아이디어를 떠...

Back to top ↑

Algorithm and Data Structure

[알고리즘 문제해결전략] 분할 정복

분할 정복(Divide & Conquer)이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 방법 일반적인 재귀 호출과 분할 정복의 차이 분할 정복이 일반...

[알고리즘 문제해결전략] 알고리즘 설계 패러다임

무식하게 풀기 ‘무식하게 푼다(brute-force)‘는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부...

[알고리즘 문제해결전략] 알고리즘 분석

알고리즘(Algorithm)이란? 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 한 가지 방법을 명료하게 써 놓은 것 알고리즘을 평가하는 두 가지의 큰 기준은 알고리즘이 사용하는 시간과 공간입니다. 시간: 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작...

Back to top ↑

Operating System

[OS 공룡책] Chapter 3. 프로세스

본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 Operating System Concept 10th 을 바탕으로 작성하였습니다. 프로세스는 실행 중인 프로그램을 말하며, 현대의 컴퓨팅 시스템에서 작...

[OS 공룡책] Chapter 2. 운영체제 구조

본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 Operating System Concept 10th 을 바탕으로 작성하였습니다. 2.1 운영체제 서비스 (Operating-System Service...

[OS 공룡책] Chapter 1. 서론

본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 Operating System Concept 10th 을 바탕으로 작성하였습니다. 운영체제(operating system) 는 응용 프로그램을 위한 기...

Back to top ↑

Python

[Python] Flask로 tensorflow SavedModel 배포하기

왜 Flask? Flask란 Python을 사용해서 Web Server를 만들 수 있게 도와주는 Web Framework다! 인공지능 프로젝트에서 인공지능 모델을 웹서비스에 적용하는 과정에서 처음에는 tensorflow.js를 사용했는데, 생각보다 소스코드가 많이 없어서 적용하...

[Python] venv 가상환경 구축하기

가상환경 venv venv는 python 설치하면 같이 설치되어 제공되기 때문에 따로 설치해줄 필요가 없다. 가상환경을 구축하는 이유는 프로젝트마다 필요로하는 모듈의 버전을 분리하여 관리해주기 위함이다. 가상환경 구축 $ python -m venv 가상환경이름 가상환경 구...

[Python] AWS S3에서 이미지 로드하기

모듈 설치 import 해야 되는 모듈은 다음과 같다. import os import dotenv import boto3 import PIL.Image as image 각각 모듈은 다음과 같은 명령어로 설치 가능하다. $ pip install python-dotenv $ ...

Back to top ↑

Job Hunting

[취뽀일기] 2022년도 하반기 CJ올리브네트웍스 1차 면접

코딩 테스트 합격 4월 28일 목요일, 합격 통보를 받았다! 면접 준비 아무래도 1차 면접은 직무면접이기 때문에 자소서에 언급한 내용 위주로 나올 질문들을 예상하여 준비하였다. 지원서에 학부 때 들은 수업을 기입하는 부분이 있어 나는 생체인식 수업을 넣었는데 관련해서 물어볼 ...

Back to top ↑

Unity

[Unity] 간단한 2D RPG 게임 만들기

프로젝트 소개 이 프로젝트는 아래 링크의 강좌를 진행하며 학습하였습니다. https://hoil2.tistory.com/5 프로젝트 동기 Unity 활용에 보다 익숙해지기 위해서 이 프로젝트를 진행하게 되었습니다. 프로젝트 언어 ...

Back to top ↑