programming/알고리즘 풀이 (40) 썸네일형 리스트형 [백준 알고리즘] 14938번 - 서강그라운드 1. 문제 및 예시 실행결과 다익스트라 문제라는 것을 처음부터 알게 되었다. 문제 잘 읽고 푸는 습관을 들여야하는데... 부등호하나 잘못써서 두번의 틀렸습니다가 찍힐뻔 했다... 다익스트라가 손에 조금 익어서 해당 알고리즘을 사용하고 있는데 플로이드 워셜로 나중에 공부해서 적재적소에 사용할 수 있으면 좋겠다. 출처: https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2. 풀이 과정 문제 쪼개기 1. 입력 2. 모든 노드를 시작점으로 설정 - cache.. [백준 알고리즘] 12851번 - 숨바꼭질 2 (BFS에서의 같은 depth 처리과정) 1. 문제 및 예시 실행결과 BFS문제인 것은 파악했는데 visited 배열을 처리하는 과정에서 조금 힘들었다. 논리적으로 길을 먼저 세워 풀면 되는 문제를 너무 급하게 덥벼든 것 같다. visited를 배열에 삽입하기 전에 처리하는 것이 좋을 수 있지만(Queue가 커지는 것을 방지) 이 문제 처럼 같은 depth의 중복을 처리해야하는 문제는 queue에서 노드를 꺼내서 visited처리를 하는게 좋을 수 있다는 것을 깨달았다. 다음은 예외 케이스이다. 1 3 출처: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000).. [백준 알고리즘] 17144번 - 미세먼지 안녕! 1. 문제 및 예시 실행결과 구현과 시뮬레이션 문제이다. 어우 힘들어... 구현은 아무래도 높은 집중력과 예외처리를 위한 설계가 중요시 되는 것 같다. 한번 오류나면 멘탈이 나가서 문제 난이도가 생각보다 높게 느껴진다. 재능있는 사람들은 처음부터 오류없는 코드를 잘 작성하겠지만, 나는 그런 것 같지는 않으니 최대한 고심해서 코드를 짠다. 그래서 이리 힘든 것인지... 출처: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 과정 알고.. [프로그래머스] 138476번 - 귤고르기 1. 문제 및 예제 담은 귤의 종류가 적다는건 갯수가 많은 종류를 순서대로 나열해 순서대로 박스에 넣어주면 된다. 귤의 종류와 그 갯수를 저장할 자료구조 하나 그리고 그것을 갯수로 정렬할 알고리즘을 생각하면 별로 어렵지 않은 문제이다. C++의 sort()를 사용했으니 시간복잡도는 O(NlogN)이다. https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 처음 내가 이 코드를 작성하고 제출을 했을 때 분명 더 좋은 풀이법이 있을거라 .. [프로그래머스] 86491번 - 최소직사각형 (완전탐색) 1. 문제 및 예제 완전탐색이라고 그냥 너무 무식하게 다 비교하면 안된다는걸 알게된 문제. 처음에는 모든 높이와 넓이를 매칭시키고(여기서 나온 시간복잡도는 O(N*N) 이걸 모든 명함과 비교하는 방법.(결과적으로 총 시간 복잡도는 O(N*N*N)... 내가 미친거지 아주) 생각해보면 참 답이 없다 싶었다... 아직도 이런 문제로 해매다니... 자괴감 들었지만 그래도 다른 풀이들 참고하면서 풀었다. 개인적인 의견으로 수학 못 하는 나에게 이 문제는 레벨1 문제는 아닌듯... 출처: https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고,.. [백준 알고리즘] 1744번 - 수 묶기 (그리디 알고리즘) 1. 문제 및 예시 실행결과 그리디와 정렬을 사용하는 문제이다. 문제의 핵심만을 파악하면 구현은 어렵지 않은 문제이지만, 핵심을 파악하고 알고리즘을 정의하는 과정이 조금 어려웠다. 출처: https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수열에서 두 수를 묶어 최대한 큰 수를 만드는 과정은 그렇게 어렵지 않다. 정렬한 후 뒤에서부터 두개의 수를 묶어 곱하면 된다. 가장 큰 수 두개를 곱하는 것이 가장 큰 수를 만드는 방법이기 때문이다. 이 과정.. [백준 알고리즘] 1012번 - 유기농 배추 (DFS 알고리즘) 1. 문제 및 예시 실행결과 이 글의 소제목이 DFS 알고리즘이지만, 나는 DFS알고리즘을 모르는 상태이다...... 그냥 내가 생각한 방식대로 풀었더니 그것이 DFS 알고리즘이었던 것이다. 다른점이 있다면 나는 자료구조를 queue를 사용하였지만 DFS 알고리즘은 stack을 사용한다고 한다. 이 글은 DFS알고리즘의 설명보다는 1012번을 푸는 방법에 대한 글이라고 생각해줬으면 좋겠다. 출처: www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 중요한 점은 이놈의 지렁이.. [백준 알고리즘] 1929번 - 소수 구하기 (시간 초과, 소수 알고리즘) 1. 문제, 실행결과 예시 백준 알고리즘 카테고리에 글을 쓰는게 정말 오랜만인 것처럼 느껴진다. 아마 실제로도 오랜만일 것이다 ㅎㅎ. 이 문제에 대한 풀이를 올리는 이유는 시간 초과라는 새로운 문제를 만났기 때문이다. 실제로 소수를 구하는 문제는 정말 많이 풀어봤지만, 이번 문제의 최대 입력값은 100000으로 기존에 사용하던 방법( 1 ~ N 까지의 모든 수를 비교하는 방법 )을 사용하면 시간초과가 날 수 밖에 없었다.( 심지어 숫자 하나당 줄바꿈을 해야하는 문제이다. ) 때문에 소수를 찾는 다른 방법을 사용해야 했다. 방법은 아래에서 자세히 설명할 것이다. 다음은 문제와 실행결과 예시 이다. 출처: https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의.. 이전 1 2 3 4 5 다음
