본문 바로가기

Algorithm

 (175)
[SQL] 즐겨찾기가 가장 많은 식당 정보 출력하기 / 왜 MAX()가 안될까? https://school.programmers.co.kr/learn/courses/30/lessons/131123 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그냥 보기에는 간단한 문제여서 group by 를 사용하여 max()로 출력해주었지만 답이 틀리게 나온다. SELECT FOOD_TYPE, REST_ID, REST_NAME, MAX(FAVORITES) AS FAVORITES FROM REST_INFO GROUP BY FOOD_TYPE ORDER BY FOOD_TYPE DESC 왜 MAX()는 안될까?? 그 해답은 아래의 글에 작성되어있다. ht..
[BOJ] 17406. 배열돌리기4 Python, Java https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 1. 해결방법 생각보다 힘들었던 문제이다. 배열을 돌려야 하는데 이 과정이 꽤나 머리를 지끈거리게 만든 것 같다. 여기서 사용했던 핵심 포인트는 조합을 사용해서 회전 연산의 순서를 결정하고, 그 것을 바탕으로 해당 위치에 대한 배열을 돌려야 한다. 1. 먼저 조합을 구해야 한다. ---> 주어진 예시는 (3, 4, 2), (4, 2, 1)일 때, 첫 번째 회전 방법은..
[BOJ] 17141. 연구소2 Python https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 1. 해결방법 어우 완전탐색 문제이다. 완전탐색을 하드코딩으로 푸니까 중간에 로직이 꼬여서 고생을 좀 했다. 이 문제도 연구소1처럼 시간초과를 생각하면서 코드를 짜야한다. 본인은 바이러스가 놓일 수 있는 위치를 미리 리스트에 담아두어서 백트래킹으로 놓일 수 있는 경우의 수를 모두 탐색하였다. (Combinations을 사용해도 됨) 1. 미리 바이러스가 놓일 위치를 리스트에 담는다. 2. dfs (백트래킹..
[BOJ] 14502. 연구소 Python https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 해결방법 그래프 완전 탐색문제이다. 1. 먼저 벽을 3개 쳐야하므로, 백트래킹을 이용하여 빈 공간(0)에 벽을 3개 친다. 2. 벽을 쳤으면, BFS를 통해서 바이러스 부분이 퍼져나가는 로직을 구현한다. 3. BFS를 다 돌았아면, 연구소의 넓이를 구한다. 새롭게 배운 부분은, 기존에 사용하던 백트래킹 로직에서 for문을 많이 사용하게 되어서 시간초과가 나온다. 해결방법은 '//'와 '%'의 연산을 이용..
[BOJ] 2943. 탑 Python, Java https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 1. 해결방법 탐색으로 모든 경우를 확인하면 시간초과가 난다. stack으로 해결한다는 생각이 쉽게 떠오르는 것도 아니고 탐색이 안됐을 땐, 꽤나 멘탈이 나갔다. 다른 분의 코드를 보고 이해를 했다. 이 문제는 오른쪽에서 읽으면 결국 탐색이 되어버리기 때문에 왼쪽에서 읽는 방법을 생각해야 한다. 이것이 stack으로 생각하기 위한 지름길 아이디어이다. 1. for문으로 tops를 돌면서 하나하나..
[SWEA] 암호문1 Java https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14w-rKAHACFAYD& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 해결방법 ArrayList를 이용한 간단한 문제이다. 다만 아직 자바에 익숙하지 않아서, 입력문 부분에서 애를 먹었지만 입력을 받기만 한다면 쉽게 해결된다. ArrayList의 add()메서드를 이용하면 insert 즉, 해당 인덱스 위치에 값을 집어넣을 수 있다. 이를 이용하면 해결이 가능하다. 2. 정답코드 import java.io.BufferedReader; import java.io..
[BOJ] 2304. 창고 다각형 Python https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. 해결방법 솔직히 개인적으로 접근 하는 데 있어서 너무 어려웠다... 엄청 많은 시간이 투자해도 해결하지 못해서 다른 분들의 힌트를 보고 해결했다,,,,,, 위 문제는 stack으로도 해결해도 되지만, 조건이 너무 까다로워서 stack으로 해결하지 못했다. 핵심포인트는 가장 높이가 큰 인덱스의 정보를 찾고, 왼쪽과 오른쪽 끝에서 부터 탐색하면서 넓이를 구하는 것이다 왼쪽부터 보..
[BOJ] 12891. DNA 비밀번호 Python, Java https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 해결방법 이 문제는 초기 값을 매우 크게 주고 있으므로, 보자마자 for문으로 모두 탐색을 시도한다는 것은 시간초과로 이어질 수 있다. 핵심은 O(N) 안으로 시간복잡도를 해결하는 것이며, O(N) 안으로 해결하기 위해서는 투 포인터를 이용하여 윈도우 슬라이딩 기법으로 해결하면 된다. ### 윈도우 슬라이딩 ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4..

티스토리툴바