⏰ 시간복잡도 Python에서 1초에 약 2천만 연산 가능 시간복잡도 계산할 때 적용해볼 것 🔎 완전탐색 input의 개수가 현저히 적을 때 사용 가능 🥞 스택 문자열에서 문자열을 출력해야할 때 그리고 그 조건이 입력 문자열을 활용하는 문제에서 사용 투스택
저도 매운 음식을 참 좋아하는데요. 한 번 문제를 풀어보도록 하겠습니다. 목표 시간: 60분 마감 시간: 00:50 제출 시간:
목표 시간: 100분마감 시각: 02:28제출 시각: 02:58저도 공항에 들릴 때면 항상 입국 심사를 하고는 했는데요.요새 취업준비 때문에 바빠 해외 여행을 못 갔네요. 😭 아쉬운 마음을 뒤로 한 채 문제를 풀어보았습니다.
목표 시간: 60분소요 시간: 105분
1년 전부터 내 머리를 아프게 하였던 문제 ...파이썬으로 풀면 시간 초과를 피하기 힘들다. 파이파이로 제출하자
이 문제를 왜 큐를 사용했을까?그건 아마도... 잘 ~ 생각을 해보면 선입선출 구조의 문제이기 때문이다 ! ㅎㅎ가장 앞에 있는 기능이 나가지 않는 이상 뒷 기능들은 못 나가니까그것이 곧 큐의 특성 ~! 😣😣😣
최소비용 구하기 알고리즘 분류 [다익스트라 알고리즘] 이 문제에서 왜 다익스트라를 사용해야 할까? 그 이유는 다음과 같다. 출발 도시에서 도착 도시로 가는 것이니 단일 노드 - 단일 노드이고 버스 비용이 발생하고 이는 양수이니까 Edge에 양수 weight가 있는 카테고리로 분류가 된다.
Σ solved_acClass4] [시그마 문제 실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇...
조합 solved_acClass4] [조합 문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 nCm을 출력한다. 예제 입력 1 예제 출력 1 어떤 알고리즘을 쓰는가 [재귀] 1트 combinaion 모듈을 사용하여 날먹좀 하려 했지만 역시나 시간초과 2트, 재귀 (76ms)...
별 찍기 - 11 solved_acClass4] [별 찍기 -11 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 예제 출력 1 ...
토마토 solved_acClass3] [토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. img 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의...
DFS와 BFS solved_acClass3] [DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 ...
DSLR solved_acClass3] [DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자...
패션왕 신해빈 solved_acClass3] [패션왕 신해빈 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠...
비밀번호 찾기 solved_acClass3] [비밀번호 찾기 문제 2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민...
카잉 달력 solved_acClass3] [카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다....
IOIOI solved_acClass3] [IOIOI 문제 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 ...
📖 최소 힙 solved_acClass3] [최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 1.배열에 자연수 x를 넣는다. 2.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입...
듣보잡 solved_acClass3] [듣보잡 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보...
🏠 단지번호붙이기 solved_acClass3] [단지번호붙이기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상...
절댓값 힙 solved_acClass3] [절댓값 힙 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 1.배열에 정수 x (x ≠ 0)를 넣는다. 2.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그...
🔎 미로 탐색 solved_acClass3] [미로 탐색 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 ...
🔎 경로 찾기 solved_acClass3] [경로 찾기 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 ...
🍅 토마토 (3차원) solved_acClass3] [토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. img 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수...
🦠 바이러스 solved_acClass3] [바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 ...
🔨 벽 부수고 이동하기 solved_acClass4] [벽 부수고 이동하기 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 ...
🧀 치즈 solved_acClass4] [치즈 문제 img N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 ...
💣 문자열 폭발 solved_acClass4] [문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어...
플로이드 solved_acClass4] [플로이드 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그...
🎓 서강그라운드 solved_acClass4] [서강그라운드 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을...
🍗 치킨 배달 solved_acClass4] [치킨 배달 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시...
🚙 특정한 최단 경로 solved_acClass4] [특정한 최단 경로 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 ...
🌳 이진 검색 트리 solved_acClass4] [이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. img 전위 순회...
🗳 게리 맨더링 2 📖 알고리즘 👉🏻 브루트 포스 알고리즘은 [문제 제한 조건이 작을 때] 써볼까? 할 수 있다. 사실 "작다"라는 개념은 상대적이기에 가늠하기 어려울 수도 있지만 이 문제의 조건을 봐보자. 5 ≤ N ≤ 20 1 ≤ Ar ≤ 100 딱 봐도 작다는 Feel이 온다 ... 때로는 단순무식한 방법이 통한다. 📐 설계 연습...
🕵🏻♂️ 골드바흐의 추측 📖 알고리즘 👉🏻 에라토스테네스의 체는 [소수 검증]을 할 때 사용한다. 이 문제의 핵심은 특정 숫자가 소수인지 아닌지 판별을 해야한다는 것이다. n = a+b일 때, b-a가 최대가 되도록 설정을 해야하므로 2부터 n-1까지 소수 판별을 해야한다. 이해가 쉽도록 예를 들어보겠다. 📐 설계 연습장-67 b...
🚌 최소비용 구하기 2 최소비용 구하기 2 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여...
📱 반도체 설계 반도체 설계 문제 반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어...
🔥 불! 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각...
👍🏻 좋다 좋다 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타...
🔎 소수 찾기 Class2] [소수 찾기 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로
5️⃣ 오목 오목 문제 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 화면 캡처 2022-07-28 194358...
💬 문자열 압축 Class2] [문자열 압축 문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여...
🪢 수 묶기 수 묶기 문제 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수...
🔢 N으로 만들기 N으로 만들기 문제 준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다. 처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다. 다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다. 수의 왼쪽에 숫자...
📱 앱 앱 문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에...
🍶 물통 물통 문제 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손...
🌀 소용돌이 예쁘게 출력하기 소용돌이 예쁘게 출력하기 문제 크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다. 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된...
🐊 먹을 것인가 먹힐 것인가 먹을 것인가 먹힐 것인가 문제 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-...
🦠 거리두기 확인하기 Level2] [거리두기 확인하기 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다...
N으로 표현 Level3] [N으로 표현 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가...
☎️ 전화번호 목록 Level2] [전화번호 목록 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를...
🟰 후위 표기식 후위 표기식 문제 수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위...
배열의 길이가 최대 13이므로 삼중 반복문을 사용해도 시간 초과에 걸리지 않는다.따라서 완전 탐색을 이용함
이정연의 코딩테스트 대비 프로그래머스 Level1 정복
코딩테스트 대비 프로그래머스 1단계 부수기
CODE
CODE
CODE
숫자 문자열과 영단어해시 자료구조를 이용하면 정말 쉽게 풀 수 있는 문제...하지만 그걸 떠올리지 못 하고 일일이 직접 구현하였다.
문제 링크 CODE 고찰 0의 개수를 셀 때 count 메서드를 이용하면 간편하다.
문제 링크
string.upper(): 대문자 변환 string.lower(): 소문자 변환 나의 CODE 코드를 작성하면서도 "이렇게 푸는 것이 맞나..?" 하는 의문이 들었다. 당연히 아니었다. 이런 단순무식한 방법보다 더욱 빠르고 간결한 코드가 있었으니! 바로 정규 표현식을 활용한 코드다. 정규 표현식 참고 블로그 베스트 CODE
CODE
프로그래머스 1단계 부수기
문제 링크
문제 링크
그리디로 접근하면 된다.
문제 링크프로그래머스 환경에서 디버깅은 참 쉽지 않다 ...문제를 너무 더럽게 푼 느낌이 든다.
이진수 변환 메서드에 대하여 배웠다.format 메서드를 사용하면 다양한 진법에 맞추어 숫자를 변환시킬 수 있다.이 때 b는 binary를 의미한다.
CODE
JadenCase
Binary Transform
피보나치 수유명한 문제. 기초도 다질겸 DP로 한 번 풀어보았다.
프로그래머스 Level2 - 2018 Summer/Winter Coding
프로그래머스 LEVEL 2 / 2017 팁스타운
프로그래머스 LEVEL2 / 연습문제
프로그래머스 Level1
프로그래머스 Level1 , ASCII 코드 활용
프로그래머스 Level1
프로그래머스 Level1
프로그래머스 Level1
프로그래머스 Level1
Intro Link 문제 링크 CODE (stage,실패율) 리스트에서 실패율은 내림차순, stage는 오름차순 정렬
🏠 단지번호붙이기 solved_acClass3] [단지번호붙이기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서
토마토 solved_acClass3] [토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. img 창고에 보관되는 토마토들 중에는 잘 익은 것도 있
문제 소개 대표적인 문제로 백준의 평범한 배낭 문제가 있다. 라벨링 냅색 알고리즘은 다음과 같은 조건/문제에서 가져다 쓴다. 조건: 무게 리스트, 가치 리스트, 최대 무게 문제: 최대 가치 이 때, (무게,가치)를 지닌 물품을 쪼갤 수 있을 때(설탕 같이) fractional로 접근하고 쪼갤 수 없을 때는 0-1 냅색으로 접근한다. 0-1 냅색 (...
용도 구현 그림 다익스트라를 구현하는 방법은 여러 가지가 있지만 가장 효율적인 방법은 [우선순위 큐]를 활용하는 방법이다. 그래프가 그림과 같이 주어져있다. A 노드에서 출발한다고 가정한다. 이 때 자기 자신으로 가는 최단 거리는 0이고 나머지 노드들에 대해서는 무한대로 초기화를 한다. 우선순위 큐에서 팝을 한 게 현재 노드이다.
프로그래머스 레벨1 정복
프로그래머스 레벨1 정복
프로그래머스 레벨1 정복
프로그래머스 레벨1 정복
프로그래머스 레벨1 정복
Level1 정복
프로그래머스 Level2
프로그래머스 Level2
프로그래머스 Level2
2018 KAKAO BLIND RECRUITMENT
➕➖✖️➗ 문제 설명 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한 조건 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 입출력 예...
프로그래머스 고득점 kit
프로그래머스 고득점 kit
프로그래머스 고득점 kit - Greedy
프로그래머스 연습문제 1단계
프로그래머스 레벨1 연습문제
문제 링크 풀이 heap 자료 구조를 이용하면 쉽게 풀 수 있다. python은 최소 힙이므로 k개를 유지하며 0번 인덱스를 뽑아주면 최하 점수를 알 수 있다. 코드
문제 링크 해설 이 문제는 그리디로 접근해야 한다. 왜냐하면 귤의 사이즈 중에서 개수가 많은 것을 우선 순위로 선택해야 하기 때문이다. 귤의 사이즈별 개수를 어떻게 파악할까? 해시 자료구조를 이용하면 {사이즈: 개수} 형식으로 정리를 할 수 있다. 개수가 많은 것을 우선순위로 선택한다는 점을 이용하여 최대힙을 떠올렸다. 왜냐하면 최대힙은 pop을 하게 ...
카카오 2020 기출 문제 링크 스택 문자열 관련 문제는 보통 스택부터 떠올린다. 이 문제 또한 2개의 스택을 활용하면 어렵지 않게 풀 수 있다. 스도 코드 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없...
올바른 괄호
124 나라의 숫자 풀이 규칙 발견하기가 너무 어려웠다 ... 😭 n%3이 0 ➡️ 4 / 1 ➡️ 1 / 2 ➡️ 2 n = n//3 n%3 = 0인 경우에만 n을 1 감소 n이 0이 될때까지 반복 n = 15인 경우를 예시를 들어보겠다. 15%3 = 0 ➡️ 마지막 숫자 4 n = 15//3 = 5 15%3 = 0 이므로 n = 5-1 =...
촌수계산
장애물 인식 프로그램 풀이 특징이라면은... visited 배열을 생성하지 않고 graph를 수정하며 중복 방지를 했다. 우리는 1을 지나다니며 탐색을 하기 원하기 때문에 이미 방문한 지점을 0으로 수정하여 재방문 하지 않게 설계했다. 초기 조건 n: 그래프의 가로/세로 길이 graph: 2차원 행렬, 1은 장애물 0은 길을 의미 최종 문제 b...
거리 합 구하기 정말 어려웠다. 결국 해설 강의 참조 😭 다익스트라/플로이드 와샬 두 가지 방법으로 시도해봤지만 실패! 그 이유는 다익스트라는 O(ElogE)의 시간복잡도를 갖는데 이 문제는 모든 노드로부터 다익스트라를 수행해야하므로 O(E^2logE)의 시간복잡도를 갖는다. 대충 연산량이 E^2이라고 해도 최대 연산량은 (4*10^10) = 400...
플레이페어 암호 풀이 특정 알고리즘의 사용보다는 주어진 조건을 차근차근 구현하는 문제. devide 인풋 메시지로 두 글자 암호화된 리스트 반환 string 형태로 반환해도 되지만 뒤의 함수에서 편리한 재사용을 위해 string list로 반환함. > Ex) HELLOWORLD > ['HE', 'LX', 'LO', 'WO', 'RL', 'DX'...
업로드중.. 금고털이 풀이 전형적인 냅색 알고리즘 문제다. 그 중에서도 그리디로 접근 가능한 fraction knapsack이다. 최대 가치를 항상 먼저 뽑아줘야 하는 게 포인트이므로 내림차순 정렬으로 풀었는데 시간 초과가 발생했다. 그래서 최대힙을 이용하여
지도 자동 구축 초반에 감을 못 잡아서 예상치 못한 시간을 잡아먹었다 ... 풀이 점 개수 1단계: 3^2 = (2+1)^2 2단계: 5^2 = (3+2)^2 3단계: 9^2 = (5+4)^2 4단계: 17^2 = (9+8)^2 . . . n단계: ([(n-1)단계 밑]+2^(n-1))^2 코드
소프티어 ⭐️⭐️
소프티어 ⭐️⭐️⭐️
소프티어 코딩테스트 연습문제
소프티어 코딩테스트 연습문제
https://softeer.ai/practice/info.do?idx=1&eid=583 과정 설계 BFS 기본 골격에 문제 조건을 첨가해주면 된다. 큐의 원소를 (x,y,count,who)로 설정했다. who: 태범이인지 소나기인지? x,y: 태범 혹은 소나기의 좌표 count: 태범이의 현재까지 이동 거리 2트에 성공했는데 소나기가 여러 개...
과정 설계 컴퓨터 배열 nlist를 이분탐색으로 정답 oldcom을 찾는다. start = 1 , end = 2*10^9으로 초기화 하고 mid를 중간 지점으로 잡는다. n_list의 모든 원소에 대하여 업그레이드 비용을 계산해봤을 때, 주어진 예산(B)를 초과하면 end를 mid로 변경하고 B 이하라면 start를 mid+1로 변경한다. 코드
LIS를 가져올 수 있느냐? 설명은 여기
https://softeer.ai/practice/info.do?idx=1&eid=1256 설계 tree_matrix: dictionary로 이루어진 2차원 배열이다. dictionary는 'L'과 'R'로 나뉘며 각각 왼쪽에서 올라온 업무, 오른쪽에서 올라온 업무를 뜻한다. Ex) tree_matrix = [ {'L':[], 'R':[]}, {'...
소프티어 레벨 3
소프티어 레벨3
프로그래머스 신규
소프티어 레벨3
프로그래머스 레벨2
프로그래머스 레벨2
프린터 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서...
백준 실버2
프로그래머스 레벨3
문제 설명 원래 문제 설명은 따로 안 적고 바로 풀이를 기록했지만 ... 간혹가다 문제 이해가 안 간 사람들이 있을 수도 있을 것 같아서 앞으로 추가하려고 한다. 나도 가끔 문제 이해가 안 되는 것들이 있어서 ㅎㅎ 역지사지! 이 문제는 주어진 숫자 리스트에서 연산자를 끼워넣는 문제이다. 예를 들어, 숫자 = [1,2,3,4,5] , 연산자 = [+,...
[Silver IV] 숫자 카드 2 - 10816 문제 링크 성능 요약 메모리: 113624 KB, 시간: 2504 ms 분류 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵 문제 설명 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근...
[Bronze II] 진법 변환 - 2745 문제 링크 성능 요약 메모리: 113112 KB, 시간: 116 ms 분류 수학, 구현, 문자열 문제 설명 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자...
Hashing 문제 링크 성능 요약 메모리: 113112 KB, 시간: 112 ms 분류 문자열, 해싱 문제 설명 APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는...
[Gold IV] 최단경로 - 1753 문제 링크 성능 요약 메모리: 149508 KB, 시간: 704 ms 분류 그래프 이론, 데이크스트라 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와...
프로그래머스 Level3
백준 골드5
백준 브론즈1
프로그래머스 레벨2
삼성 SW 역량 테스트 기출문제 Python 풀이
삼성 SW 역량 테스트 [주사위 굴리기] 파이썬 풀이
삼성 SW 역량 테스트
백준 골드5
프로그래머스 레벨3
구름 레벨3
프로그래머스 스택/큐 고득점 키트
구름 LEVEL 난이도3
코딩테스트 버스트!!!
코테 버스트 !!!
코테 버스트!
문제 링크 설계 solution end point 기준 오름차순 정렬 end point 이전에 시작하는 미사일 탐색 요격 미사일 개수 증가
문제 링크
1일 1 알고리즘 챌린지
알고리즘 해결책 모색력을 기르기 위한 꾸준한 훈련.
문제 링크 핵심 z --> a로 가는 방법을 잘 생각해봐야 한다. CODE
프로그래머스 레벨1 업데이트 되었길래 정복하고자 ... ^-^
레벨2
레벨1
레벨2
레벨2
레벨3
레벨3
골드5
골드4