알고리즘/Algospot 썸네일형 리스트형 28.2 문제: 고대어 사전(문제 ID: DICTIONARY) 28.2 문제: 고대어 사전(문제 ID: DICTIONARY, 난이도: 하) 위상정렬 문제... 위상정렬은 사이클이 없는 방향 그래프, 즉 DAG일 때만 가능한데.. 위상정렬이 맞는지 아닌지 체크하는 코딩 방법을 모르고 있었다... 그래서 헤메다가 책을 보고 역방향 간선이 존재하는지 여부만 체크하면 된다는 것을 알게 되었다. 위상 정렬을 할때는 bfs 를 쓰거나 dfs를 쓰는 두가지 방법이 있다. 이번 문제에서는 dfs 로 위상정렬을 하고 리턴될때마다 저장한 vector를 이용해서 역방향 간선을 체크할 수 있는 방법을 알게됐다. (bfs로 풀때 위상정렬 체크하는 방법도 알아놔야 겠다!) 원래는 그냥 스택에 넣고 출력만 했었는데, 위상정렬을 한번 더 체크하려니 조금 복잡했었다. 책에서는 이차원 배열같이 해.. 더보기 외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하) ★★★★★다시 풀어 볼 문제★★★★★ 알고리즘 문제해결 전략 1권외발 뛰기 (문제 ID: JUMPGAME, 난이도: 하) 나름 DP문제는 많이 풀어봤다고 생각했지만 , 이 문제처럼 TRUE FALSE로 답을 내는 문제는 처음이었다.내가 푼 DP문제들은 경우의 수를 구하는 문제가 대부분이었다.그러다 보니 약간 생소한 느낌이고, 다른 문제를 푸는 느낌이었다.그래서 풀어보는데 이해가 안가고 고민해야 했던 부분이 많았다. # 내가 지금까지 풀어온 DP는 뭔가 점화식을 정하고 풀어야 한다는 강박관념이 있었는데,이 문제는 그냥 재귀함수로 원하는 칸에 도달할 때까지 풀면서, 메모이제이션만 하면 됐다.물론 이 과정에서 점화식을 구하고 풀어도 되겠지만 딱히 점화식이라고 생각하지 않았다(개인적으로) 코드적 스킬은 마지막 .. 더보기 6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) ★★★★★다시 풀어볼 문제★★★★★ 알고리즘 문제해결 전략 1권6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 문제를 제대로 읽지 못해서 풀지 못한 케이스.처음에는 단순히 0번 부터 9번까지 스위치를 킬것인지 말것인지 로 풀었다가다시 읽어서 여러번 스위치를 켤 수 있지만 10번만 누르는 것인 줄 스스로 착각한 문제.그러다보니 기저 조건 등을 틀리게 작성해버렸다. 그리고 다시 짤때도 스위치를 누르지 않는다/ 스위치를 1~3번 누른다로 나누어서 생각하는 바람에한참을 고민했었다. 하지만 스위치를 0~3번 누른다로 생각을 바꿔서 푸니까 쉽게 풀렸다. 문제를 잘 읽는게 정말 중요하다는 것을 느꼈다. 시간 초과 코드 1234567891011121314151617181920212223242.. 더보기 6.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하) ★★★★★다시 풀어볼 문제★★★★★ 알고리즘 문제해결전략 1권6.5 문제: 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하) 완전탐색 문제 첫번째 코드는 시간상 오류가 나는 코드이다.내가 보기에 슈퍼컴퓨터라면 정답은 나올 것 같다;;나름 중복되는 경우의 수를 지우기 위해 재귀함수의 for문을 건드렸지만, 아주 미세한 차이만을 나타냈을 뿐이었다.일단 나름 책에서의 첫문제를 적용해서 풀려고 노력은 했다는 점은 만족한다. 정답 코드는 일단 for문에서 경우의 수를 줄이려고 한 것이 아니라는 점이 좋았다.나 같은 경우에는 항상 for문을 복잡하게 만들어서 경우의 수를 줄이려고 하는 습관이 있었는데 그것을 깰 수 있었다.내가 실수한 점은 진짜 무식하게 모든 경우를 돌려서 블록을 맞추려고 했던 점이고,.. 더보기 6.3 문제 : 소풍 ( 문제 ID: PICNIC , 난이도: 하) ★★★★★다시 풀어볼 문제★★★★★ 알고리즘 문제 해결 전략 1권6.3 문제 : 소풍 ( 문제 ID: PICNIC , 난이도: 하) 완전탐색 문제를 재귀로 구현. 이번에 내가 치뤘던 삼성 소프트웨어 역량 평가 1번 문제랑 흡사한 듯 보인다.내가 그 문제를 못 풀었던 것 처럼 이 문제도 풀지 못했다. 다시 한번 그 문제를 풀어봐야 겠다. 생각보다 그렇게 복잡하게 생각하지 않아도 되는 문제.단 주의할 점은 중복하는 경우의 수를 계산하는 방식.난이도가 하라고 표기되어 있지만 나한테는 어려웠던 문제. 이 문제를 통해서 bool 타입 변수를 어떤 이름으로 선언해야 효과적인지 배울 수 있었다.그 동안 bool 타입을 선언하고 조건문 안에서 이게 언제 true일까 false 일까 하는 고민으로 낭비되는 시간을 좀 줄.. 더보기 이전 1 2 다음