Algorithm7 0과 1 상태 변환(값을 서로 바꾸거나 제자리에서 바꾸거나) 여기서 기억해야 할 테크닉은 found 변수를 이용해서 for else를 구현한 것. /* 상태변환 1. 임의로 0과 1 두 개를 선택해서 서로 위치를 교환. 2. 임의로 0또는 1 한개를 선택해 뒤집는다. 예시. 11000111. 목표 11100110 3번째 0과 8번째 1을 서로 바꾸면 1번만에 목표 달성. 최소횟수 구하기. 11000111 -> 11111110. 1. 3번째와 8번째 교환. +1 2. 4번째 1로 바꿈 +1 3. 5번째 1로 바꿈 +1 4. 정답 3. 풀이. 목표 문자열을 한 배열에 저장해놓고. 시작배열의 요소 1개씩 비교하면서 다르다면 반복문을 통해 다른 것과 교환한다. 끝났으면 또 다음 요소를 1개씩 비교하면서 나간다. 만약 또 다르다면 */ // console.log() fun.. 2021. 7. 24. 백준 1463번 : 1로 만들기 단순 그리디 방식으로 푸는 것이 아니라 10->9->3->1 처럼 1을 빼고나서 3을 나눴을 때 더 빠르게 1로 만들 수 있기 때문에 동적계획법으로 접근하면서 메모이제이션 기법을 사용해야 한다. n = int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1]+1 if i%3 == 0: dp[i] = min(dp[i], dp[i//3]+1) if i%2 == 0: dp[i] = min(dp[i], dp[i//2]+1) print(dp[n]) 1. 왜 dp 리스트를 n+1까지 0으로 만드는가? 예를 들어서 n이 10이라고 했을 때 dp[10]까지 최소값을 저장하면서 연산할 것이기 때문에 리스트에 +1을 더해야 한다. 2.. 2021. 7. 13. 백준 - 1260 DFS와 BFS (파이썬) 첫 시도 : 上 문제를 파악하고 2차원 리스트형태로 만드는 것부터 막혔었다. 해답을 보고 했지만 이해하기가 어려웠다. 두번째 시도 : 中 해답을 보면 이제 어떤 식으로 짜여졌는지 이해가 간다. DFS, BFS를 이용하는 문제 핵심 1. 입력값으로 노드의 간선을 입력하는데 2차원 배열형태로 갈 수 있는 곳을 1로 표시해서 만든다. 2. 방문한 노드는 다시 방문하지 않도록 visited를 선언한다. 3. 1번 노드부터 시작하기 때문에 리스트들을 만들 때 제일앞은 건너뛴다고 가정하고 노드의 개수 +1 로 리스트를 만든다. 연습을 위해 DFS와 BFS를 나눠서 코드를 써보자. 먼저 DFS. n , m, s = map(int, input().split()) visited = [False] * (n+1) graph.. 2021. 6. 30. 이코테-음료수 얼려먹기 (파이썬) 첫 시도 : 上 이해도 하지 못했다. 그냥 읽었을 뿐 두번째 시도 : 中 일부가 보였다. 약간 부분적으로 이해는 했으나 전체적으로 이해를 못했다. 약간 이해해도 곧바로 까먹었다. 세번째 시도 : 下 전체가 보였다. 전체적인 흐름을 읽을 수 있다. 이런 유형. 이제 코드도 짤 수 있다. DFS를 이용하는 문제 예를 들어서 3x3 틀이 있다고 가정했을 때 0과 1로 채울 수 있다. 1은 틀. 즉, 막힌 부분이고 0은 다 연결되어 있는 부분이다. 얼음을 얼렸을 때 몇개의 얼음을 만들 수 있는지 그런 문제다. 좀 더 직관적으로 보면 아래와 같은 예시에서는 총 3개의 얼음을 만들 수 있다. --------- 0 0 1 0 1 0 1 0 1 --------- 원리 2차원 리스트를 만들고 (x, y)가 0이면 1로 .. 2021. 6. 29. 앞으로의 계획 정리 github에 알고리즘 공부를 매일하면서 잔디를 심자. -> 나중에 성실함을 보여주기 위함 이것이 코딩테스트다책으로 개념을 공부하고 나면 알고리즘 사이트(코드 시그널, 코드포스, 백준+solved, 정올, 프로그래머스)에서 풀고 푼 것에 대한 설명을 기술하면서 정리해두자 -> 이 문제를 풀기 위해서 어떻게 접근했는지 보는 입장에서 편하게 정리한다고 생각 가장 중요한 것은 무엇보다 성실함. 성실함을 잊지말자. 2021. 6. 27. 모든 알고리즘 계산은 velog에서 한다. 코드를 쓸 때 velog가 편해보여서 앞으로는 일단 velog만 관리할듯하다. https://velog.io/@joker77z joker77z (박태준) - velog 이코테 공부 순서 4주 기준. 하루 3시간 투자.가장 중요한 것 : 틈날때마다 보기.1단계 : 파이썬 문법 공부2단계 : 코드업 쉬운문제 200문제 가량.3단계 : 알고리즘 이론, 기출문제 학습4단계 : 백준 velog.io 약 1달동안 사용해 본 결과 심플해서 뭔가 다른 곳에 정신을 쏟지 않고 온리 정리하는데에만 집중해서 사요하기에 나쁘지 않았다. 근데 사용하다보니 디자인적으로 자유롭지 못한 부분이라던지 코드를 정리하고나서 이쁘게 보이지 않아서 다시 티스토리에서 당분간 정리해봐야겠다. 2021. 5. 17. 이전 1 2 다음
