'PS/BOJ&Programmers' 카테고리의 글 목록 (5 Page)

[백준/13424] Three Dots / 완전탐색 - 파이썬

2023.01.17·

PS/BOJ&Programmers

📝 알고리즘 이 문제는 완전탐색 방식으로 풀면 점의 개수가 1000 개일 때, 1000 * 1000 * 1000 = 10^9로 시간 초과를 하게 된다. 따라서 세 점의 거리가 동일한 케이스를 모두 계산하는 방법이 아닌, 동일한 간격이 존재하는 점을 찾는 방식으로 구현하도록 한다. 수직선 상에 임의의 세 점 a,b,c가 있을 때 점 C는 b에서 a와 b의 거리만큼 더한 값이다. 이 알고리즘을 활용하여 점 C를 찾고, 이 값이 입력받은 list에 존재한다면 세 점은 동일한 거리를 가진 점들이다. 💻 최종 코드 from collections import defaultdict t = int(input()) for _ in range(t): n = int(input()) dots = sorted(list(map(..

[백준/12759] 틱! 택! 토! - 파이썬

2023.01.17·

PS/BOJ&Programmers

📝 첫번째 시도 개인적으로 이 문제가 어려웠던 이유는 게임이 끝나고 승부를 판단하는 게 아니라 입력이 될 때 누가 언제 이기는지 알아내야 하기 때문에 헤맸다. 만약에 승부만 판단하는 문제였다면, 플레이어 1과 2가 했던 게임을 입력 받고 승부 조건만 확인하면 되기 때문이다. 그래서 처음에는 이렇게만 이해하고 다음과 같이 코드를 작성했다. # 먼저 시작하는 사람 n = int(input()) g = [[' ']*3 for _ in range(3)] for i in range(9): r,c = map(int, input().split()) # 게임판 if i % 2 == 0: g[r-1][c-1] = 'X' else: g[r-1][c-1] = 'O' # 승부 확인을 위해서 새로운 배열에 대입. res = [..

[백준/1100] 하얀 칸/파이썬 2차원 리스트/체스판 - 파이썬

2023.01.16·

PS/BOJ&Programmers

💡 파이썬 2차원 리스트 이 문제를 풀 때 8x8의 체스판을 입력 받고 정의해야 한다. 파이썬 2차원 리스트를 선언하는 방법은 다음과 같다. 파이썬 2차원 리스트는 좌표평면이나 행렬 등과 같은 표현을 해야할 때 쓰이므로, 익혀두는 게 좋을 것같다. # 방법1 arr = [list(input()) for _ in range(8)] # 방법2 arr = [] for i in range(8): arr.append(list(input())) 📝 문제 해설 T F T F T F ... F T F T F ... T F T ... 체크무늬 체스판을 떠올리면 된다. 하얀 칸 위에 말이 몇 개 있는지 출력해야 하기 때문에, 하얀 칸의 인덱스에 대한 정보를 알아야 한다. 이때 행렬 좌표의 특성을 활용하면 편하다. (행번호..

[백준/11652] 카드 - 파이썬

2023.01.14·

PS/BOJ&Programmers

📝 알고리즘 처음에는 정수를 하나씩 입력 받으면 정렬해서, 양옆을 비교한 뒤 같은 값이면 카운팅을 해주는 방법을 고안했다. 그러나 같은 값이 몇개인지 세어볼 때는 딕셔너리를 이용하는 게 효율적이다. 기준이 되는 값을 key에, 해당 개수를 value에 저장하면 된다. 얼마 전에 풀었던 https://www.acmicpc.net/problem/1159 문제도 이와 비슷한 알고리즘으로 같은 값 개수 세기문제를 해결할 수 있다. 1159번: 농구 경기 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작 www.acmicpc.net for _ in range(n): num = ..

[백준/14582] 오늘도 졌다 / 야구에 대한 이해 / 파이썬 리스트 누적합

2023.01.14·

PS/BOJ&Programmers

🔎 문제 이해 평소 야구를 즐겨보지 않아서 그런지 초와 말에 대한 개념이 없었다. 그래서 처음엔 그냥 i번째에 이기고 있으면 역전패가 성립한다고 코드를 구현했는데 틀린 거다...! 질문 게시판을 통해 반례를 찾아보니 출제자가 그래서 문제 마지막에 경기는 1회초 -> 1회말 -> 2회초 -> ... -> 9회초 -> 9회말이라는 설명까지 덧붙인 듯하다. 역시 문제를 꼼꼼히 잘 읽는 것도 중요하다. 괜히 써진 문장은 없기 때문에 최대한 힌트를 많이 얻어가는 게 유리하다. 💡 파이썬 리스트 원소 누적합 게임은 현재까지 얻었던 점수들의 합으로 판단을 하기 때문에, 누적합을 구해서 승부를 판단했다. a = list(map(int, input().split())) b = list(map(int, input().sp..

[백준/7510] 고급 수학

2023.01.14·

PS/BOJ&Programmers

🔎 알고리즘 삼각형의 세 변의 길이가 주어졌을 때, 이 삼각형이 직각 삼각형인지 아닌지 판단하기 위해 피타고라스의 정리의 역을 이용하면 된다. 피타고라스의 정리 : 직각삼각형에서 빗변 길이의 제곱은 다른 두 변의 길이의 제곱의 합과 같다. 피타고라스 정리의 역 : 세 변의 길이가 a,b,c인 삼각형에서 a^2 + b^2 = c^2이면 c가 빗변인 직각삼각형이다. 💻 최종 코드 각 변의 길이 위치를 알아야 계산을 할 수 있기 때문에 sorted(s)로 입력 받은 값을 정렬해주고, 인덱싱을 통해서 피타고라스의 역을 계산해주었다. n = int(input()) for i in range(n): s = list(map(int, input().split())) s = sorted(s) print('Scenario..

[백준/3986] 좋은 단어 / 스택 / 스택 활용법 / 스택 원리

2023.01.13·

PS/BOJ&Programmers

아쉽게도 처음부터 이 문제를 보고 스택으로 풀어야겠다!! 라고 떠오른 건 아니다. 처음에 인덱스가 짝수인 / 홀수인 경우를 나눠서 세어보려고 했는데,, 알고리즘이 너무 복잡하고 변수도 쓸데없이 많다는 생각에 서치를 했다! 오래 고민하고 생각했는데도 내가 생각하는 알고리즘이 이상하다/도저히 모르겠다 싶을 땐, 빠르게 다음 스탠스를 취하는 것도 중요한 것같다.. 생각보다 아직 나는 아는 게 없기 때문이다. 그래도 괜찮다. 알고리즘 공부를 더욱 꾸준히, 열심히 해서 아는 영역을 넓혀 나가는 것이 이번 방학의 목표이기 때문에, 하루하루 정진하다보면 방학이 끝날 때 쯤엔 나도 아는 게 꽉꽉 차있을 테니까~~~~ 혹시 스택에 대해 모르신다면? https://cobinding.tistory.com/entry/%EC%..

[백준/11179] 2진수 뒤집기

2023.01.12·

PS/BOJ&Programmers

이 문제는 2진수 -> 10진수 변환과 10진수 -> 2진수 변환 모두를 구현해야 하는 문제이다. 파이썬 내장 함수와 문자열 인덱싱을 통해 쉽게 구현할 수도 있지만, 직접 코드를 작성해보았다. 💻 최종 코드 n = int(input()) b = [] x = 0 ans = [] c = 0 while n != 0: if n % 2 == 0: b.append('0') else: b.append('1') n //= 2 # 뒤에서부터 append 되니까 어차피 뒤집혀 나옴 s = ''.join(b) for i in range(len(s)-1,-1,-1): x = int(s[i]) * 2 ** c ans.append(x) c += 1 print(sum(ans)) while 문은 10진수를 이진수로 변환한 코드이다...

[백준/2947] 나무 조각/정렬/두가지 풀이

2023.01.11·

PS/BOJ&Programmers

💻 내 풀이 직관적인 풀이라고 생각하지만 정석보다 우회해서 푼 느낌이라 코드를 더 찾아봤다. t = input().split() tmp = 0 s = sorted(t) while True: for i in range(1,len(t)): if t[i-1] > t[i]: tmp = t[i-1] t[i-1] = t[i] t[i] = tmp print(*t) if t == s: break 💻 다른 풀이 t = input().split() for j in range(len(t)): for i in range(1,len(t)): if t[i-1] > t[i]: t[i-1], t[i] = t[i], t[i-1] print(*t) 내 기억상 이게 버블소트랑 가장 가까웠던 것같다. 출처: https://it-garden..

[백준/6996] 애너그램.. 반례찾기

2023.01.10·

PS/BOJ&Programmers

🔎 처음시도 n = int(input()) for _ in range(n): a, b = input().split() cnt = 0 for i in a: if i in b: cnt += 1 if cnt == len(a) and len(a) == len(b): print('{} & {} are anagrams.'.format(a,b)) else: print('{} & {} are NOT anagrams.'.format(a,b)) 반례: aaaa aaab. 이유: if i n b 코드에서 변수 a와 변수 b가 가진 a의 개수에 상관없이, 포함되어있는지 아닌지만 판단했기 때문에, 오류 발생.. 그래서 a,b 서로서로 검사해주는 코드로 바꿨는데 또 .. 틀린거다... 틀린 이유는 똑같음.. 같은 어미가 있을 때..

[백준/1159] 농구경기

2023.01.10·

PS/BOJ&Programmers

🔎 문제 이해 오늘 딕셔너리를 공부해서 그런지 보자마자 첫글자를 key값으로 넣고, 다음 입력값의 첫글자가 이미 딕셔너리 key로 저장되어 있다면 +1 해주는 로직이 떠올랐다. 📝 첫번째 시도 _ 실패 n = int(input()) d = {} for i in range(n): name = input() key = name[0] # 만약 이미 d에 key 값이 존재하는 경우 if d.get(key): d[key] += 1 else: d[key] = 1 ans = list(d.values()) for i in ans: if i >= 5: for k,v in d.items(): print(k) 첫번째 시도 모든 key 값을 출력해버림. 당연하다. items 함수를 통해 딕셔너리의 key값을 구했기 때문이다...

[백준/5704] 팬그램/ 카운트, 딕셔너리

2023.01.04·

PS/BOJ&Programmers

🔎 처음 시도 이중 포문으로 하나하나 비교하면 되겠지?라는 생각으로 모두 비교해줬는데, 이렇게 하면 입력이 한꺼번에 주어졌을 때 밀리는 현상 때문에 올바르게 판단을 못한다. 얘가 검사를 다할 때까지 sleep을 건다고 쳐도, 잘못된 알고리즘인 것같다는 생각이 들었다. 어쨌든 문자열을 보려면 모든 문자열을 다 확인해봐야 하는데,, 어떻게 할까 하다가 알게된 find 함수. str.find(찾고자하는 문자열) 형식으로 사용된다. 만약 값을 찾으면 str의 해당 인덱스가 반환되고, 없으면 -1을 반환한다. 🤔 두 번째 시도 cnt = 26 # 총 알파벳 개수 while True: sentence = input() sentence.replace(" ", "") if sentence == '*': break fo..

[백준/1551] 수열의 변화

2023.01.04·

PS/BOJ&Programmers

💻 최종 코드 n,k = map(int, input().split()) num = list(map(int, input().split(','))) for _ in range(k): ans = [] # 초기화 for i in range(1,len(num)): sub = num[i] - num[i-1] ans.append(sub) num = ans # num을 계산한 값으로 초기화 print(*num, sep=',') 크게 어려운 알고리즘은 필요없지만, for문의 구조와 초기화해서 값을 갱신한다는 지식이 없으면 풀기 힘들 것같다..! 생각은 떠올랐지만, 구현하는 데에 좀 시간이 걸렸다. 이중 포문에 조금 더 익숙해져야겠다는 생각이 들었다.

[백준/4458] 첫 글자를 대문자로

2023.01.01·

PS/BOJ&Programmers

🔎 두 가지 방법 이 문제를 구상할 때 문자열은 불변 데이터니까 새로 정의해줘야 하는 번거로움을 피하기 위해 list로 작성했다. 하지만 (이 경우에 한해서) 둘의 속도 차이는 별로 크지 않았고, 두 방법을 적재적소에 사용하기 위해 다 익혀놓는 것이 좋을 거라 생각해서 두 가지 모두 구현해보았다. 💻 list를 활용한 구현 n = int(input()) for _ in range(n): s = list(input()) s[0] = s[0].upper() print(''.join(s)) 파이썬의 join 함수를 활용하여 리스트를 문자열로 변경해주었다. 💻 문자열을 활용한 구현 n = int(input()) for _ in range(n): s = input() new = s[0].upper()+s[1:] ..

[백준/15726] 이칙연산

2023.01.01·

PS/BOJ&Programmers

처음 작성한 코드 a,b,c = map(int,input().split()) # 가장 작은 값을 나누고 큰 값끼리 곱함 print(max(a*b/c)) 'float' object is not iterable 이라는 오류가 발생한다. max 함수는 iterable(반복가능한) data에 적용되는 함수이기 때문에 두 개 이상의 값을 작성하거나, list와 같은 여러 데이터의 집합에 적용해야 한다. 최종 코드 a,b,c = map(int,input().split()) # 가장 작은 값을 나누고 큰 값끼리 곱함 print(max(int(a*b/c), int(a/b*c))) 둘 중에 더 큰 값을 출력하면 되니까 위와 같이 코드를 작성하면 된다. 굳이 큰 수 작은 수 비교를 하지 않아도 연산을 하고나서 큰 값을 판..

티스토리툴바