Heecheol's blog

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 효율적으로 계산하는 방법이 있는지 고민을 했었다. 근데 emoticons의 길이가 최대 7이라는 점에서 완전탐색을 이용해도 되겠다는 생각을 했다. 할인율은 총 네 가지 경우만 존재하므로 최대 유저가 100명이어도 해볼만하다고 생각했다. 그래서 재귀를 이용해 우선 모든 할인율 케이스를 미리 구해주었다. 그리고 매 경우별로 직접 계산해서 결과를 출력하였다. import Foundation..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 풀었을 때는 반복문의 중첩으로 배열을 전부 탐색해서 해결했다. 그래서 세 개의 케이스에서 시간초과가 났따. 10^5이므로 최악의 경우 충분히 시간초과가 나올 수 있는 크기였다. 그래서 한 번의 반복문을 통해 해결하려고 해보았따. 해결하기까지는 오래걸렸지만 막상 해결하고 나니 충분히 더 빨리 풀 수 있는 문제였다. 우선, 가장 마지막부터 처리하는 것이 가장 빠른 방법인 것을 알아..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 처음엔 문제도 제대로 이해못했고, 제대로 이해하고 나서도 푸는데 오래걸렸다. 그래프가 두 집합으로 나뉠때 각 집합의 원소들이 연결되어있지 않아야한다. 나는 BFS를 이용했다. visited의 첫 값을 0으로 두고, 1부터 차례대로 반복문을 돌렸다. 그래서 visited값이 0인 경우엔 값을 1로 만들고, 해당 점과 연결된 모든 점을 확인했다. 해당 점과 연결이 되어있다는건 같은 집합에 ..

문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 이 문제에서 중요한 것은 외부 공기와 접촉해야한다는 것이다. 처음에 아무생각없이 닿는 공기가 두 개 이상이면 바로 없애도록 해서 틀렸었다. 가장자리에는 치즈를 두지 않으므로 이를 이용해서 바깥 공기를 구해주면된다. 처음에 풀었던 방식은 우선 바깥공기를 전부 배열에 넣고, 다시 처음부터 BFS를 돌려 치즈를 구한 뒤에 공기랑 닿는 면이 바깥공기 배열에 들어가 있는지 확인해서 ..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 어려웠다... 다른 BFS문제들과 대부분 비슷했지만, 먹이를 먹는 기준때문에 오래걸렸다. 처음에는 단순히 dx, dy의 순서만 바꿔서 해결하려고했는데, 이렇게 해서는 풀 수 없다는 것을 알게되었고 정렬을 해야 해결이 된다는 것을 알게되었다. 기본적인 BFS를 사용하는 것은 동일하다. 근데 이제 더 이상 갈 곳이 없다면 while문은 종료될 것이다. 이때, 탐색하는 동안 먹을 수 ..