옌의 로그

문제 [백준] 크로스워드 퍼즐 쳐다보기 (Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #2 3번) 사용 알고리즘 - 구현 해결방법 행(row)방향, 열(column)방향으로 전체 탐색하면서 나오는 모든 단어들을 비교해 답을 구한다 알파벳을 만나는 경우, res 변수에 더해준다 벽을 만나는 경우, 이전까지 만들어진 단어(res)를 temp에 저장한 뒤, 다시 알파벳이 나오면 그 지점을 시작으로 다시 단어를 만든다 res가 2글자 이상인 경우 temp도 2글자 이상인 경우 temp = min(res, temp) >> temp를 최소값으로 갱신시킨다 temp가 1글자 이하인 경우 temp = res >> temp에 ..

문제 [백준] 후위 표기식2 사용 알고리즘(자료구조) - 스택(Stack) 해결방법 후위 표기식이란?? 예를 들어, 중위 표기식 3+4를 후위 표기식으로 표현하면 34+ 가 된다 => 그렇다면? 입력 받은 식을 앞에서부터 보면서, 피연산자인 경우 : 스택에 저장 연산자가 나온 경우 : 스택에서 2개의 피연산자를 꺼내서 연산한 뒤, 결과값을 다시 스택에 저장 예제 1번 ) 더보기 5 ABC*+DE/- 1 2 3 4 5 처리 과정 1 push st : [1] 2 push st : [1, 2] 3 push st : [1, 2, 3] pop 한 후, * 연산 st : [1, 6] pop 한 후, + 연산 st : [7] 4 push st : [7, 4] 5 push st : [7, 4, 5] pop 한 후 / ..

문제 [백준] 색종이 만들기 (Olympiad > 한국정보올림피아드 > KOI 2001 > 중등부) 사용 알고리즘 - 분할 정복 - 재귀 해결방법 종이를 한 변의 길이가 절반이 되게끔 자른다고 생각하고 문제를 해결한다 종이를 자르는 경우는 기준위치의 색깔과 현재 위치의 색깔이 다를 때 종이를 자른다 한 변의 길이가 절반이 되게 자르는 경우, 종이 4장이 생성되는데, 이 때 각 종이의 기준위치는 다음과 같다 길이 : N 일때, 기준위치 (col, row) // (0, 0)이다 종이1 > 길이 : N/2, 기준위치 (col, row) 종이2 > 길이 : N/2, 기준위치 (col, row+N/2) 종이3 > 길이 : N/2, 기준위치 (col+N/2, row) 종이4 > 길이 : N/2, 기준위치 (col+..

문제 [백준] 마라톤 틱택토 (Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #6) 사용 알고리즘 - 브루트 포스 (Brute Force) 해결방법 입력 받은 보드에서 행, 열 또는 대각선 방향에서 3연속하는 이니셜이 있는 경우 승리자로 취급한다 전체 좌표를 돌면서 대각선 좌측 아래 방향, 아래 방향, 대각선 우측 아래 방향, 우측 방향 이렇게 총 4가지 방향을 탐색한다 최소 3개만 연속하면 되므로, 좌표마다 같은 방향으로 최대 2칸 까지만 탐색한다 범위를 벗어나는 경우 탐색하지 않는다 같은 이니셜이 3개 이상 연속한 경우 탐색을 완전 종료한다 반례 모음집 더보기 정답 : A 포인트 : 대각선 방향 탐색시 가능한..

문제 [백준] 주유소 (Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번) 사용 알고리즘 - 그리디 (Greedy) 해결방법 마을이 일직선 상에 있다는 것이 포인트 한 마을에서 다음 마을로 이동하기 전에 가장 저렴한 주유소를 저장해 두고 해당 주유소에서 주유한 뒤 이동한다 매 번 마을에 도착할 때마다 최소 주유비에 다음 이동 거리를 곱해서 경비를 구해야한다 예제 1의 경우 각 마을의 주유비가 [5, 2, 4, 1] 이다. 이 때 이동할 때마다 그리디 하게 주유비를 선택한다고 하면 다음과 같다. i 현재 주유비 최소 주유비 이동 거리 경비 0 5 5 2 10 1 2 2 3 6 2 4 2 1 2 소스코드 사용언어 : C++ #include #include using namespace..

문제 [백준] 풍선 공장 사용 알고리즘 - 이분 탐색 해결방법 스텝별로 실시간 누적 작업시간을 담는 우선순위 큐를 활용한다 우선순위 큐에 pair를 삽입한다. 이렇게 하면 가장 작업이 빨리 끝나는 스태프가 항상 top 에 위치하기 때문에, 해당 스태프를 Pop 한 뒤, 작업을 할당해서 다시 push 해주면 된다. 예제 1을 살펴보면, 가장 빠르게 풍선 1개를 완성한 (3, 3) 스태프를 Pop 하고, 해당 스태프에게 작업을 한 번더 할당한 뒤 (6, 3) 을 push 해준다. 그 다음으로 빠르게 풍선 1개를 완성한 (5, 5) 스태프를 pop하고, 일을 할당한 뒤 (10, 5)를 push 한다. 그 다음으로 빠르게 풍선 1개를 완성한 (6, 3) 스태프를 pop하고, 일을 할당한 뒤 (9, 3)를 pu..

문제 [백준] 사탕 게임 (Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 ) 사용 알고리즘 - 브루트포스 (Brute Force) 해결방법 이 문제의 핵심은, 바꾼 사탕이 위치한 행, 열 만 탐색하는게 아닌, 전체 보드판을 다 탐색해야 한다는 것 ! 예제 2번을 살펴보면, C(1,0), Y(1,1) 두 사탕을 swap 한 후 (0,0) 부터 행방향 탐색을 했을 때, [P, P, P, P] 로 연속한 N개의 사탕이 확인되므로 탐색이 종료된다. 보드판의 (0,0)부터 마지막 사탕까지 쭉 반복문을 돌면서, 인접한 사탕 (가로 방향, 세로 방향) 을..

문제 [백준] IF문 좀 대신 써줘 사용 알고리즘 - 이분 탐색 (Binary Search) 해결방법 입력받은 전투력 배열(level_num)을 이분탐색으로 탐색한다. 예제 2에서 살펴보면 다음과 같은 흐름으로 계산된다 더보기 99가 입력되었을 때 lv : 99 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) right => 0 (mid - 1) left : 0, right : 0 mid : 0 level_num[mid] : 100 (B) right => -1 (mid - 1) level_name[mid] : B . . . lv : 101 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) left => 2 (mi..

문제 [백준] 크림 파스타 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 dp[A배열 원소 개수] = (최대값 - 최소값)의 최대값 A배열에 값이 들어올 때 마다 A의 원소중 최소값과 비교해 최소값을 체크해준다. 들어온 값 - 최소값 과 dp[i-1]을 비교해 더 큰 값을 dp[i]에 기록해준다. A 배열에 원소가 들어올 때마다의 상황을 표로 나타낸 것 50이 들어왔을 때 원소 중 최소값 : 50 input 값과 최솟값의 차 : 0 50이 들어오기 전까지 가장 (최대값-최소값)의 최대값 : 0 dp[1] = 0 100이 들어왔을 때 원소 중 최소값 : 50 input 값과 최소값의 차 : 50 (100-50) 100이 들어오기 전까지 가장 (최대값-최소값)의 최대값 (= d..

문제 [백준] 설탕 배달 (Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번) 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 동전으로 금액을 만드는 문제와 같다고 보면 된다. > 3과 5를 가지고 N키로 만들기 $dp[N] = 사용한 최소 동전(설탕 봉지) 수 $dp 배열을 0으로 초기화 해준 뒤 반복문을 돌면서 채워주면 되는데, 이 때 3, 5 번째는 각 각 1개의 봉지 만으로 만들 수 있기 때문에 1로 갱신, 4의 경우 만들 수 없는 숫자기 때문에 0으로 갱신해준다. $dp[$i-3], $dp[$i-5] 의 값이 모두 있는 경우 (0보다 큰 경우) 최소 값에 1을 더해주면..