본문 바로가기

코딩테스트51

JSON Parsing request와 json 패키지를 사용해서 JSON 데이터를 파싱할 때, 각 키의 데이터를 수정하려면 아래처럼 dictionary 형태로 변환시켜 value를 수정한다.data = {"key1":"value1"} data["key1"] = "value2" 전체 데이터를 스캔하여 특정 값을 가진 키를 찾으려고 한다. 아래 코드로 (for, if로) 전체를 확인하면서 원하는 값을 가진 키를 찾았다.data = { "key1":"value1", "key2":"value2", "key3":"value3", "key4":"value4", "key5":"value5", } for key in data: if "value3" == data[key]: print(key) break 간단한 데이터라면 위 방식으로도 충분.. 2023. 3. 19.
[프로그래머스][Lv.2][Python] 최댓값과 최솟값 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12939 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 split 하고 min, max 함수로 결과 return 3. 코드 def solution(s): list_s = [int(x) for x in s.split(" ")] return f'{min(list_s)} {max(list_s)}' 4. 결과 2022. 10. 1.
[프로그래머스][Lv.2][Python] 땅따먹기 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근방식 DP문제이다. 바텀업 방식으로 해결하면 좋다. 점화식 : 4개의 열(Column) 중 현재 열과 같은 열을 제외한 나머지 값 중 최대값을 현재값에 더한다. for j in range(4): land[i][j] += max([land[i-1][x] for x in list({0, 1, 2, 3} - {j})]) 가장 큰 합들이 마지막 열에 반영되었기 때문에 가장 아래 열에서.. 2022. 10. 1.
[프로그래머스][Lv.2][Python] 카펫 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근방식 주어진 brown과 yellow의 개수는 해당 색 부분의 넓이와 같다. 가로를 x, 세로를 y라고 할 때, 주어진 brown과 yellow의 조합으로 xy와 x+y를 알 수 있다. 간단한 이차방정식을 만들고 이후는 완전탐색으로 값을 찾음 3. 코드 def solution(brown, yellow): answer = [] x_y = int(brown / 2) + 2 xy =.. 2022. 10. 1.
[프로그래머스][Lv.2][Python] 올바른 괄호 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 괄호가 "("면 push 한다. 괄호가 ")"면 pop한다. 문자열의 반복이 끝났을 때, 스택에 값이 남아있다면 잘못된 괄호이다. 3. 코드 def solution(s): list_stack = [] for ch in s: if ch == "(": list_stack.append(ch) else: if list_stack == []: return False else: l.. 2022. 10. 1.
[프로그래머스][Lv.2][Python] H-Index 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 H-Index는 N편의 논문중 H번 인용된 논문이 H편 이상일 때의 최대값을 의미한다. 논문의 순서는 중요하지 않다. H-Index는 내부의 인용된 회수와 같지 않을 수도 있다. 3. 코드 def solution(citations): citations = list(reversed(sorted(citations))) len_citations = len(citations) .. 2022. 10. 1.
[프로그래머스][Lv.1][Python] 다트 게임 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/17682 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 S, D, T, *, #을 공백을 포함하여 replace 후 공백으로 split 해주면 서로 분리됨(마지막 공백은 제거) 각 기호에 맞는 점수를 제곱해서 정수로 변경해줌 *은 현재와 이전 값에 *2 (해당 범위에 * 이나 다른 기호가 포함될 경우도 고려해서 미리 정수로 변경해줌) #은 0으로 변경 후 현재 값에 -1 정수로 변환된 전체 리스트를 합쳐줌 -> 총점 3. 코.. 2022. 9. 25.
[프로그래머스][Lv.1][Python] 3진법 뒤집기 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/68935 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 10진법을 2진법으로 만들때와 비슷하게 3으로 나눈 나머지를 리스트에 추가 역순으로 들어갔기 때문에 문제에서 요구하는 앞뒤 반전은 생략 해당 자리에 맞게 3의 제곱수를 곱해서 누적해줌 3. 코드 def solution(n): answer = 0 tmp = [] # 3^0:1, 3^1:3, 3^2:9, 3^3:27, 3^4:81... while(n!=0): tmp.appe.. 2022. 9. 20.
[프로그래머스][Lv.1][Python] 최대공약수와 최소공배수 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12940 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 최대 공약수 : 두 수 이상의 여러 수의 공약수 중 최대인 수 -> n과 m에 동시에 나눠지는 i 중 가장 큰 값 최소 공배수 : 두 수 이상의 여러 수의 공배수 중 최소인 수 -> n과 m을 곱한 값을 최대 공약수로 나눈 값 (유클리드 호제법) 더 쉬운 방법 : math 패키지 활용 import math math.gcd(a, b) math.lcm(a, b) 3. 코드 .. 2022. 9. 20.
[백준] 14502번 - 연구소 (골드 5) 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 방식 지도 공간 중의 0인 위치를 찾아, 중복 되지 않고 3개의 위치를 선택한다. (순열) 해당 위치에 벽을 세우고 BFS로 바이러스를 확산시킨다. (4 방향) 모든 지도에 수행하면서 안전한 영역(0인 곳)이 가장 많이 남은 개수를 찾는다. 코드 #include #include #include #include #include #include using namespace std; void func_1.. 2022. 4. 21.
[알고리즘] 순열과 조합 순열 (Permutation) 먼저 위키피디아에서 순열의 정의를 찾아봤다. 수학에서의 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이라고 설명한다. 순열은 Permutation 의 앞글자 P로 표현한다. n개의 원소를 가진 집합을 임의의 다른 순서로 섞는 연산의 경우의 수는 n! 과 같고, n개의 원소 중 r개의 원소를 선택하여 순열하는 경우의 수는 P(n, r)과 같다. 아래 이미지는 위키피디아에서 P(n, r) 연산하는 방법을 설명한 부분이다. C++ 코드로 구현해보자. #include #include #include using namespace std; void func(){ vector v = {1, 2, 3}; do{ for(int i = 0; i < v.size(); i++){ .. 2022. 4. 21.
[백준] 1874번 - 스택 수열 (실버 3) 문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 방식 1~n 까지 오름차순으로 정렬된 num_vector, stack_vector, 원하는 수열을 입력 받을 target_vector 를선언한다. target_v의 각 요소들에서 num의 top(back)과 값을 비교한다. 같으면 다음 target으로 이동하고 다르면 하나씩 뽑아서 비교하면서 stack에 .. 2022. 4. 19.
[알고리즘] 다익스트라(Dijkstra) 최단 거리 알고리즘 그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, A* 등이 있고, 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘에는 플로이드 워셜 알고리즘이 있다. 해당 알고리즘들을 응용하여 최단 거리를 가지는 경로를 구하는 방법도 있지만, 이 글에서는 다익스트라 알고리즘을 활용하여 최단 거리만 구해보겠다. 먼저 우선순위 큐를 사용하지 않는 최초의 다익스트라 알고리즘은 아래 과정과 같고 O(V2) 의 시간 복잡도를 갖는다. (2중 for 문 구조) 시작 노드 결정 현재 노드를 기준으로 각 노드의 최소 비용을 계산 방문 하지 않은 노드 중 최소 비용의 노드를 선택 선택된 노드를 기준으로 거리 비용을 .. 2022. 4. 11.
[자료구조] 우선순위 큐 - 작성 중 큐는 FIFO, 우선순위 큐는 우선순위가 높은거 먼저 나옴 구현 1. 리스트를 이용한 구현 (큐로도 가능?) 2. 힙을 이용한 구현 시간 복잡도 1 -> 0(1), 삭제 시는 O(N) // 찾아서 삭제해야됨 2. -> O(log N) / O(log N) -> 삽입 삭제가 시간복잡도 동일하고 데이터의 입출력 과정이 힙정렬과 동일, 이때는 O(N log N) 힙은 완전 이진트리의 일종, 항상 루트 노드 제거 최소 힙은 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선 제거됨 ㄴ 넣었다 빼면 걍 오름차순 최대 힙은 루트 노드가 가장 큰 값이고 값이 가장 큰 데이터가 우선 제거됨, 내림차순 완전이진트리 : 루트부터 왼쪽, 오른쪽으로 순서대로 데이터가 삽입되는 트리 최소힙 구성함수 (min-heapif.. 2022. 4. 11.
[백준] 4963번 - 섬의 개수 (실버 2) 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 접근 방식 BFS로 영역나누기, 8방향 검사 코드 #include #include #include #include using namespace std; int main() { int w = 1, h = 1; queue q; int direc[8][2] = { {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1} }; .. 2022. 4. 4.
[백준] 1920번 - 수 찾기 (실버 4) 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 방식 정렬 후 이진탐색 구현 매개변수로 정렬된 벡터 전달 -> 10% 시간 초과 입출력 속도 개선 -> 10% 시간 초과 정렬된 벡터를 전역 변수로 접근(매개변수로 전달하는 과정에서 시간이 많이 걸릴 수 있다고 함) -> 통과 코드 #include #include #include #include using namespace std; vec.. 2022. 4. 4.
[백준] 1463번 - 1로 만들기 (실버 3) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근 방식 다이나믹 프로그래밍 분류에 있는 문제이므로 점화식을 찾아 DP로 구현 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 위 규칙을 기반으로 점화식을 찾아보자. 가능한 연산과 규칙을 나열해보면 최종적으로 dp[n] = 1 + min(dp[n-1], dp[n/2], dp[n/3]) 이라는 점화식을 찾을 수 있다. 점화식의 의미는 현재 수에 대한 연산 횟수 증가(1) + 가능한 이전 연산 중 최소 값 ( min(...) ) 이다. 코.. 2022. 4. 4.
[백준] 10026번 - 적록색약 (골드 5) 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근 방식 기본 Map과 색약 Map을 만들어 BFS로 구역을 나눠줌 틀렸습니다. 코드와 정답 코드 차이 // 틀린 코드 if (map_visit[i][j] == 0) { q.push({i, j}); visit_value++; } // 정답 코드 if (map_visit[i][j] == 0) { q.push({i, j}); map_visit[i][j] = ++visit_value; }.. 2022. 4. 4.
[백준] 10773번 - 제로 (실버 4) 1. 문제 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 2. 접근 방식 Stack 활용 3. 코드 #include #include using namespace std; int main() { int test_case, tmp, sum=0; cin >> test_case; stack stack_zero; for (int i = 0; i > tmp; if (tmp==.. 2022. 3. 15.
[백준] 15829번 - Hashing (브론즈 2) 1. 문제 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 2. 접근 방식 1차 : 문제에서 알려준 공식대로 구현 -> 50점, 작은 문자열에서는 잘 동작하지만 큰 문자열에서는 시간초과 2차 : 합동식 활용 A * B mod C -> (A mod C) * (B mod C) -> 통과 3. 코드 1차 코드 #include #include typedef unsigned long long ll; using namespace std; int main.. 2022. 3. 15.

티스토리툴바