Algorithm

1. 문제 설명 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 주어진 입력에 대해 시작점 (0,0)부터 bfs를 통해 탐색하자. visited 배열에 이전 이동 거리에서 1을 더해주며 지나야 하는 최소 칸 수를 구해준다. 나의 코드 // // Created by 태윤맥북 on 4/17/24. // #include #include #include using namespace std; int dx[4] = {1, 0, -1, 0}; i..

1. 문제 설명 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 문제 해결의 흐름 (bfs 이용) 석유 지도 (land)를 탐색하며 석유를 찾는다. 석유를 찾았다면 bfs를 통해 석유 덩어리의 크기를 파악하고 해당 석유 덩어리를 캘 수 있는 모든 column값을 집합(set)에 저장한다. (column값들의 중복을 제거하기 위해 집합에 저장함!) bfs 탐색이 끝났다면 column 위치 중 어느 위치에서 시추하는 것이..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 2. 풀이 과정 문제 해결의 흐름 맥주가 20개 있는 상태(full)에서는 거리가 1000미터 이하인 곳까지 도착할 수 있다. 편의점이 왜 n개가 주어졌을까...?? 사실 페스티벌에서 가장 가까운 편의점을 bfs로 찾아 그 편의점과 페스티벌 사이의 거리가 1000 미터 이하인지 확인하는 문제 아닐까? 나의 코드 // // Created by 태윤맥북 on 4/15/2..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net bfs 개념을 배우고 난 뒤 첫 문제였습니다 ㅎ. 입문용으로 최고의 문제인 듯합니다. 2. 풀이 과정 문제 해결의 흐름 강호의 위치 S층에서 꼭대기 층인 F층 사이를 오르락(U) 내리락(D)하기. 이동하며 방문한 층은 방문처리한다. 이때, 이동한 층이 스타트링크가 위치한 곳(G)이라면 결과값을 제출하자. 나의 코드 #include #include using namespace std; ..

1. 문제 설명 링크 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 전형적인 bfs 문제입니다. 3차원 배열이 싫다하시는 분들은 7576의 토마토 문제를 추천 드립니다. 두 문제 모두 같은 방법으로 풀 수 있습니다. 2. 풀이 과정 문제 해결의 흐름 입력 받은 배열에 관해 토마토가 익은 상태(1)라면 큐에 저장하자. 큐에 저장된 값 주위(총 6방향)를 탐색하며 안 익은 토마토(0)가 있다면 익은 토마토로 바꾸고 방문..

빠르고 느림은 상대적인 표현이다. 효율성을 중요시하는 알고리즘 세계에서 빠르고 느림을 표현하는 척도는 무엇일까? 1. 빅 오 표기법이란? Big - O Nation, 즉 '빅 오 표기법'은 알고리즘의 시간 복잡도를 나타내는 표기법이다. 이 표기법을 통해 알고리즘의 빠르고 느림을 표현할 수 있고 코드가 얼마나 효율적인지 평가할 수 있다. 참고로 시간복잡도의 3가지 표현은 다음과 같은데, Big-O(빅-오) 표기법을 사용하는 이유는 최선의 경우를 고려했어도 최악의 경우가 발생할 수 있기에 최악의 시간을 기본적으로 대비하는 것이 바람직하기 때문이다. 이를 전문적으로 표현하면 빅 오표기법은 알고리즘의 효율성을 상한선을 기준으로 표기한다고 한다. (x축이 입력크기, y축이 실행시간일 때, 그래프가 위로 향할수록,..

https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 문제 설명 풀이 과정 나의 풀이 ① 문제 바라보기 최근에 dfs & bfs 문제만 유형별로 골라서 풀고 있는중이라 문제 유형을 알고 푸니 쉽게 접근이 가능했다. 주어진 A, P값에 따라 반복순열이 다르게 나온다. 예제 1의 경우 57 -> 74 -> 65 -> 61 -> ... -> 37 , 58 -> 89 -> ... -> 37 -> 58 로 순열이 나타난다. n번쨰 값이 n-1번째 값으로부터 파생된다는 점에서 일종의 방향성을 발견할 수 있었다! ② 아이디어 열기 문제에서 구하고자 하는 값은 무한으로 반복..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.www.acmicpc.net 문제 설명풀이 과정나의 풀이① 문제 바라보기  '어 뭐야? 그냥 버블정렬을 이용하여 오름차순으로 정렬한 뒤 0번째 인덱스 요소와 마지막 인덱스 요소를 뽑으면 끝인데?' 라고 생각했지만 시간초과가 나버렸다...#include int main(void) { int N,k; std::cin >> N; int arr[N]; for (int i = 0;..