seungineer

2141번: 우체국 boj.ma문제의 조건첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.N이 10^5으로 O(N^2) 이하의 알고리즘만 적용 가능함을 알 수 있다.만약 O(N^2) 알고리즘이 적용 가능하다면 모든 N에 대해 우체국을 세워서 해당 우체국에서 마을까지의 거리를 구하면 쉽게 '거리의 합이 최소가 되는 위치'를 찾을 수 있다. 문제 접근임의의 우체국 위치를 가정하고 식을 세워보면 아래와 같은 형태임을 알 수 있다. 마을은 (1, 0), (2, 0), (3, 0)에 위..

알고리즘 문제를 풀이한 후에 구글링 해보며 효과적인 풀이었는지 항상 확인한다."12904 파이썬" 키워드로 구글링 하면 대부분 reverse(), array slice를 사용한 풀이 밖에 없어서 풀이의 다양성을 추가하고자 투 포인터 풀이에 대해 작성한다.Intuition1. S를 T로 변환 가능? ➡️ T를 S로 변환 가능?문제에서는 S를 T로 만들기 위해 '문자열의 뒤에 A를 추가'하거나 '문자열을 뒤집고 뒤에 B를 추가'할 수 있다고 한다. 이 두 방법을 이용해 S를 T로 만들 수 있는지 확인하면 된다.문자열의 뒤에 A 혹은 B가 있을 때, A가 있다면 문자열에 곧바로 추가된 것이고 B가 있다면 뒤집혀서 추가되었다고 생각할 수 있다. 즉, 만들어진 결과를 보고 이전 상태를 생각할 수 있으므로 T를 S..

Week 1 ~ 3, '컴퓨팅 사고로의 전환'이 마무리 되었다. 발제명과 같이 기존 사고 방식을 컴퓨팅과 동일한 사고 방식으로 전환하기 위해 알고리즘 문제를 활용하였다. 알고리즘 문제를 컴퓨터가 해결할 수 있도록 파이썬으로 코드를 짠다. 이렇게 코드를 짜며 내가 사고하는 방식을 컴퓨터가 처리할 수 있는 방식대로 동기화하는 주차였다. 3주간 알고리즘 문제들을 컴퓨터에게 해결시켜(?) 본 결과 어느정도 사고 방식이 동기화가 되는 것 같다(아주 조금). 다만, 아직도 time, space complexity 를 줄일 수 있는 방식을 떠올리지 못 하고 있다. 조금 더 공부하고자 하는 부분이다. 또한 백준에 아직 접근해보지 못 한 문제들이 많이 남아 있다. 이러한 문제들을 경험해보면서 더 능숙하게 컴퓨터에게 일을..

재귀에 대해서 공부하면서 '절차지향적 사고'가 아닌 '귀납적 사고'로 접근해야 한다는 얘길 들었다. 그 당시에 어렴풋이 이해했던 부분이 동적프로그래밍을 공부하면서 좀 더 선명히 이해가 되는 것 같아 기록해두고자 한다. 백준 9084 이 문제는 동전의 type이 주어질 때 주어진 금액을 만드는 모든 방법의 수를 출력하는 것이다. 동전의 최대, 최소 개수가 아닌 경우의 수를 모두 합한 값을 출력해야 한다. 주어진 금액에서 시작하여 모든 경우를 절차대로 타고 들어가면 복잡하다. 또한 '중복 부분 문제'가 발생한다. 그러므로 DP를 활용해본다. 1. 테이블 정의하기 dp[i] 는 'i를 만들기 위해 필요한 모든 방법의 수로 정의한다. 이렇게 정의해본 이유는 간단히 dp[주어진 금액] 하면 정답을 찾을 수 있기 ..

백준 1931 문제를 풀다가 85%에서 '틀렸습니다'가 나왔고, 틀리게 만든 케이스에 대해서 고민을 하였다. 몇 가지 반례를 찾을 수 있었다. 이를 해결한 코드를 제출하여 '맞았습니다'가 나왔다. 제출 이후 문득 생각난 케이스가 있어 '맞았습니다'가 나온 코드에 넣어서 테스트해 보았다. 예상 결과와 다른 값을 출력했다. 백준에서 검증하지 않은 케이스인 줄 알았지만, 글을 쓰면서 내가 생각을 잘못했다는 것을 깨달았다... 💩 그래도 잠깐이나마 백준 사이트의 '데이터를 추가한 사람' 리스트에 이름을 올릴 수 있나 행복회로를 돌렸기에 기록해두고자 한다. 백준 1931 문제 요약 입력되는 N개의 회의 시작, 끝 시각을 바탕으로 가장 많은 회의를 진행할 수 있는 경우의 수를 출력하는 것이다. 물론 회의실이 1개이..