BOJ

문제 백준 1158번 요세푸스 문제 풀이 덱을 이용해서 푸는 간단한 자료구조 문제였다. 출력 형식에만 유의하면 된다. 부스트캠프 준비 끝나고 정처기 실기 본 다음에 바로 오픽 준비하고 있는데 은근히 바쁘다. 다시 열심히 문제도 풀고 개발 공부도 해야겠다. 참고로

연속된 알파벳이 없도록 압축한 뒤 각 문자를 탐색했다.

다이나믹 프로그래밍 기본 문제들부터 계속 연습해서 풀이 속도 높여야함

에라토스테네스의 체 -> 특정 범위 내의 모든 소수를 찾는 경우 가장 효율적. 2~제곱근까지 약수를 통한 판별 -> 특정 숫자 N에 대한 소수 판별시 유용. 그리고 투포인터 문제에서 인덱스에러를 주의하자.

백준 1700번 멀티탭 스케줄링문제를 보자마자 페이징 기법이 생각났다.앞으로 꽂을 플러그를 미리 알 수 있기 때문에 뽑아야할 콘센트의 결정이 쉬워진다.꽂혀있음꽂혀있지 않음2-1. 멀티탭에 빈 공간 있음2-2. 멀티탭이 꽉 참 -> 정렬에 의해 마지막 원소 변경, 뽑은

list, tuple -> 평균 O(n) / set, dictionary -> 평균 O(1), 최악 O(n)

백준 1806번 부분합투포인터라는 힌트를 본 덕에 쉽게 풀 수 있었다..연속된 부분 수열의 왼쪽과 오른쪽을 가리키는 l, r 변수를 사용하여 시간복잡도를 O(n)으로 줄일 수 있었다.어떤 케이스에서 오답인지 모르겠어서 검색해서 몇 개 대입해본 후 고쳤는데,테스트케이스

문제 백준 1916번 최소비용 구하기 풀이 처음에는 dfs를 사용하여 코드를 작성했다. 주어진 예제의 경우는 n이 작기 때문에 잘 동작했는데 채점을 돌려보니 RecursionError로 런타임 에러가 발생했다. def dfs(L, val): global

문제 백준 1935번 후위 표기식2 풀이 각 알파벳에 대응되는 값을 넣어주기 위해 딕셔너리를 사용했다. 표기식을 숫자로 바꿔주고 난 다음은 스택으로 계산하면 된다. 출력형식이 소수 둘째자리까지인데 까먹어서 검색해서 풀었다.

백준 1966번 프린터 큐간단한 구현 문제. 15분정도 소요됐다.처음에는 그냥 (중요도, 문서번호) 순서로 키 값을 설정해 정렬하면 되겠다 생각했는데,중요도가 낮을 경우 큐의 맨 뒤로 삽입한다고 명시되어있기 때문에 deque를 사용해야 했다.아직 구현 문제에서 입출력을

쉬운 문제도 다 이유가 있다... 메모리 초과에 주의하자.. 항상 효율적인 코드 짤 생각을 할 것

아주 기본적인 그리디 문제. 그리디에 정렬이 빠지면 섭하다.

백준 2293번 동전1 또 생각없이 dfs로 풀었다. 어김없이 RecursionError 당했다.이제 좀 dfs 트라우마 생기려함.도저히 방법을 모르겠어서 알고리즘 분류를 봤다. 동적프로그래밍이었다...다음과 같이 동적 배열을 구할 수 있다.공간 효율을 위해 2차원 리

dp 문제. 그런데 이제 두번다시 마주치고 싶지 않은 감정을 곁들인..

문제 백준 2346번 풍선 터뜨리기 풀이 덱을 사용하는 문제. 가중치cnt가 양수, 음수 모두 있기 때문에 양수일 경우에는 -1을 해줘야 해당 풍선에 도착했을 때 cnt == 0의 조건을 만족할 수 있다. 처음에 1번 풍선을 터뜨릴 때 양수일 때만 -1을 했어야

분할정복 알고리즘 너무 오랜만이라서 풀이 방법 완전히 까먹고있었다... 재귀탐색하는 과정을 구현하는게 너무 오래걸렸다.

백준 2667번 단지번호붙이기보자마자 dfs로 풀어야지라고 생각했다.. 제일 만만한가...?입력이 공백구분없이 들어오기 때문에 문자열 한 줄씩 각 문자에 대해 타입변환하여 입력받았다.board에서 1을 만날 때마다 단지 하나를 추가하고 dfs()를 호출하여 단지 내 집

부모노드 정보만 저장해도 되는건데 계속 자식노드 정보를 저장하느라 어떻게 트리를 지지고 볶아야되는지 한참을 고민하고 빙빙돌아갔다.

dp 기본문제

정렬된 리스트에서 어떠한 숫자 x가 존재하는지 탐색하기 위해 중앙값을 두고 비교한다.

새삼 sys.stdin.readline()의 중요성을 깨달았다... 아무리 코드 고쳐도 계속 시간초과나서 환멸났는데 input()에서 sys.stdin.readline()으로 바꾸자마자 맞았습니다 뜨네 ㅎ;

정렬할 때만 람다식 쓰다보니까 자꾸 간간히 쓰는 방법을 잊는다..

다이나믹 프로그래밍 기본 문제

아주 기본적인 다이나믹 프로그래밍 문젠데 약간 응용된 문제였다. 그림 그려서 규칙찾을 때 빼먹는거 없도록 조심하자.

투포인터 대표문제

누워서 폰하다 불현듯 풀이 생각나서 노트북 켰는데 틀렸음ㅎ 그래서 구글 검색했는데 와 진짜 어이없게 간단했고.. 그리디.. 아직 많이 부족하다. 더 많이 풀어보고 다양한 접근 방식을 익혀둬야겠다.

집합 자료형을 이용해서 쉽게 풀었다.. 알고리즘 분류가 자료구조, 트리를 사용한 집합과 맵이다. 이런 쉬운 문제의 경우 코딩테스트에서는 기본 제공 기능에 제한을 두기 때문에 다른 풀이를 생각해봐야겠다.

백준 14503번 로봇청소기코드 다 짜놓고 입력값을 잘못 이해하고 있어서 쓸데없이 오래걸렸다ㅡㅡ오류1 - 입력값 r, c가 1부터 시작하는 줄 알고 배열에 적용한다고 -1을 해줬었다.오류2 - direction에 r, c를 반대로 넣고 있었다.....오류 잡는다고 1시

잡생각하면서 풀었더니 쓸데없이 정말 오래걸렸다.

뭐가 잘못된지 몰랐다. 그리고 x1, y1을 쓸데없이 왜주나 생각했다. 역시 그냥 주어지는 건 없다. 항상 모든 것엔 이유가 있다;;

간단한 다이나믹 프로그래밍 문젠데 조금 오래걸렸다. 1차원 배열로 풀 때 특히 생각이 오래걸리는 편이다. 다이나믹 프로그래밍 문제 더 많이 풀고 시간 단축할 것

백준 16967번 배열 복원하기 간단한 구현 문제였다.손으로 b배열을 그려보고서야 이해됐다. 쉬운 난이도임에도 15분정도 소요된 것 같다.

도저히 모르겠어서 검색해보고.. 투에모스 수열이라는 걸 처음 알게되었음ㅎ;;ㅎㅎ;

좀 더 가독성있게 바꾸려고 check[i] == 1이 출석된 걸로 바꿔서 채점 돌렸는데 시간초과가 났다. 이유를 찾아봐야겠다.. -> 누적합을 이용해서 시간을 개선했다.

언제나 투포인터 문제를 풀때면 인덱스에러를 마주한다. 포인터의 종료지점 및 종료조건을 잘 파악해서 제발 while의 브레이크가 안고장나도록 하자.

언젠가 배웠었던 슬라이딩 윈도우가 생각났다.그래놓고 처음엔 for문에서 sum() 함수 돌렸다. 시간초과 날 줄도 모르고. 포인터를 사용해서 시간복잡도를 개선하자.

round() 함수는 해당 자리의 수가 5일 때 값이 불분명해진다. 소수점 넷째자리까지 반올림이면 0.00005를 더한 후 버림하는 것과 같다.

집중 못하고 계속 문제 삽질하지말라고~ 뭐하러 split() 놔두고 손수 파싱했는지 모르겠고.. 또 그걸 반복문 돌리면서 계산하고 있었다..ㅎㅅㅎ